Communication System

After several incidents of miscommunication with his waiters, Takis installed a new electronic system in his pizzeria so that they could transmit orders from the serving area to the kitchen. The system allows waiters to send orders to Takis encoded as binary strings, that is, strings consisting of ~0~ and ~1~ (e.g. "~000110~").

Let ~p_1~, ~p_2~, ~...~, ~p_N~ be a sequence consisting of ~N~ positive integers. We will say that the sequence ~p~ is a pyramid if there exists a position ~k~ (with ~1 \le k \le N~) such that:

• ~p_i < p_{i+1}~, for every ~i~ with ~1 \le i < k~,
• ~p_i > p_{i+1}~, for every ~i~ with ~k \le i < N~.

In some strange way (which does not concern us), every order at the pizzeria is represented as a pyramid. Your task is to create a communication protocol between the waiters and Takis.

This is a "communication" problem. This means that your code will be executed twice for each test case:

• the first time (as the waiters), with the orders as input, in order to "encode" them into binary strings that can be sent through the system,
• the second time (as Takis), with the binary strings encoded during the first execution as input, in order to "decode" them and reconstruct the orders as pyramids.

Your code is considered correct for an order if the pyramid it prints during the second execution is identical to the one it received as input during the first execution, and it is considered correct for a test case if it is correct for all the orders it contains. Read the following carefully to understand how the input and output work, as well as how scoring is performed (it depends on the lengths of the binary strings you send through the system).

Problem

Write a program in C++ that reads the input data from the file commsystem.in and prints the results to the file commsystem.out.

Input Files (commsystem.in)

The first line contains an integer ~M~, which is either equal to ~1~ or equal to ~2~. The second line contains an integer ~T~: the number of orders.

If ~M = 1~, you take the role of the waiters. The next ~T~ orders follow, each consisting of two lines. The first line of each order contains an integer ~N~: the size of the corresponding pyramid. The second line of the order contains ~N~ integers ~p_1~, ~p_2~, ~...~, ~p_N~: the elements of the pyramid.

If ~M = 2~, you take the role of Takis. The next ~T~ messages follow, each consisting of one line containing a binary string. It is guaranteed that the binary strings were produced by running your program on some orders with ~M = 1~.

Output Files (commsystem.out)

If ~M = 1~, the output must contain ~T~ lines. For each order, the corresponding line must contain a non-empty binary string that encodes the corresponding input pyramid.

If ~M = 2~, the output must contain ~2 \cdot T~ lines. Each order must correspond to two lines: the first line must contain an integer, the size ~N~ of the pyramid represented by the binary string, and the second line must contain ~N~ integers, the elements of the pyramid.

Sample Input - Output Files:

First execution:

Input:

1
2
5
1 4 8 11 3
3
1 2 3

Output:

0011010
111

Second execution:

Input:

2
2
0011010
111

Output:

5
1 4 8 11 3
3
1 2 3

Explanation:

During its first execution, our program chooses to encode the pyramid ~[1,\;4,\;8,\;11,\;3]~ as the binary string "~0011010~" and ~[1,;2,;3]~ as "~111~". Note: This encoding is arbitrary; your program may choose any encoding format it wants.

During its second execution, our program receives as input the binary strings produced during the first execution and manages to decode them and reconstruct the original orders received by the waiters. Thus, our program is considered correct for this test case.

Constraints

• \(1 \\e T \le 100.000\)
• ~N \ge 1~
• ~1 \le p_i \le 12~
• Every given order is a pyramid.

Subtasks:

Let ~L_{max}~ be the maximum length of a binary string sent by your program during its first execution, considering all orders across all test cases of the given subtask.

1. (21 points) You must have ~L_{max} \le 92~.
2. (23 points) Either ~p_1 > _2~ or ~p_{N - 1} < p_N~, and you must have ~L_{max} \le 22~.
3. (27 points) You must have ~L_{max} \le 28~.
4. (29 points) You must have ~L_{max} \le 22~.

Notes:

• Formatting: In both the input and the output, each line ends with a newline character.
• Maximum execution time: ~1~ sec. for each of the two executions.
• Maximum available memory: ~16~ MB.

Warning: The answer may exceed ~2^{32}~ and, in general, you may need to perform operations with numbers larger than those that can be represented by the basic int type. Also, make sure to read the input and print the output efficiently in problems that require it.