Ana has $N$ pairs of natural numbers with values between $1$ and $10^9$. Additionally, no two pairs have the same first number. Therefore, we can think of Ana's pairs as members of a map (e.g., map<int,int> in C++). We call the first numbers in the pairs keys, and the second numbers values.

Ana wants to send the contents of her map to Borna, but the communication channel she uses has a limited number of bits! Therefore, Ana must devise a procedure to convert her map into a sequence of bits of a certain length, which she will then send to Borna over the communication channel.

Borna will receive the sent sequence of bits and attempt to reconstruct Ana's map from it. Although he may not know the contents of the entire map, he must be able to achieve the functionality of the map. More precisely, for every possible value $x$ that belongs to the set of keys, Borna must be able to return the corresponding value map[x] of that key in the map. To be sure that he has successfully reconstructed the map, Borna will ask for a key value $Q$ times.

Help Ana and Borna by writing a program that converts a given map into a sequence of bits and that can reconstruct the original map from the given sequence of bits.

Input

The first line contains a natural number $T$ ($T = 1$ or $T = 2$). If $T = 1$, the program must encode the given map into a sequence of bits. If $T = 2$, the program must reconstruct the original map from the given sequence of bits.

If $T = 1$, the next line contains a natural number $N$ ($1 \le N \le 100$), the number of pairs in Ana's map. Then, in the $i$-th of the next $N$ lines, there are natural numbers $x_i$ and $y_i$ ($1 \le x_i, y_i \le 10^9$) which represent the key and value of one pair in the map, respectively. It holds that $x_i \neq x_j$ for $i \neq j$.

If $T = 2$, the next line contains three natural numbers $N, Q$ and $K$ ($1 \le N, Q \le 100, 1 \le K \le 6000$), representing the number of pairs in the map, the number of queries Borna asks, and the number of received bits, respectively. The next line contains a sequence of characters '0' or '1' of length $K$, which represents the received sequence of bits. In the $i$-th of the next $Q$ lines, there is a natural number $x_i$. It is guaranteed that $x_i$ belongs to the set of possible keys of the original map.

Output

If $T = 1$, in the first line print a natural number $K$ ($1 \le K \le 6000$), the length of the encoded bit sequence. In the next line, print a sequence of characters '0' or '1', representing the values of the sent bits in order.

If $T = 2$, print $Q$ lines. In the $i$-th line, print the answer to the $i$-th query.

Subtasks

Your solution will be tested in two steps. First, it will be called with official input data where $T = 1$. If the output of your solution is a valid sequence of $K$ bits, in the second step your solution will be restarted with the sequence of bits printed in the first step. If the answers to the queries that your program prints in the second step are in accordance with the map from the official input data, it is considered that your program has successfully reconstructed the map.

If your program has not successfully reconstructed the map, it will be scored with 0 points. Otherwise, the number of points achieved depends on $K$ according to the following table:

The execution time of your solution is the sum of the execution times of both evaluation steps.

Examples

Input 1

1
3
2 10
3 3
5 7

Output 1

7
1100111

Input 2

2
3 2 7
1100111
5
3

Output 2

7
3