costinland

Costin is the dictator of Costinland, a country located on a very small island in the middle of Pacific Ocean. One day, Costin started feeling depressed because his island was very small. In order to stop his own depression, he decided to conquer other countries, so that the territory of Costinland and his influence as a dictator will be even bigger! In order to do that, he needs an army! But no citizen of Costinland fits the dictator’s requirements… So what army would be better than an army of Costins? Thus, being the smartest person living in Costinland, he invented cloning on a Saturday evening. Being a very playful person (the most playful person in Costinland), he wanted to play with his clones while creating them.

For that, Costin chose a piece of land consisting of $N \times M$ cells. There are $4$ types of cells: X (if a Costin steps on this cell, he clones himself; one of the Costins goes right and the other one goes down), r (if a Costin steps on this cell, he will go right, regardless of his initial direction), d (if a Costin steps on this cell, he will go down, regardless of his initial direction), . (if a Costin steps on this cell, he will not change his initial direction and will move to the next cell indicated by his direction).

Costin leaves from $(1,1)$ and wants to reach $(N,M)$, along with all of the created clones. Costin is also very lazy (the laziest person in Costinland), so he asks you “nicely” to help him build such a matrix, such that exactly $K$ clones will reach $(N,M)$. Clones cannot be “lost” on their way (read the constraints carefully).

Task

Given $K$, help Costin generate such a (small) matrix that will bring to $(N,M)$ exactly $K$ Costins.

Input data

The first line contains one integer: $K$.

Output data

The first line will contain to integers: $N, M$ (the size of the matrix). The following $N$ lines will contain $M$ characters, describing the matrix.

Restrictions

• The character situated on $(1,1)$ must be different from ., in order to give a direction to the first Costin. (It can be X, d or r)
• None of the Costins stops until he reaches $(N,M)$.
• In order not to waste Costins or to lose them somehow during their path, the last line of the matrix will consist only of r and the last column will consist only of d. By exception, the character situated on $(N,M)$ will be . (There is no need to give the Costins a direction since they reached their destination)
• In order to get $100$ points, you need to generate a matrix with both of its sides smaller than or equal to $5$, for the first subtask, and one with both of its sides smaller than or equal to $49$, for the second subtask (more details below in the SCORING section).

Scoring

Let $C \times D$ be the contestant’s matrix size.

Subtask 1:

• If $max\{C,D\} \leq 5$, you will receive $100\%$ of the points on that test case.
• If $max\{C,D\} = 6$, you will receive $60\%$ of the points on that test case.
• If $6 <$max{C,D}$\leq 500$, you will receive $60 \cdot \frac{500 - max\{C,D\}}{500-6} \%$ of the points on that test case.
• If $max\{C,D\} > 500$, you will receive $0\%$ of the points on that test case.

Subtask 2:

• If $max\{C,D\} \leq 49$, you will receive $100\%$ of the points on that test case.
• If $49 < max\{C,D\} < 62$, you will receive $60 + 40 \cdot \frac{1.2^{62 - max\{C,D\}}}{1.2^{62-49}} \%$ of the points on that test case.
• If $max\{C,D\} = 62$, you will receive $60\%$ of the points on that test case.
• If $62 < max\{C,D\} \leq 500$, you will receive $60 \cdot \frac{500 - \max\{C,D\}}{500-62} \%$ of the points on that test case.
• If $max\{C,D\}>500$, you will receive $0\%$ of the points on that test case.

Compiler messages

• "The output does not fit the requirements": You will get this message if your matrix does not respect the constraints or the output data.
• "Matrix size too big": You will get this message if $max\{C,D\}>500$.
• "The matrix does not generate the required number of Costins": You will get this message if, in the end, there won’t be exactly $K$ Costins in $(N,M$).
• If you don’t get any of these messages, you will receive a score according to the formulas from above and a message which specifies the size of your generated matrix for that test case.

Example

stdin

11

stdout

4 4
XXXd
.XXd
.XXd
rrr.