Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
N 人のプレイヤーとゲームマスターのあなたが帽子の色当てゲームをプレイします. プレイヤーは縦一列に並んでおり,前から順に 1 から N までの番号がつけられています.
各プレイヤーは赤または青の帽子をかぶっています.
この情報は文字列 S によって表され,S の i 文字目が R
ならばプレイヤー i は赤い帽子を,B
ならば青い帽子をかぶっています.
あなたは文字列 S を知っていますが,プレイヤーは知りません.
各プレイヤーは,自分の前にいるプレイヤー(つまりより番号の小さいプレイヤー)の帽子の色だけを見ることができます.
特に,自分の帽子の色は見えません.
ゲームは次のように進行します.
まずあなたが,赤い帽子をかぶっているプレイヤーの人数と,青い帽子をかぶっているプレイヤーの人数を数え,それを全プレイヤーに伝えます. その後,以下の一連の流れ(ラウンドと呼ぶ)を 10^{100} 回繰り返します.
- あなたが各プレイヤーに「自分の帽子の色が分かりますか?」と質問する.
それに対しプレイヤーは,他のプレイヤーに聞こえないように正直に
Yes
またはNo
で返答する. - すべてのプレイヤーへ質問し終えたら,
Yes
と答えたプレイヤーを全員発表する. この発表は全プレイヤーが聞くことができる. ただし,発表するのはあくまでプレイヤーの番号であり,その帽子の色は伝えないことに注意せよ.
すべてのプレイヤーはとても賢く,また他のプレイヤーも同様に賢いということを知っています.
彼らは自分の帽子の色が確定した最初のラウンドからあなたの質問に Yes
と返答します.
また,他のプレイヤーがそのような戦術をとっていることを知った上で,自分の帽子の色を推理します.
各プレイヤーについて,すべてのラウンドが終了した時点で自分の帽子の色が分かっているか否かを求めてください.
1 つの入力ファイルにつき,T 個のテストケースに答えて下さい.
制約
- 1 \leq T \leq 100
- 1 \leq N \leq 100
- S は
R
とB
からなる長さ 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 です」と発表する.
- プレイヤー 1: あなたの質問に
- ラウンド 2:
- プレイヤー 1: 自分の帽子の色が青だったと仮定する.すると,ラウンド 1 でプレイヤー 2 は自身の帽子の色が赤だと気づいたはずである.しかし実際にはプレイヤー 2 は
No
と返答している. よって自分の帽子の色は赤だとわかる. あなたの質問にYes
と返答する. - プレイヤー 2: あなたの質問に
No
と返答する. - プレイヤー 3: あなたの質問に
Yes
と返答する. - あなたが「
Yes
と答えたのはプレイヤー 1,3 です」と発表する.
- プレイヤー 1: 自分の帽子の色が青だったと仮定する.すると,ラウンド 1 でプレイヤー 2 は自身の帽子の色が赤だと気づいたはずである.しかし実際にはプレイヤー 2 は
- ラウンド 3:
- プレイヤー 1: あなたの質問に
Yes
と返答する. - プレイヤー 2: あなたの質問に
No
と返答する. - プレイヤー 3: あなたの質問に
Yes
と返答する. - あなたが「
Yes
と答えたのはプレイヤー 1,3 です」と発表する.
- プレイヤー 1: あなたの質問に
- \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
orNo
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
andB
. - 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
."
- Player 1: answers
- 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 answersYes
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
."
- 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
- 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
."
- Player 1: answers
- \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.
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
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
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
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 である。
一般に 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.
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