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 x 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).

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

The first line contains one integer: K.

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.

• 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).