HIE - Hieroglyphs

no tags 

Original problem statement (in Polish) can be found here.

Archibald the Archeologist is on the trail of a great mystery! This mystery is so great, and deals with such important matters, that solving it would surely cause a massive uproar in the communities of archeologists and computer scientists alike. Whole textbooks would have to be rewritten from scratch, from "Introduction to archeology" to "Algorithms and data structures".

That's what Archibald claims, anyway. But most of the scientific world considers him insane since the Rosetta Stone incident (which allegedly contained pseudocode of Dijkstra's algorithm). This time, he claims the existence of previously unknown, ancient South American La-Og-Mhtir civilization - moreover, he has the evidence to support that claim. Their temple, hidden somewhere in the underground of the Amazon rainforests, supposedly contains boundless amounts of ideas, and revealing them would lead to several breakthroughs in computer science. Archibald proposes a bold thesis that even P=NP problem was already solved by this civilization, and the proof (which is elegant and ingenious) can be found somewhere in the heart of their shrine.

La-Og-Mhtirs' temple is really well hidden - despite multitude of hints that Archibald found during many years of his studies, he still can't pinpoint its exact location.

It looks like this time he is really close, though! During his expedition in the Central Andes in Chile, he found some ancient tablets. There is an inscription above the entrance to the chapel: "Fastest solution will be found only by the ingenious one", and it uses very characteristic symbols of the La-Og-Mhtirs' alphabet (which, by sheer luck, has 26 letters, just like the English alphabet).

Archibald carefully examined two biggest tablets on the inner wall of the chapel. Both contained n rows of letters, and there were n letters in each row. He also found a bizarre mechanism behind the first one! By tinkering with some buttons (made from stone), Archibald can turn any letter on the first tablet into another one from the alphabet - but it takes a long time (n2 hours). After further examination it turned out that another set of buttons can be found near the chapel's ceiling - by using them, it is possible to choose a square-shaped area inside the tablet, and rotate it by 90 degrees (clockwise or counterclockwise) - and it only takes one hour! For no apparent reason, chosen square has to be at least 5 letters wide.

As an example: in the picture above, by choosing a 5x5 square with top left corner in the second row and the second column of the first tablet, and rotating it counterclockwise, we obtain the second tablet. Rows and columns are numbered from 1 to n, from top to bottom and from left to right.

Finally, the mystery gradually uncovers itself, right before the Archibald's eyes. Devoting whole life to studying various hints, scattered throughout the world, is starting to pay off. The only thing left to do for Archibald is to use the mechanisms, and make the first tablet look exactly like the second one. More than that - it has to be done as quickly as possible. If La-Og-Mhtirs will deem his solution worthy, the chapel will reveal the location of the Great Temple.


The first line contains a single integer t, denoting the number of testcases. (t <= 10). The descriptions of the testcases follow.

The first line of the description contains a single integer n - size of the tablets. (5 <= n <= 30). Then the descriptions of the two tablets follow. The description of a single tablet consists of n lines, each containing n uppercase letters of English alphabet (which correspond to appropriate letters of La-Og-Mhtirs' alphabet). The j-th character in the i-th line describes the i-th row and j-th column of the tablet.


For each testcase you should find a sequence of moves that will turn the first tablet into the second one. The sequence starts with two integers m and k (0 <= m <= n3, 0 <= k <= n4), denoting the number of moves in the sequence and the time needed to execute that sequence in hours, respectively. Then you should output the descriptions of the m moves.

The description of one move starts with a string "Z", "OL", or "OP", denoting changing one letter, rotating a square counterclockwise and rotating a square clockwise, respectively. For a "Z" move, you should then output two integers r, c and a single character of the English alphabet x (1 <= r,c <= n). It denotes changing the letter in the r-th row and c-th column to x.

For a "OL" or "OP" move, you should then output three integers r, c, q. (1 <= r,c <= n, 5 <= q <= n). It denotes a rotation of the square that is q letters wide, with top left corner in the r-th row and the c-th column. Given square should be completely contained inside the tablet.





2 37
OL 2 2 5
Z 6 6 X


If the sequence of moves satisfies all the conditions given in the problem statement, and k is computed correctly, it is worth k/(n4) points. Overall score is equal to the sum of individual scores.

Sample testcase explanation

First operation rotates a square 5 letters wide, with its top left corner in (2,2). This operation takes 1 hour to execute. Second operation changes the letter in the sixth row and the sixth column to "X", which takes 62 hours to execute. Then, the total score is (1+62)/(64) which is about 0.029.

Added by:Piotr Jagiełło
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:PIZZA 2015 qualifying round