AtCoder Regular Contest 049

D - すわっぷしまーす


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

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

「すわっぷしまーす」は、高さが 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のクエリの後は下図のようになっています。

D_img0

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

D_img1


Submit提出する