A long time ago (probably even in the first book), Nicholas Flamel, a great alchemist and the creator of the Philosopher's Stone, taught Harry Potter three useful spells. The first one allows you to convert a grams of sand into b grams of lead, the second one allows you to convert c grams of lead into d grams of gold and third one allows you to convert e grams of gold into f grams of sand. When Harry told his friends about these spells, Ron Weasley was amazed. After all, if they succeed in turning sand into lead, lead into gold, and then turning part of the gold into sand again and so on, then it will be possible to start with a small amount of sand and get huge amounts of gold! Even an infinite amount of gold! Hermione Granger, by contrast, was skeptical about that idea. She argues that according to the law of conservation of matter getting an infinite amount of matter, even using magic, is impossible. On the contrary, the amount of matter may even decrease during transformation, being converted to magical energy. Though Hermione's theory seems convincing, Ron won't believe her. As far as Ron is concerned, Hermione made up her law of conservation of matter to stop Harry and Ron wasting their time with this nonsense, and to make them go and do homework instead. That's why Ron has already collected a certain amount of sand for the experiments. A quarrel between the friends seems unavoidable...
Help Harry to determine which one of his friends is right, and avoid the quarrel after all. To do this you have to figure out whether it is possible to get the amount of gold greater than any preassigned number from some finite amount of sand.
Note
Consider the first sample. Let's start with the
500 grams of sand. Apply the first spell
5 times and turn the sand into
1000 grams of lead. Then apply the second spell
4 times to get
600 grams of gold. Let’s take
400 grams from the resulting amount of gold turn them back into sand. We get
500 grams of sand and
200 grams of gold. If we apply the same operations to
500 grams of sand again, we can get extra
200 grams of gold every time. Thus, you can get
200,
400,
600 etc. grams of gold, i.e., starting with a finite amount of sand (
500 grams), you can get the amount of gold which is greater than any preassigned number.
In the forth sample it is impossible to get sand, or lead, or gold, applying the spells.
In the fifth sample an infinitely large amount of gold can be obtained by using only the second spell, which allows you to receive
1 gram of gold out of nothing. Note that if such a second spell is available, then the first and the third one do not affect the answer at all.
The seventh sample is more interesting. We can also start with a zero amount of sand there. With the aid of the third spell you can get sand out of nothing. We get
10000 grams of sand in this manner. Let's get
100 grams of lead using the first spell
100 times. Then make
1 gram of gold from them. We managed to receive
1 gram of gold, starting with a zero amount of sand! Clearly, in this manner you can get an infinitely large amount of gold.