题目描述

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:

• The $1$-bit Gray code consists of the two binary numbers $0$ and $1$. That is, $G_1=[0,1]$.
• 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 $\textbf{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:

• 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<2^{k_i}$, then set $a_j=G_{k_i,a_j}$; otherwise, do nothing to $a_j$.
• Given $p$, query the value of $a_p$.

Please output the results of each query in order.

输入格式

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 $\textbf{binary form}$ of an integer $p$ ($0\le p< 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 the $\textbf{binary forms}$ of all the results of the type-2 operations without leading zeros, each on its own line.

3 4
2 0
1 4 1 2 3 2
2 100
2 10

0
110
11

提示

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]$.