A - Hat Puzzle

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000

問題文

N 人のプレイヤーとゲームマスターのあなたが帽子の色当てゲームをプレイします. プレイヤーは縦一列に並んでおり,前から順に 1 から N までの番号がつけられています.

各プレイヤーは赤または青の帽子をかぶっています. この情報は文字列 S によって表され,Si 文字目が R ならばプレイヤー i は赤い帽子を,B ならば青い帽子をかぶっています. あなたは文字列 S を知っていますが,プレイヤーは知りません. 各プレイヤーは,自分の前にいるプレイヤー(つまりより番号の小さいプレイヤー)の帽子の色だけを見ることができます. 特に,自分の帽子の色は見えません.

ゲームは次のように進行します.

まずあなたが,赤い帽子をかぶっているプレイヤーの人数と,青い帽子をかぶっているプレイヤーの人数を数え,それを全プレイヤーに伝えます. その後,以下の一連の流れ(ラウンドと呼ぶ)を 10^{100} 回繰り返します.

  • あなたが各プレイヤーに「自分の帽子の色が分かりますか?」と質問する. それに対しプレイヤーは,他のプレイヤーに聞こえないように正直に Yes または No で返答する.
  • すべてのプレイヤーへ質問し終えたら,Yes と答えたプレイヤーを全員発表する. この発表は全プレイヤーが聞くことができる. ただし,発表するのはあくまでプレイヤーの番号であり,その帽子の色は伝えないことに注意せよ.

すべてのプレイヤーはとても賢く,また他のプレイヤーも同様に賢いということを知っています. 彼らは自分の帽子の色が確定した最初のラウンドからあなたの質問に Yes と返答します. また,他のプレイヤーがそのような戦術をとっていることを知った上で,自分の帽子の色を推理します.

各プレイヤーについて,すべてのラウンドが終了した時点で自分の帽子の色が分かっているか否かを求めてください.

1 つの入力ファイルにつき,T 個のテストケースに答えて下さい.

制約

  • 1 \leq T \leq 100
  • 1 \leq N \leq 100
  • SRB からなる長さ N の文字列.
  • 入力される値はすべて整数.

入力

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

T
case_1
case_2
\vdots
case_T

各テストケース case_i は以下の形式である.

N
S

出力

各ケースについて,答えを長さ N の文字列として出力せよ. 出力する文字列の i 文字目は,すべてのラウンドが終了した時点でプレイヤー i が自分の帽子の色を知っているなら 1, そうでないなら 0 とせよ.


入力例 1

7
3
RBR
4
BRBR
5
BBBBB
5
BBBRR
20
BRBBRRRRBRRBRBBBRRBR
50
RRBRRRBBBRRRBBBRRBRRBBRBRRBBRRRRRBBBBBRRRBRBRRBRRR
100
BRBRBRBBRRRBBRRBRBBRBBBRBBRBBRRRRBBRRBBBBBBBBBBBBRRBBRBBRBBBBRRRRRRRRRBRBBRBBBBRBBBRBRRBRRBBRBBBBBBB

出力例 1

101
0101
11111
10111
10111111010101011101
11111010111010111010101010101011111111111011111111
1111111001111001111111010001111101011111111011011011111111111111111101111111111111010101011111111111

1 つめのケースでは,ゲームは以下のように進行します.

  • まずあなたが「赤い帽子をかぶっているプレイヤーは 2 人,青い帽子を被っているプレイヤーは 1 人です」と全プレイヤーに伝える.
  • ラウンド 1:
    • プレイヤー 1: あなたの質問に No と返答する.
    • プレイヤー 2: あなたの質問に No と返答する.
    • プレイヤー 3: 前にいるプレイヤーの帽子の色が赤と青なので,自分が赤い帽子をかぶっているとわかる. あなたの質問に Yes と返答する.
    • あなたが「Yes と答えたのはプレイヤー 3 です」と発表する.
  • ラウンド 2:
    • プレイヤー 1: 自分の帽子の色が青だったと仮定する.すると,ラウンド 1 でプレイヤー 2 は自身の帽子の色が赤だと気づいたはずである.しかし実際にはプレイヤー 2No と返答している. よって自分の帽子の色は赤だとわかる. あなたの質問に Yes と返答する.
    • プレイヤー 2: あなたの質問に No と返答する.
    • プレイヤー 3: あなたの質問に Yes と返答する.
    • あなたが「Yes と答えたのはプレイヤー 1,3 です」と発表する.
  • ラウンド 3:
    • プレイヤー 1: あなたの質問に Yes と返答する.
    • プレイヤー 2: あなたの質問に No と返答する.
    • プレイヤー 3: あなたの質問に Yes と返答する.
    • あなたが「Yes と答えたのはプレイヤー 1,3 です」と発表する.
  • \vdots

すべてのラウンドが終了した段階で,プレイヤー 1,3 は自分の帽子の色を知っています. しかしプレイヤー 2 はわからないままです. より詳しく言えば,プレイヤー 2 の持つ情報だけでは S=RRB である可能性と S=RBR である可能性がどちらも否定できないため,自分の帽子の色を確定させることができません. よって答えとして文字列 101 を出力します.

Score : 1000 points

Problem Statement

You, the game master, and N players play a Hat Guessing Game. The players line up behind one another, numbered 1 to N from front to back.

Each player wears a red or blue hat. The colors of the hats are represented by a string S: player i wears a red hat if the i-th character of S is R, and a blue hat if it is B. You know the string S, but the players do not. Each player can only see the colors of hats of the players in front of them (namely, the players with smaller player numbers). Particularly, they cannot see the color of their own hat.

The game goes as follows.

First, you count the numbers of players with red hats and those with blue hats, and tell them to all players. Then, you repeat the following sequence of events (called a round) 10^{100} times.

  • You ask each player, "Have you found out the color of your own hat?" Each player will honestly answer Yes or No without being heard by other players.
  • After asking all players, you announce all players who have answered Yes. All players can hear this announcement. Note that you just announce the player numbers and not the colors of their hats.

All players are extremely clever and know that the other players are also clever. They start answering Yes in the first round when the color of their hat is determined. Additionally, they know that the other players also take this strategy, and use this knowledge to infer the color of their hat.

For each player, find whether they will have found out the color of their own hat after all rounds.

Process T test cases for each input file.

Constraints

  • 1 \leq T \leq 100
  • 1 \leq N \leq 100
  • S is a string of length N consisting of R and B.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case case_i is in the following format:

N
S

Output

For each test case, print the answer as a string of length N. The i-th character of the string should be 1 if player i will have found out the color of their own hat after all rounds, and 0 otherwise.


Sample Input 1

7
3
RBR
4
BRBR
5
BBBBB
5
BBBRR
20
BRBBRRRRBRRBRBBBRRBR
50
RRBRRRBBBRRRBBBRRBRRBBRBRRBBRRRRRBBBBBRRRBRBRRBRRR
100
BRBRBRBBRRRBBRRBRBBRBBBRBBRBBRRRRBBRRBBBBBBBBBBBBRRBBRBBRBBBBRRRRRRRRRBRBBRBBBBRBBBRBRRBRRBBRBBBBBBB

Sample Output 1

101
0101
11111
10111
10111111010101011101
11111010111010111010101010101011111111111011111111
1111111001111001111111010001111101011111111011011011111111111111111101111111111111010101011111111111

In the first case, the game goes as follows.

  • First, you announce to all players, "Two players wear red hats, and one wears a blue hat."
  • Round 1:
    • Player 1: answers No to your question.
    • Player 2: answers No to your question.
    • Player 3: Because the hats of the players in front of him are red and blue, he realizes his hat is red. He answers Yes to your question.
    • You announce, "Player 3 answered Yes."
  • Round 2:
    • Player 1: Assume his hat is blue. Then, player 2 should have noticed in round 1 that his hat is red. However, player 2 actually answered No. Thus, he realizes his hat is red, and answers Yes to your question.
    • Player 2: answers No to your question.
    • Player 3: answers Yes to your question.
    • You announce, "Players 1 and 3 answered Yes."
  • Round 3:
    • Player 1: answers Yes to your question.
    • Player 2: answers No to your question.
    • Player 3: answers Yes to your question.
    • You announce, "Players 1 and 3 answered Yes."
  • \vdots

After all rounds, players 1 and 3 know the colors of their hats. However, player 2 does not. More specifically, player 2 can deny neither the possibility that S=RRB nor the possibility that S=RBR with just the information he has, so he cannot determine the color of his hat. Thus, the string 101 should be printed as the answer.

B - The Greatest Two

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1500

問題文

整数 N,K(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) が与えられます.

あなたは以下の操作を好きな回数 (0 回でもよい) 行うことができます.

  • 整数 i (1 \leq i \leq N-K+1) を選ぶ. P_i,P_{i+1},\cdots,P_{i+K-1} の中で 1 番目に大きい要素と 2 番目に大きい要素の値を入れ替える.

操作後の P としてあり得る順列の個数を 998244353 で割ったあまりを求めてください.

制約

  • 2 \leq K \leq N \leq 250000
  • (P_1,P_2,\cdots,P_N)(1,2,\cdots,N) の順列である.
  • 入力される値はすべて整数.

入力

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

N K
P_1 P_2 \cdots P_N

出力

答えを出力せよ.


入力例 1

3 3
2 3 1

出力例 1

2

この例では可能な操作は i=1 のみです.

1 回操作すると,P_1,P_2,P_3 の中で 1 番目に大きい要素 (=P_2=3)と 2 番目に大きい要素 (=P_1=2) の値が入れ替わり,P=(3,2,1) になります. さらにもう一度操作すると,P=(2,3,1) になります.

よって,操作後の順列としてあり得るのは P=(2,3,1),(3,2,1)2 つです.


入力例 2

3 2
1 3 2

出力例 2

6

入力例 3

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

出力例 3

144

入力例 4

20 5
8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9

出力例 4

1451520

Score : 1500 points

Problem Statement

You are given integers N and K, and a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).

You can perform the following operation any number of times, possibly zero.

  • Choose an integer i (1 \leq i \leq N-K+1). Swap the values of the two greatest elements among P_i,P_{i+1},\cdots,P_{i+K-1}.

Find the number, modulo 998244353, of permutations that P can be after your operations.

Constraints

  • 2 \leq K \leq N \leq 250000
  • (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
P_1 P_2 \cdots P_N

Output

Print the answer.


Sample Input 1

3 3
2 3 1

Sample Output 1

2

In this case, the operation can only be performed with i=1.

After one operation, the two greatest elements among P_1,P_2,P_3, which are P_2=3 and P_1=2, have their values swapped, and you have P=(3,2,1). After one more operation, you have P=(2,3,1).

Thus, there are two permutations, P=(2,3,1),(3,2,1), that P can be after your operations.


Sample Input 2

3 2
1 3 2

Sample Output 2

6

Sample Input 3

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

Sample Output 3

144

Sample Input 4

20 5
8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9

Sample Output 4

1451520
C - Jewel Pairs

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 2000

問題文

1 から N までの番号がついた N 個の宝石があります. 宝石 i の色は C_i で,その価値は V_i です. ここで,色は 1 以上 N 以下の整数で表されます.

2 つの宝石の組 (i,j) は以下の条件を両方満たすとき (そしてその時のみ),よい組と呼ばれます.

  • C_i \neq C_j
  • V_i + V_j \leq L

あなたは N 個の宝石からいくつかのよい組を作ろうとしています. 1 つの宝石が 2 個以上の組に含まれてはいけませんが,どの組にも含まれない宝石があっても構いません.

作った組に含まれるすべての宝石の価値の総和としてあり得る最大値を求めてください.

制約

  • 1 \leq N \leq 250000
  • 1 \leq L \leq 10^9
  • 1 \leq C_i \leq N
  • 0 \leq V_i \leq L
  • 入力される値はすべて整数.

入力

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

N L
C_1 V_1
C_2 V_2
\vdots
C_N V_N

出力

答えを出力せよ.


入力例 1

4 5
1 2
1 3
2 1
2 4

出力例 1

4

(1,2)1 番目の条件を満たさないのでよい組ではありません.

(1,4)2 番目の条件を満たさないのでよい組ではありません.

この入力例での最適な組の作り方は,組 (2,3) を作ることです.


入力例 2

5 10
3 8
4 2
1 5
1 3
1 2

出力例 2

17

この入力例での最適な組の作り方は,組 (1,5),(2,3) を作ることです.


入力例 3

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

出力例 3

34

入力例 4

20 1000000000
15 239276621
15 910500852
15 245532750
15 715892722
16 80707349
15 257261830
12 950300098
15 322288793
15 256358887
15 504976376
2 907119713
15 152036484
13 298766520
15 480968804
15 285187325
13 755031424
15 69837029
15 88860861
9 596982638
15 272961035

出力例 4

4704511147

Score : 2000 points

Problem Statement

There are N gems numbered 1 to N. Gem i has a color C_i and a value V_i. Here, colors are represented as integers from 1 through N.

A pair of two gems (i,j) is said to be a good pair if (and only if) they satisfy the following conditions:

  • C_i \neq C_j,
  • V_i + V_j \leq L.

You will make some number of good pairs from the N gems. A gem must not belong to multiple pairs, but it is fine if some gems belong to no pairs.

Find the maximum possible total value of all gems in your pairs.

Constraints

  • 1 \leq N \leq 250000
  • 1 \leq L \leq 10^9
  • 1 \leq C_i \leq N
  • 0 \leq V_i \leq L
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N L
C_1 V_1
C_2 V_2
\vdots
C_N V_N

Output

Print the answer.


Sample Input 1

4 5
1 2
1 3
2 1
2 4

Sample Output 1

4

The pair (1,2) is not good because the first condition is not satisfied.

The pair (1,4) is not good because the second condition is not satisfied.

In this case, it is optimal to make the pair (2,3).


Sample Input 2

5 10
3 8
4 2
1 5
1 3
1 2

Sample Output 2

17

In this case, it is optimal to make the pairs (1,5) and (2,3).


Sample Input 3

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

Sample Output 3

34

Sample Input 4

20 1000000000
15 239276621
15 910500852
15 245532750
15 715892722
16 80707349
15 257261830
12 950300098
15 322288793
15 256358887
15 504976376
2 907119713
15 152036484
13 298766520
15 480968804
15 285187325
13 755031424
15 69837029
15 88860861
9 596982638
15 272961035

Sample Output 4

4704511147
D - Cat Jumps

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 2000

問題文

正整数列 A_1,A_2,\cdots,A_N が与えられます. S=N+\sum_{1 \leq i \leq N}A_i と定義します.

猫のすぬけくんは S 枚のカードを持っています. 各カードには整数が書かれており,それらは A_1,A_2,\cdots,A_N,-1,\cdots,-1 です. 特に,-1 のカードは \sum_{1 \leq i \leq N}A_i 枚あります.

すぬけくんは今,数直線上の座標 0 の位置に立っています. すぬけくんはこれから S 回,以下の操作を行います.

  • 現在すぬけくんがいる座標を x とする. 持っているカードを 1 枚選んで捨てる. 捨てたカードに書いてあった数を v とするとき,座標 x+v へとジャンプする. ジャンプ後の座標が 0 なら,コインを 1 枚獲得する.

k=1,2,\cdots,N に対して,すぬけくんがちょうど k 枚のコインを獲得するようなジャンプの列が何通りあるかを 998244353 で割ったあまりを求めてください.

数えるのがジャンプの列であることに注意してください. つまり,2 つのカードに書いてある数が同じ場合,それらを捨てる操作は同一視します.

制約

  • 1 \leq N \leq 5000
  • 1 \leq A_i \leq 5000
  • 入力される値はすべて整数.

入力

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

N
A_1 A_2 \cdots A_N

出力

N 行出力せよ. i 行目には k=i に対する答えを出力せよ.


入力例 1

2
1 1

出力例 1

2
4

例えば,(-1,+1,+1,-1) というジャンプの列が考えられます. この場合,すぬけくんの座標は 0 \to -1 \to 0 \to 1 \to 0 と変化し,2 枚のコインを獲得します.

以下に,すべてのジャンプの列とその結果獲得するコインの枚数を示します.

  • (-1,-1,+1,+1): 1
  • (-1,+1,-1,+1): 2
  • (-1,+1,+1,-1): 2
  • (+1,-1,-1,+1): 2
  • (+1,-1,+1,-1): 2
  • (+1,+1,-1,-1): 1

入力例 2

3
1 2 3

出力例 2

140
220
144

入力例 3

20
16 6 15 19 1 9 6 1 11 7 6 12 3 11 11 18 10 9 15 5

出力例 3

507808441
401798892
110460932
680359166
737048635
442374434
737773176
980506765
473506608
693729211
532774651
621434128
4273369
839437048
585784927
590354055
969740008
825216624
442091194
660636013

Score : 2000 points

Problem Statement

You are given a sequence of positive integers A_1,A_2,\cdots,A_N. Let S=N+\sum_{1 \leq i \leq N}A_i.

Cat Snuke has S cards. Each card has an integer written on it. The integers on the cards are A_1,A_2,\cdots,A_N,-1,\cdots,-1. Particularly, there are \sum_{1 \leq i \leq N}A_i cards with -1.

Snuke is now standing at the coordinate 0 on a number line. He will perform the following operation S times.

  • Let x be the current coordinate of Snuke. Choose and discard one of the cards he has. Let v be the number on the discarded card, and jump to the coordinate x+v. If he has jumped to the coordinate 0, earn one coin.

For each k=1,2,\cdots,N, find the number, modulo 998244353, of sequences of moves for Snuke such that he earns exactly k coins.

Note that you should count sequences of moves. Namely, if two cards have the same number, discarding one of them is not distinguished from discarding the other.

Constraints

  • 1 \leq N \leq 5000
  • 1 \leq A_i \leq 5000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print N lines. The i-th line should contain the answer for k=i.


Sample Input 1

2
1 1

Sample Output 1

2
4

One possible sequence of moves is (-1,+1,+1,-1). Here, Snuke changes his coordinate as 0 \to -1 \to 0 \to 1 \to 0 and earns two coins.

Here are all possible sequences of moves and the number of coins that will be earned.

  • (-1,-1,+1,+1): one coin
  • (-1,+1,-1,+1): two coins
  • (-1,+1,+1,-1): two coins
  • (+1,-1,-1,+1): two coins
  • (+1,-1,+1,-1): two coins
  • (+1,+1,-1,-1): one coin

Sample Input 2

3
1 2 3

Sample Output 2

140
220
144

Sample Input 3

20
16 6 15 19 1 9 6 1 11 7 6 12 3 11 11 18 10 9 15 5

Sample Output 3

507808441
401798892
110460932
680359166
737048635
442374434
737773176
980506765
473506608
693729211
532774651
621434128
4273369
839437048
585784927
590354055
969740008
825216624
442091194
660636013
E - Adjacent Xor Game

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 2500

問題文

N 個の非負整数 A_1,A_2,\cdots,A_N が与えられます. 各 k=1,2,\cdots,N について,以下の問題を解いてください.

Alice と Bob が以下のようなゲームをします.

  • Alice が A_1,A_2,\cdots,A_N の中から k 個の数を選ぶ. 選んだ数を x_1,x_2,\cdots,x_k (順不同)とおく.

  • Bob が長さ 2k の非負整数列 y=(y_1,y_2,\cdots,y_{2k}) を作る. ここで,y は以下の条件を満たす必要がある.

    • 0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}
    • z_i=y_{2i-1} \oplus y_{2i} と定義する. このとき,\{z_1,z_2,\cdots,z_k\} は多重集合として \{x_1,x_2,\cdots,x_k\} と一致する.

なお,\oplus はビット単位 \mathrm{XOR} 演算を表します.

このゲームのスコアy_{2k} の値とします. Bob はスコアを最小化するように行動します. その上で Alice はスコアを最大化するように行動します. このとき,スコアはいくつになるでしょうか?

ビット単位 \mathrm{XOR} 演算とは

非負整数 A, B のビット単位 \mathrm{XOR}A \oplus B は、以下のように定義されます。

  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR}(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

  • 1 \leq N \leq 250000
  • 1 \leq A_i \leq 10^9
  • 入力される値はすべて整数.

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ.


入力例 1

3
1 2 3

出力例 1

2
6
6

k=1 の場合を考えます.

  • Alice が x_1=1 を選んだ場合: Bob は y=(0,1) を作り,スコアは 1 になります.
  • Alice が x_1=2 を選んだ場合: Bob は y=(0,2) を作り,スコアは 2 になります.
  • Alice が x_1=3 を選んだ場合: Bob は y=(1,2) を作り,スコアは 2 になります.

よって Alice は x_1=2 または x_1=3 を選び, スコアは 2 になります.

k=2 の場合を考えます. Alice が (x_1,x_2)=(2,3) を選び,Bob が y=(1,2,4,6) を作ると,スコアは 6 になります. これは両者の最適な行動の一例であり,求める答えは 6 です.

k=3 の場合を考えます. Alice が (x_1,x_2,x_3)=(1,2,3) を選び,Bob が y=(0,1,1,2,4,6) を作ると,スコアは 6 になります. これは両者の最適な行動の一例であり,求める答えは 6 です.


入力例 2

5
1 1 1 1 1

出力例 2

1
3
5
7
9

入力例 3

5
1 2 4 8 16

出力例 3

16
24
28
30
31

入力例 4

20
167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186

出力例 4

536870912
1610612736
2684354560
3758096384
4831838208
4831838208
4831838208
4831838208
4831838208
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664

Score : 2500 points

Problem Statement

You are given N non-negative integers A_1,A_2,\cdots,A_N. For each k=1,2,\cdots,N, solve the following problem.

Alice and Bob play the following game.

  • Alice chooses k numbers from A_1,A_2,\cdots,A_N. Let x_1,x_2,\cdots,x_k be the chosen numbers (in arbitrary order).

  • Bob makes a sequence of 2k non-negative integers y=(y_1,y_2,\cdots,y_{2k}), which must satisfy the following conditions.

    • 0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}.
    • Let z_i=y_{2i-1} \oplus y_{2i}. Then, \{z_1,z_2,\cdots,z_k\} coincides with \{x_1,x_2,\cdots,x_k\} as a multiset.

Here, \oplus denotes bitwise \mathrm{XOR}.

Let the score of the game be the value of y_{2k}. Bob plays to minimize the score. With this in mind, Alice plays to maximize the score. What will the score be?

What is bitwise \mathrm{XOR}?

The bitwise \mathrm{XOR} of non-negative integers A and B, A\ \mathrm{XOR}\ B, is defined as follows.

  • When A\ \mathrm{XOR}\ B is written in binary, the k-th lowest bit (k \geq 0) is 1 if exactly one of the k-th lowest bits of A and B is 1, and 0 otherwise.
For instance, 3\ \mathrm{XOR}\ 5 = 6 (in binary: 011\ \mathrm{XOR}\ 101 = 110).
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined to be (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k), which one can prove to be independent of the order of p_1, p_2, p_3, \dots p_k.

Constraints

  • 1 \leq N \leq 250000
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.


Sample Input 1

3
1 2 3

Sample Output 1

2
6
6

Consider the case k=1.

  • If Alice chooses x_1=1: Bob makes y=(0,1), for the score of 1.
  • If Alice chooses x_1=2: Bob makes y=(0,2), for the score of 2.
  • If Alice chooses x_1=3: Bob makes y=(1,2), for the score of 2.

Thus, Alice will choose x_1=2 or x_1=3, for the score of 2.

Consider the case k=2. If Alice chooses (x_1,x_2)=(2,3) and Bob makes y=(1,2,4,6), the score will be 6. This is an example of optimal play for both players, and the answer is 6.

Consider the case k=3. If Alice chooses (x_1,x_2,x_3)=(1,2,3) and Bob makes y=(0,1,1,2,4,6), the score will be 6. This is an example of optimal play for both players, and the answer is 6.


Sample Input 2

5
1 1 1 1 1

Sample Output 2

1
3
5
7
9

Sample Input 3

5
1 2 4 8 16

Sample Output 3

16
24
28
30
31

Sample Input 4

20
167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186

Sample Output 4

536870912
1610612736
2684354560
3758096384
4831838208
4831838208
4831838208
4831838208
4831838208
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664