問題文

京都大学の周辺には立て看板が立てられています。

この立て看板が京都の伝統的な景観を破壊しているという噂を耳にしたあなたは、この噂が本当かどうか確かめることにしました。

大学周辺には 1 から N まで番号付けられた N 枚の立て看板があり、立て看板 i は面積が s_i、派手さが a_i となっています。

立て看板 i の景観破壊指数は s_i \times a_i で与えられます。

N 個の立て看板の景観破壊指数のうち最大の値を出力してください。

制約

• 1 \leq N \leq 100
• 1 \leq s_i \leq 100 (1 \leq i \leq N)
• 1 \leq a_i \leq 100 (1 \leq i \leq N)
• 入力は全て整数である。

入力例1

3
3 2 1
3 3 4

出力例1

9

各立て看板の景観破壊指数は 9, 6, 4 であり、このうち最大のものは 9 です。

入力例2

1
1
1

出力例2

1

問題文

あなたはとある弾幕ゲームで遊んでいます。

あなたの目的は、適切に自機を操作することで一度も被弾しないことです。

この弾幕ゲームのマップは H 行 W 列のマス目で表現されています。

あなたにはゲーム開始時点でのマップの状態が与えられます。

i 行 j 列目のマスには文字 c_{ij} が書かれており、c_{ij} は以下のいずれかです。

• . の場合：何もないマス。
• x の場合：弾を表すマス。
• s の場合：自機を表すマス。マップの一番下の行にただ 1 つだけ存在する。

自機および弾の移動は、ゲーム開始から t (1 \leq t \leq H - 1) 秒後に同時かつ瞬時に行われます。移動後に自機と弾が同じマスに存在する場合は、被弾となります。

それぞれの弾は、移動ごとに 1 つ下のマスへ移動します。そして一度マップ外に出た弾は消滅し、以降ゲームに現れることはありません。

自機の移動は、あらかじめ命令列を出力することによって行います。

命令列は H - 1 文字からなる文字列で、i 文字目はゲーム開始から i 秒後の自機の移動を表します。このとき、各文字は以下のいずれかでなければなりません。

• L：左に 1 マス移動する。
• R：右に 1 マス移動する。
• S：そのマスにとどまる。

ただし、ゲームの途中で自機が画面外に出るような命令列は与えることができません。

目的を達成できる命令列が存在するならば、そのうちの 1 つを出力してください。存在しないならば、impossible を出力してください。

制約

• 2 \leq H, W \leq 10
• c_{ij} は ., x, s のいずれかである。
• 自機は必ず一番下の行のマスのいずれかにただ 1 つ存在する。

入力例1

4 3
xx.
...
.xx
.s.

出力例1

LRR

この命令列に従って自機を移動させると、以下のようになります。

xx.        ...        ...        ...
...   L    xx.   R    ...   R    ...
.xx  --->  ...  --->  xx.  --->  ...
.s.        sxx        .s.        xxs

この入力では、LRR が唯一達成可能な命令列となります。

入力例2

3 3
xxx
...
.s.

出力例2

impossible

入力例3

6 4
x.xx
.xxx
x.xx
xx.x
xx.x
.s..

出力例3

RSLLR

問題文

9 \times 9 のマス目があり、最初マス目は全て白で塗られています。

あなたはできるだけ少ないマスを黒で塗りつぶし、白いマスが 縦、横、斜めのいずれにも 7 マス連続して並ばないようにしたいです。

そのような塗りつぶし方の中から 1 つを出力してください。

問題文

ある日、京都大学の地下の調査によって、今は失われし古の超技術が使われた競プロ装置が発掘されました。

この装置に、一つの正整数が答えである競技プログラミングの問題と正整数 q を入力するとその競技プログラミングの問題の答えを q で割った余りが出力されます。

ただし、この装置の出力は古の文字で書かれているため、出力が偶数か奇数かしか判別することができません。

あなたはこの装置を使って、答えが １\leq X \leq 10^9 を満たす正整数 X であり、長年誰にも解かれていない競技プログラミングの問題を解くことにしました。

ただし、この装置を使う度に京都大学に膨大な使用料を払う必要があり、使える資金に余裕がないため装置の使用回数は 30 回以下にして、 X を求めてください。

入出力

この問題では最初に与えられる入力は無い。

解答プログラムは次の形式の出力をすることで競プロ装置を利用できる。

? q

ここで q は 1 \leq q \leq 10^9 を満たす正整数で競プロ装置に入力される。末尾には改行を出力せよ。

次に、競プロ装置の出力を表す文字列が以下の形式で与えられる。

r

r は even または odd である。意味は次のとおりである。

• even のとき、 X を q で割った余りは偶数である。
• odd のとき、 X を q で割った余りは奇数である。

上記の競プロ装置の利用回数の上限は 30 回である。 30 回を超えて ? q の形式の出力をした場合は Query Limit Exceeded となる。

何回か競プロ装置を利用した後、あなたは問題の解 X を当てる。あなたが問題の解であると思う値を answer とすると、

! answer

というフォーマットで出力する。末尾には改行を出力せよ。解を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。

また、これら以外のフォーマットで出力した場合のジャッジ結果も不定である。

各出力の後には、出力をフラッシュする必要があることに注意せよ。例えば C/C++ では競プロ装置の利用の際 q を

printf("? %d\n", q); fflush(stdout);

と出力すればよい。

制約

• 1 \leq X \leq 10^9
• 1 \leq q \leq 10^9
• X, q は整数
• 競プロ装置の利用は 30 回までしか行えない。

入出力例

X = 3 である場合に、以下のような入出力が考えられる。

これは入出力の一つの例であり、意味のある入出力をしているとは限らない。

問題文

長さ N の順列 P = p_1, p_2, ..., p_N が与えられます。長さ N の順列であって、P より辞書順で小さいか等しいもの全てについて転倒数を求め、その和を答えてください。ただし答えはとても大きくなることがあるので、10^9 + 7 で割った余りを出力してください。

ただし、順列 X = x_1, x_2, ..., x_N の転倒数とは、1 \leq i < j \leq N かつ x_i > x_j を満たす整数 i, j の組の個数のことです。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq p_i \leq N
• 入力は全て整数である。
• p_1, p_2, ..., p_N は順列である。

入力例1

3
2 1 3

出力例1

2

順列 (2, 1, 3) より辞書順で小さいか等しい、長さ 3 の順列は (1, 2, 3), (1, 3, 2), (2, 1, 3) の 3 種類です。

これらの順列の転倒数はそれぞれ 0, 1, 1 なので、答えは 0 + 1 + 1 = 2 となります。

入力例2

4
1 2 3 4

出力例2

0

入力例3

8
5 6 2 7 1 3 8 4

出力例3

281881

問題文

机の上に N 枚のカードがあり、それぞれ 1 から N まで番号付けられています。

これらのカードを用いて 2 人で以下のゲームを行います。

• 先手から交互にカードを 1 枚ずつ机の上から取ります。
• 机の上のカードが全て取られたらゲームは終了します。

その後、以下のルールに従ってスコア計算を行い、勝者を決定します。

• i (1 \leq i \leq N) 番目のカードを取ったプレイヤーがスコア s_i を得る。
• i = 1, 2, ..., M について、a_i 番目のカードと b_i 番目のカードをどちらも取ったプレイヤーがスコア c_i を得る。

その結果、合計スコアが大きいプレイヤーが勝者となり、合計スコアが同じ場合は後手が勝者となります。

勝者となるためにお互いが最適に行動したとき、どちらが勝者となるでしょうか。

制約

• 入力は全て整数である。
• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq a_i < b_i \leq N
• 1 \leq s_i, c_i \leq 10^9

入力例 1

4 4
1 20 30 10
1 2 40
1 3 30
1 4 50
2 3 100

出力例 1

First

• 先手は初めに 1 番目のカードを取ります。
• 次に、後手が 2 番目のカードを取った場合を考えます。
• このとき、先手は 3 番目のカードを取ります。
• すると、後手は 4 番目のカードを取るしかありません。

そのときの合計スコアは次のようになり、先手が勝者となります。

• 先手は 1 番目と 3 番目のカードを取ったので、先手の合計スコアは 1 + 30 + 30 = 61 です。
• 後手は 2 番目と 4 番目のカードを取ったので、後手の合計スコアは 20 + 10 = 30 です。

他の場合も先手が上手く取ることで、先手が勝者となります。

入力例 2

6 10
16 14 5 2 6 11
1 2 17
1 3 8
1 6 7
2 3 2
2 4 1
2 6 9
3 4 3
3 5 2
4 5 17
5 6 26

出力例 2

Second

入力例 3

10 9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000

出力例 3

Second

問題文

次を満たす N 要素の整数列 a_1, a_2, ..., a_N を構成してください。

• 0 \leq a_i \leq 10^{12}
• M 個の整数 c_1, c_2, ..., c_M について、a_{c_i} = 0
• b_i = Σ _{j | i} a_j としたとき、1 \leq i \leq N-1 を満たす各 i について、b_i < b_{i+1}

ここで j | i は、j が i を割り切ることを意味します。

制約

• 入力は全て整数である。
• 1 \leq N \leq 3 \times 10^5
• 1 \leq M \leq N
• 1 \leq c_i \leq N
• M 個の整数 c_1, c_2, ..., c_M は全て異なる。

入力例1

3 1
1

出力例1

Yes
0 1 2

この数列の各要素は非負整数なので、問題文の 1 つ目の条件を満たしています。
また a_1 = 0 なので、2 つ目の条件を満たしています。
さらに b_1 = a_1 = 0、b_2 = a_1 + a_2 = 1、b_3 = a_1 + a_3 = 2 であり、3 つ目の条件も満たしています。

入力例2

3 3
1 2 3

出力例2

No

この場合、a_1 = a_2 = a_3 = 0 である必要がありますが、このとき必ず b_1 = b_2 = b_3 = 0 となるため、3 つ目の条件を満たすことは不可能です。

問題文

トール君は、数列が大好きな男の子です。

トール君がいつものようにリビングで数列を愛でていると、テレビから「多様性」という言葉が聞こえてきました。

それを聞いたトール君は、自分が持っている数列にも多様性をもたせたいと思い、以下の条件をすべて満たすような N 要素の整数からなる数列 a_1, ..., a_N を作ることにしました。

• a_{l_i}, a_{l_i + 1}, ..., a_{r_i} の中に b_i とは異なる値が少なくとも1つ存在する。(1 \leq i \leq M)
• すべての要素の値は 1 以上 S 以下である。

トール君はこれらの条件を満たす数列が何通りあるかが気になりましたが、自力で数えるのは難しいことに気が付きました。

トール君の代わりに、あり得る数列の個数を求めてあげましょう。答えは非常に大きくなりうるので、10^9 + 7 で割ったあまりを出力してください。

制約

• 入力はすべて整数で与えられる。
• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq S \leq 10^5
• 1 \leq l_i \leq r_i \leq N
• 1 \leq b_i \leq S
• (l_i, r_i, b_i) の組はすべて異なる。

入力例1

3 2 2
1 2 1
2 3 2

出力例1

4

満たすべき条件は、以下の 3 つです。

• a_1, a_2 のうち少なくとも 1 つは 1 以外の整数である。
• a_2, a_3 のうち少なくとも 1 つは 2 以外の整数である。
• 数列の要素の値はすべて 1 以上 2 以下である。

これを満たす数列は、(1, 2, 1), (2, 1, 1), (2, 1, 2), (2, 2, 1) の 4 つ存在します。

入力例2

8 3 4
1 5 1
2 6 1
4 8 1

出力例2

65364

入力例3

7 6 4
1 5 1
3 6 3
2 2 4
5 7 4
4 7 2
2 2 3

出力例3

7984

入力例4

5 3 52657
1 2 1
4 5 1
1 5 1

出力例4

145394311

入力例5

8 10 3
1 5 1
6 8 2
2 6 2
3 7 1
8 8 3
1 3 3
4 8 1
5 6 3
3 7 2
1 8 2

出力例5

3439

問題文

左右一列に並んだ N 個のマスで表現されるフィールド上に M 体の敵が潜んでいます。

敵は幅を持っており、i 番目の敵は左から L_i, L_i+1, ..., R_i 番目のマスに潜んでいます。 これらのマスのうち 1 マス以上の情報を得ていると、スコア s_i を得ます。

はじめ、どのマスの情報も得ていません。

Q 個のクエリが順に与えられます。 j 番目のクエリは、t_j, l_j, r_j で表され、

• t_j = 0 のとき、左から l_j, l_j+1, ..., r_j 番目のマスの情報を失います。
• t_j = 1 のとき、左から l_j, l_j+1, ..., r_j 番目のマスの情報を得ます。

各クエリ処理後の合計スコアを求めてください。

制約

• 入力は全て整数である。
• 1 \leq N, M, Q \leq 10^5
• 1 \leq s_i \leq 10^9
• t_j は 0 または 1 である。
• 1 \leq L_i \leq R_i \leq N
• 1 \leq l_j \leq r_j \leq N

入力例 1

4 2
1 2 5
4 4 8
3
1 1 4
0 2 4
0 1 1

出力例 1

13
5
0

各クエリは以下のように進行します。

• 左から 1, 2, 3, 4 番目のマスの情報を得ます。
  • 左から 1 番目のマスの情報を得ているので、スコア 5 を得ます。
  • 左から 4 番目のマスの情報を得ているので、スコア 8 を得ます。
  • 合計スコアは 13 です。
• 左から 2, 3, 4 番目のマスの情報を失います。
  • この時点では 1 番目のマスの情報のみ得ているので、合計スコアは 5 です。
• 左から 1 番目のマスの情報を失います。
  • どのマスの情報も得ていないので、合計スコアは 0 です。

入力例 2

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

出力例 2

9
12
7
12
9

入力例 3

100 10
38 64 158260522
61 81 24979445
53 77 433933447
21 32 211047202
49 53 731963982
1 12 430302156
47 57 880895728
61 74 189330739
44 98 404539679
10 49 492686568
10
1 55 81
1 32 72
0 14 67
1 13 24
1 45 56
1 9 38
0 7 61
1 4 26
1 45 58
0 44 99

出力例 3

2091939560
3527637312
1052783310
1756517080
3527637312
3957939468
1052783310
2186819236
3957939468
1134035926

問題文

コインの山が N 個あります。

山には 1 から N までの番号が振られており、i 番目の山は a_i 枚のコインからなります。

これらのコインの山を使った以下のような 2 人ゲームを考えます。

• プレイヤーは先攻と後攻に分かれる。
• 先攻からスタートして、各プレイヤーに交互に手番が回る。手番では以下の 2 つの操作を順に実行する。
  1. K 以下の正整数 x を宣言する。
     ただし、互いに 2 回目以降の手番では、 直前の自分の手番で宣言した整数よりも小さい x を宣言してはいけない。
  2. x 枚以上のコインを含む山を 1 個選び、その山からコインを x 枚取り除く。
     そのような山が存在しない場合、ゲームはそこで終了し、もう一方のプレイヤーがゲームに勝つ。

ちなつさんとあかりさんはこのゲームを、ちなつさんが先攻、あかりさんが後攻で M 回繰り返すことにしました。

ただし 1 回のゲームが終了するごとに、そのゲームで取り除いたコインは元あった山に戻すものとします。

ところで、ちなつさんとあかりさんはお互い勝つために最適に行動するため、ゲーム開始時の各山のコインの枚数に変化がなければ、ゲームの勝敗は変わらず面白くありません。

そこで 2 人は、i (1 \leq i \leq M - 1) 回目のゲームが終わり、取り除いたコインを元の山に戻したあとに、b_i 番目の山のコインを c_i 枚増やすことにしました。

M 回それぞれのゲームで、ちなつさんとあかりさんのどちらが勝つかを判定してください。

制約

• 入力は全て整数である
• 1 \leq N \leq 10^5
• 1 \leq K \leq 10^9
• 1 \leq M \leq 10^5
• 1 \leq a_i \leq 10^9
• 1 \leq b_i \leq N
• 1 \leq c_i \leq 10^9

部分点

以下の追加制約を全て満たすデータセットに正解した場合は、30 点が与えられる。

• N = 1
• M = 1

追加制約のないデータセットに正解した場合は、上記とは別に 370 点が与えられる。

入力例 1

1 8 1
7

出力例 1

Chinatsu

先攻であるちなつさんは最初の手番で、唯一の山の全てのコインを取り除くことができます。
このとき次のあかりさんの手番で、あかりさんはどのような正整数を宣言しても、それ以上の枚数のコインを含む山を選ぶことができません。
従って、ちなつさんがゲームに勝利します。
この入力例は部分点の追加制約を満たしています。

入力例 2

1 1 1
2

出力例 2

Akari

お互い 1 だけを宣言することができます。
このとき最初のちなつさんの手番で、ちなつさんは山から 1 枚のコインを取り除きます。
そして、その次のあかりさんの手番で、あかりさんは最後の 1 枚のコインを取り除きます。
2 回目のちなつさんの手番で、ちなつさんは 1 枚以上のコインを含む山を選ぶことはできません。
従って、あかりさんがゲームに勝利します。
この入力例は部分点の追加制約を満たしています。

入力例 3

5 7 3
83795 19140 82706 34385 26675
2 74621
3 60951

出力例 3

Chinatsu
Akari
Chinatsu

問題文

N 個の光オーブと M 個の闇オーブがあります。

i 番目の光オーブのエネルギーは a_i で、i 番目の闇オーブのエネルギーは b_i です。

また、各 i \in \{1, 2, ..., N\}, j \in \{l_i, l_i+1, ..., r_i\} について、i 番目の光オーブと j 番目の闇オーブは結合されています。

あなたは、各オーブに 1 以上 K 以下の整数で表されるレベルを同時に設定します。

レベルを設定した直後に、自分のレベルよりも高いレベルのオーブとしか結合されていないオーブが全て消滅します。

残ったオーブのエネルギーの平均値の最大値を求めてください。

制約

• 入力は全て整数である。
• 1 \leq N, M \leq 3 \times 10^4
• 2 \leq K \leq 3 \times 10^4
• 1 \leq a_i, b_i \leq 10^5
• 1 \leq l_i \leq r_i \leq M
• どのオーブも1つ以上のオーブと結合されている。

部分点

• N, M, K \leq 300 を満たすデータセットに正解した場合は、30 点が与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 370 点が与えられる。

入力例 1

2 3 10
15 10
11 12 13
1 2
2 3

出力例 1

13.3333333333

例えば、次のように設定すれば、2 番目の光オーブと 1 番目の闇オーブが消滅し、残ったオーブのエネルギーの平均値は (15 + 12 + 13) / 3 = 13.3333... となり最大です。

• 光オーブのレベル: 10, 8
• 闇オーブのレベル: 7, 9, 9

入力例 2

1 1 2
10
20
1 1

出力例 2

20.0000000000

入力例 3

10 10 5
97925 72167 60717 63438 89200 6986 16104 76483 23620 9806
24712 38409 16480 2643 28121 51951 23492 4420 28197 28607
1 2
3 10
2 5
9 9
6 7
2 8
3 5
2 3
4 10
5 9

出力例 3

51672.4545454545

問題文

3 次元空間上に N 個の点があり、i 番目の点の座標は (x_i, y_i, z_i) です。

まず、あなたは長さが 1 の 3 次元ベクトル v を自由に選びます。

次に、原点を通り v に垂直な平面を F とします。

各 (x_i, y_i, z_i) から F への垂線の足を p_i とします。

平面 F 上で頂点 p_1, p_2, ..., p_N の凸包を作り、その面積を S とします。

面積 S の最大値を求め、さらに、S を最大にするようなベクトル v の選び方が何通りあるかを 10^9 + 7 で割り、その余りを求めてください。

制約

• 入力は全て整数である。
• 4 \leq N \leq 60
• 0 \leq x_i, y_i, z_i \leq 1,000
• 与えられる点の座標は全て異なる。
• 全ての点が同一面上に存在することはない。
• 面積が最大となるような v の選び方は高々有限通りである。

入力例 1

4
0 0 0
1 0 0
0 1 0
0 0 1

出力例 1

0.866025403784
2

v = (1 / \sqrt{3}, 1 / \sqrt{3}, 1 / \sqrt{3}) とすると、各頂点から F への垂線の足の凸包は一辺 \sqrt{2} の正三角形となり、このときの面積 \sqrt{3} / 2 が最大となります。

v = (-1 / \sqrt{3}, -1 / \sqrt{3}, -1 / \sqrt{3}) としたときも同様に、F 上の凸包の面積が \sqrt{3} / 2 となります。

この面積となる v の選び方は、これら 2 通りのみです。

入力例 2

4
0 0 0
0 1 1
1 0 1
1 1 0

出力例 2

1.000000000000
6

入力例 3

8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

出力例 3

1.732050807569
8

入力例 4

27
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

出力例 4

6.928203230276
8

入力例 5

24
2 3 4
2 4 3
3 2 4
3 4 2
4 2 3
4 3 2
2 1 4
2 4 1
1 2 4
1 4 2
4 2 1
4 1 2
2 3 0
2 0 3
3 2 0
3 0 2
0 2 3
0 3 2
2 1 0
2 0 1
1 2 0
1 0 2
0 2 1
0 1 2

出力例 5

14.282856857086
24

問題文

N 頂点からなる根付き木 T があり、頂点には 1 から N の番号がついています。はじめは頂点 1 が根です。

また、N-1 本の辺のうち、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

各頂点 v はそれぞれ整数の配列 A_v を持っています。はじめはすべて空です。

この根付き木 T に Q 回のクエリ操作を行います。クエリ操作は 3 種類あり、それぞれ以下の通りです。

• 1 v x k ― 頂点 v の部分木に含まれる任意の頂点（頂点 v を含む） u に対して、 A_u に値 x を k 個追加する。
• 2 v y z ― 頂点 v の配列 A_v に含まれる要素の中で、val xor y \leq z を満たす値 val の個数を求める。ここで、s xor t は s と t のビットごとの排他的論理和を指す。
• 3 v ― 根を頂点 v に変更する。

あなたは、このようなクエリを順番に処理するプログラムを書かなくてはなりません。

制約

• 入力は全て整数である。
• 1 \leq N \leq 1.4 \times 10^5
• 1 \leq Q \leq 1.4 \times 10^5
• 1 \leq a_i, b_i \leq N (1 \leq i \leq N-1)
• 1 \leq v \leq N
• 0 \leq x, y, z < 2^{30}
• 1 \leq k \leq 10^9
• 与えられるグラフは木である。

入力例 1

4
1 2
1 3
3 4
14
1 1 1 1
1 2 2 1
1 3 3 1
2 1 0 4
2 2 1 3
2 4 3 2
3 4
1 3 3 1
1 4 4 1
1 1 1 1
1 2 2 1
2 1 0 4
2 2 1 3
2 4 3 2

出力例 1

1
2
2
4
5
2

• 1 個目のクエリでは、A_1 と A_2 と A_3 と A_4 に値 1 を 1 つずつ追加します。
• 2 個目のクエリでは、A_2 に値 2 を 1 つ追加します。
• 3 個目のクエリでは、A_3 と A_4 に値 3 を 1 つずつ追加します。
• 4 個目のクエリでは、根を頂点 1 から頂点 4 に変更します。
• 5 個目のクエリでは、A_1 = \{1\} であり 1 xor 0 = 1 なので 4 以下の値の個数である 1 を出力します。
• 6 個目のクエリでは、A_2 = \{1,2\} であり 1 xor 1 = 0 、2 xor 1 = 3 なので 3 以下の値の個数である 2 を出力します。
• 7 個目のクエリでは、A_4 = \{1,3\} であり 1 xor 3 = 2 、3 xor 3 = 0 なので 2 以下の値の個数である 2 を出力します。
• 8 個目のクエリでは、A_1 と A_2 と A_3 に値 3 を 1 つずつ追加します。
• 9 個目のクエリでは、A_1 と A_2 と A_3 と A_4 に値 4 を 1 つずつ追加します。
• 10 個目のクエリでは、A_1 と A_2 に値 1 を 1 つずつ追加します。
• 11 個目のクエリでは、A_2 に値 2 を 1 つ追加します。
• 12 個目のクエリでは、A_1 = \{1,3,4,1\} であり 1 xor 0 = 1 、3 xor 0 = 3 、4 xor 0 = 4 、1 xor 0 = 1 なので 4 以下の値の個数である 4 を出力します。
• 13 個目のクエリでは、A_2 = \{1,2,3,4,1,2\} であり 1 xor 1 = 0 、2 xor 1 = 3 、3 xor 1 = 2 、4 xor 1 = 5 、1 xor 1 = 0 、2 xor 1 = 3 なので 3 以下の値の個数である 5 を出力します。
• 14 個目のクエリでは、A_4 = \{1,3,4\} であり 1 xor 3 = 2 、3 xor 3 = 0 、4 xor 3 = 7 なので 2 以下の値の個数である 2 を出力します。

入力例 2

1
11
1 1 4 1
1 1 14 2
1 1 10 4
1 1 8 8
1 1 12 16
1 1 2 32
1 1 6 64
1 1 0 128
2 1 0 10
2 1 10 10
2 1 8 10

出力例 2

237
190
190

入力例 3

1
11
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
1 1 0 1000000000
2 1 0 2

出力例 3

10000000000

出力は 32 ビット整数型に収まるとは限りません。

入力例 4

1
2
1 1 1 123
2 1 0 1073741823

出力例 4

123