One morning, during a traditional inspection of a potato field, the cat Matroskin found a Colorado potato beetle on one of the bushes. Terrified, he immediately rushed off to ask Uncle Fyodor (as the most educated of his friends) about how these beetles reproduce and how to deal with them.
Potato fields are usually very neatly arranged: potato bushes are planted on them so that they form a checkered field, where each cell — potato bush. As soon as the Colorado potato beetle appears on one of the bushes, it begins to actively eat and multiply. Therefore, every hour, as many beetles will be added to each bush as the bushes adjacent to it on the side, already infested with beetles. For example, if a bush has exactly one neighbor that already has bugs, then one bug will be added to it, and if all four neighbors are infected with bugs, then four new bugs will be added to the bush. And if the beetles are not stopped, they will fill the entire field with themselves. But fortunately, once upon a time, Uncle Fyodor, after reading an article in Murzilka, made a Colorado potato beetle repeller...
To be honest, Matroskin did not really understand how this repeller works. But he remembered the main thing: it must be installed on one of the potato bushes, and as soon as there are exactly k Colorado potato beetles on this bush, something (Matroskin did not understand this) will happen and all the beetles will run away from the field.
Knowing the coordinates of the potato bush on which Matroskin installed the repeller, calculate how many hours after the appearance of the first Colorado potato beetle on the field it will act. Matroskin set a trap in the first hour after the beetle appeared on the field.
Input
You are given three numbers: x and y — the coordinates of the potato bush, on which Matroskin installed the repeller, and k — repeller parameter (1<=k<=10
9, |x|<=10
9, |y|<=10
9 ). The bush where the first beetle was found has coordinates (0, 0) . The coordinates of all field bushes do not exceed 10
9+1 modulo.
Imprint
Print a single integer: after how many hours the trap will work. If the trap never works, print −1.
Examples
| # |
Input |
Output |
| 1 |
0 0 1 |
0 |
| 2 |
0 0 5 |
2 |