Problem Statement

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

「すわっぷしまーす」は、高さが $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$ 個のクエリが与えられるので、それを処理できるような「すわっぷしまーす」を作ってください。

Input

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

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$ を表す。

Output

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