Push-Complement-Reverse

We are given a sequence consisting of N numbers ~\mathbf{x_1,x_2,\ldots,x_N}~, each belonging to the set {0, 1, 2, 3}. We play the following game for a player and two pieces of paper (left and right):

1. We start by writing down the sequence of numbers on the left paper. The right paper is empty.
2. We choose one of the following three moves:
   • 'p' (push): we erase the first number from the sequence on the left paper and write it down at the end of the sequence on the right paper.
   • 'c' (complement): we replace all numbers on the left paper with their complements modulo 3. That is, the number x is replaced by 3-x.
   • 'r' (reverse): we reverse the order of numbers on the right paper. That is, the first becomes the last, etc.
3. The game ends when all numbers are erased from the left paper.
4. The player wins if, at the end of the game, all 0s are adjacent, all 1s are adjacent, etc., in the sequence of numbers on the right paper.

Our goal is, of course, to find a sequence of moves with which the player wins. However:

• If this can be achieved in more than one way, we want to make the fewest possible moves.
• Finally, if this can be achieved in more than one way, we choose the lexicographically smallest sequence of moves.

We call the sequence of moves that wins the game and satisfies the above criteria "optimal."

For example, let's start with an initial sequence of 2, 3, 2, 1, 0. Suppose the player chooses to play 'p' moves continuously. Then, at the end of the game, the sequence on the right paper will again be 2, 3, 2, 1, 0. Therefore, the player does not win, as the pair of numbers 2 are not adjacent (a 3 intervenes).

In contrast, if the player chooses to play the following moves:

then at the end of the game both the 2s and the 3s are adjacent. Therefore, this sequence wins. However, it is not optimal: the sequence of moves 'pprppp' also wins and has a shorter length.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that reads several initial sequences of numbers and for each one prints the optimal sequence of moves.

Input Files:

The input file named pcr.in is a text file. The first line contains two integers T and N, separated by a space. The number T represents the number of sequences to follow, while the number N represents the number of numbers in each sequence. Each of the next T lines contains N numbers separated in pairs by a space: the terms ~\mathbf{x_1, x_2, \ldots, x_N}~ of an initial sequence, where ~x_i \in~ {0, 1, 2, 3}.

Output Files:

The output file named pcr.out is a text file with the following structure. It contains exactly T lines, each one containing the optimal sequence of moves for the corresponding initial sequence from the input (see above). These strings will consist of the letters 'p', 'c', and 'r'.

Examples of input - output files:

STDIN (pcr.in)

6 5
1 3 1 0 2
1 1 3 0 2
0 3 3 0 3
2 1 1 3 2
1 0 3 0 1
1 1 3 1 3

STDOUT (pcr.out)

pprppp
ppppp
pcppcpp
pcpppp
ppcppp
pppcpp

Constraints:

• 1 ~\le~ T ~\le~ 20, 1 ~\le~ N ~\le~ 100.000
• T∙N ~\le~ 100.000
• For test cases with a total value of 50%, 1 ~\le~ Ν ~\le~ 100

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 2 sec.
Maximum available memory: 256 MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: pcr *)

for PASCAL coders

/* USER: username
LANG: C
TASK: pcr */

for C coders

/* USER: username
LANG: C++
TASK: pcr */

for C++ coders

/* USER: username
LANG: Java
TASK: pcr */

for Java coders

# USER: username
# LANG: Python
# TASK: pcr

for Python coders