/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は旅行先で、「すわっぷしまーす」という不思議な完全二分木を観光しました。
「すわっぷしまーす」は、高さが 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のクエリの後は下図のようになっています。
