AT_arc049_d [ARC049D] すわっぷしまーす

[problemUrl]: https://atcoder.jp/contests/arc049/tasks/arc049_d 高橋君は旅行先で、「すわっぷしまーす」という不思議な完全二分木を観光しました。 「すわっぷしまーす」は、高さが $ 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のクエリが来る度に、求めた値を出力する。出力する度に改行を入れる事。

### Sample Explanation 1 このサンプルでは、2回タイプ2のクエリが来ます。 1回目のタイプ2のクエリの後は下図のようになっています。 !\[D\_img0\](http://arc049.contest.atcoder.jp/img/arc/049/gj43jw3ejvertjreiogjofejrtejorjeoj/D\_img0.png) 2回目のタイプ2のクエリの後は下図のようになっています。 !\[D\_img1\](http://arc049.contest.atcoder.jp/img/arc/049/gj43jw3ejvertjreiogjofejrtejorjeoj/D\_img1.png)