問題文

高橋君は旅行先で、「すわっぷしまーす」という不思議な完全二分木を観光しました。

「すわっぷしまーす」は、高さが $N+1$ で葉の個数が $2^N$ の完全二分木です。そして、葉には左から順に $1, 2, 3, ..., 2^N$ と数が書かれています。

また、葉以外の頂点について、上から $i$ 段目 $(1 ≦ i ≦ N)$、左から $j$ 番目 $(1 ≦ j ≦ 2^{i-1})$ ならば位置 $2^{i-1} + (j-1)$ となるように位置というものを定義します。

さらに、${\\rm swap}(x)$ というものを定義します。これは、位置 $x$ となる頂点を求め、左右の部分木を入れ替えるという動作です。

「すわっぷしまーす」は、以下の $2$ 種類のクエリを処理できます。

タイプ1: $k(1 ≦ k ≦ 2^N)$ が与えられるので、左から $k$ 番目の葉に書かれた数を求める。

タイプ2: $a, b(1 ≦ a ≦ b ≦ 2^N - 1)$ が与えられるので、${\\rm swap}(a), {\\rm swap}(a+1), {\\rm swap}(a+2), ..., {\\rm swap}(b)$ と、この順番で実行する。

高橋君は、旅行から帰った後、自分でも「すわっぷしまーす」を作りたくなりました。しかしなかなか難しいので、あなたが代わりに作ることになりました。

具体的には、$N$ と、$Q$ 個のクエリが与えられるので、それを処理できるような「すわっぷしまーす」を作ってください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $t_1$ $a_1$ $b_1$ $t_2$ $a_2$ $b_2$ : $t_Q$ $a_Q$ $b_Q$

• $1$ 行目には整数 $N(1 ≦ N ≦ 17)$, $Q(1 ≦ Q ≦ 200,000)$ が空白区切りで与えられる。
• $2$ 行目から $Q$ 行には、クエリの内容が与えられる。そのうち $i$ 行目には、$3$ つの整数 $t_i$, $a_i$, $b_i$ が空白区切りで与えられる。
• $t_i = 1$ の時、タイプ1のクエリである。 $a_i$ が問題文中の $k$ を表し、$b_i$ は必ず $0$ である。
• $t_i = 2$ の時、タイプ2のクエリである。 $a_i$, $b_i$ はそれぞれ問題文中の $a$, $b$ を表す。

出力

タイプ1のクエリが来る度に、求めた値を出力する。出力する度に改行を入れる事。

入力例1

3 10
2 5 5
1 1 0
1 2 0
1 3 0
1 4 0
2 1 3
1 2 0
1 3 0
1 5 0
1 6 0

出力例1

1
2
4
3
8
5
4
3

このサンプルでは、2回タイプ2のクエリが来ます。

1回目のタイプ2のクエリの後は下図のようになっています。

2回目のタイプ2のクエリの後は下図のようになっています。