The robot moves along the checkered plane and draws a spiral. Initially, it is in cell (0, 0) and is directed towards increasing the first coordinate.
Then it acts according to the following algorithm: it makes d moves forward, then it turns left and again makes d moves forward. After that, it turns to the left and multiplies the value of d by k. The robot then repeats the described process. The robot stops after a total of exactly n moves.
It is required to display a picture showing the cells visited by the robot.
Input
The input is integers n, d and k (1 ≤ n ≤ 1000, 1 ≤ d ≤ 100, 2 ≤ k ≤ 5).
Imprint
Let the minimum rectangle of cells containing all the cells visited by the robot have height h and width w. On the first line print the numbers h and w separated by a space. The next h lines should contain w characters each, print "*" for the cell visited by the robot and "." for the unvisited.
Examples
| # |
Input |
Output |
| 1 |
13 2 2 |
5 5
*****
*...*
*.***
*....
**...
|