G. Gray Transform (Weakened)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Gray code is a binary numeral system where two successive values differ in only one bit. This property makes it useful in various applications, such as minimizing errors in digital communication and measurement systems. Gray code is also known for its reflective and cyclic characteristics, which help eliminate significant errors during random sampling. It was invented by Frank Gray in the 1940s and has various construction methods.

An $$$n$$$-bit Gray code $$$G_n=[G_{n,0},G_{n,1},\cdots,G_{n,2^n-1}]$$$ can be generated by the following algorithm:

  1. The $$$1$$$-bit Gray code consists of the two binary numbers $$$0$$$ and $$$1$$$. That is, $$$G_1=[0,1]$$$.
  2. The first $$$2^n$$$ binary numbers of the $$$(n+1)$$$-bit Gray code are the same as the $$$n$$$-bit Gray code; the last $$$2^n$$$ binary strings of the $$$(n+1)$$$-bit Gray code are formed by taking the $$$n$$$-bit Gray code, arranging it in reverse order, and then adding $$$2^n$$$ to each number. That is, $$$G_{n+1}=[G_{n,0},G_{n,1},\cdots,G_{n,2^n-1},G_{n,2^n-1}+2^n,G_{n,2^n-2}+2^n,\cdots,G_{n,0}+2^n]$$$.

For example, $$$G_2=[0,1,3,2]$$$, $$$G_3=[0,1,3,2,6,7,5,4]$$$.

Now there is an array $$$a_0,a_1,\cdots,a_{2^n-1}$$$ of length $$$2^n$$$. Initially, for all $$$i\in\{0,1,\cdots,2^n-1\}$$$, $$$a_i=i$$$. We will perform $$$q$$$ operations on this array, where each operation is one of the following two types:

  1. Given $$$m$$$ and $$$k_1,k_2,\cdots,k_m$$$, for $$$i=1,2,\cdots,m$$$ in increasing order, for every $$$j\in\{0,1,\cdots,2^{k_i}-1\}$$$, if $$$a_j \lt 2^{k_i}$$$, then set $$$a_j=G_{k_i,a_j}$$$; otherwise, do nothing to $$$a_j$$$.
  2. Given $$$p$$$, query the value of $$$a_p$$$.

Please output the results of each query in order.

Input

The first line of input contains two integers, which are $$$n$$$ ($$$1\le n\le 10$$$) and $$$q$$$ ($$$1\le q\le 5000$$$).

The next $$$q$$$ lines describe the operations. Each of these lines starts with an integer $$$\text{op}$$$ ($$$\text{op}\in\{1,2\}$$$), indicating the type of operation.

  • If $$$\text{op}=1$$$, then the line is followed by an integer $$$m$$$ ($$$1\le m\le 2\times 10^6$$$) and $$$m$$$ integers $$$k_1,k_2,\cdots,k_m$$$ ($$$1\le k_i\le n$$$ for all $$$i\in\{1,2,\cdots,m\}$$$), representing a type-1 operation.
  • If $$$\text{op}=2$$$, then the line is followed by the binary form of an integer $$$p$$$ ($$$0\le p \lt 2^n$$$) without leading zeros, representing a type-2 operation with parameter $$$p$$$.

It is guaranteed that the sum of $$$m$$$ over all type-1 operations does not exceed $$$5000$$$.

Output

Output the binary forms of all the results of the type-2 operations without leading zeros, each on its own line.

Example
Input
3 4
2 0
1 4 1 2 3 2
2 100
2 10
Output
0
110
11
Note

Initially, $$$[a_0,a_1,\cdots,a_{2^n-1}]=[0,1,2,3,4,5,6,7]$$$.

After the second operation, $$$[a_0,a_1,\cdots,a_{2^n-1}]=[0,1,3,2,6,7,5,4]$$$.