A - Many Formulae

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

この数列の隣接する 2 項の間に + または - を入れて，一つの式を作ることを考えます．

• -2 回以上連続で登場しない．

### 制約

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

### 入力

N
A_1 A_2 \cdots A_N


### 入力例 1

3
3 1 5


### 出力例 1

15


• 3+1+5=9

• 3+1-5=-1

• 3-1+5=7

3-1-5-2 回以上連続で登場するため，良い式ではありません． よって，答えは 9+(-1)+7=15 となります．

### 入力例 2

4
1 1 1 1


### 出力例 2

10


• 1+1+1+1=4

• 1+1+1-1=2

• 1+1-1+1=2

• 1-1+1+1=2

• 1-1+1-1=0

よって答えは 4+2+2+2+0=10 となります．

### 入力例 3

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117


### 出力例 3

279919144


Score : 400 points

### Problem Statement

You are given a sequence of N non-negative integers: A_1,A_2,\cdots,A_N.

Consider inserting a + or - between each pair of adjacent terms to make one formula.

There are 2^{N-1} such ways to make a formula. Such a formula is called good when the following condition is satisfied:

• - does not occur twice or more in a row.

Find the sum of the evaluations of all good formulae. We can prove that this sum is always a non-negative integer, so print it modulo (10^9+7).

### Constraints

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

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N


### Output

Print the sum modulo (10^9+7).

### Sample Input 1

3
3 1 5


### Sample Output 1

15


We have the following three good formulae:

• 3+1+5=9

• 3+1-5=-1

• 3-1+5=7

Note that 3-1-5 is not good since- occurs twice in a row in it. Thus, the answer is 9+(-1)+7=15.

### Sample Input 2

4
1 1 1 1


### Sample Output 2

10


We have the following five good formulae:

• 1+1+1+1=4

• 1+1+1-1=2

• 1+1-1+1=2

• 1-1+1+1=2

• 1-1+1-1=0

### Sample Input 3

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117


### Sample Output 3

279919144


Print the sum modulo (10^9+7).

B - Insurance

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

すぬけくんは明日の運勢を占いました． その結果，N 個のシナリオのうちどれか一つが等確率で発生し，そのうち i 番目のシナリオでは A_i 円を失うことを知りました．

そこですぬけくんは，今日保険に入ることにしました． 保険会社に x 円を支払ったとすると，A_i 円を失った場合には \min(A_i,2x) 円が補填されます． ここで，x として任意の非負実数を選ぶことができます．

すぬけくんは，最終的に自分が失う金額（=x+A_i-\min(A_i,2x)）の期待値を最小化したいです． この最小値を求めてください．

### 制約

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

### 入力

N
A_1 A_2 \cdots A_N


### 入力例 1

3
3 1 4


### 出力例 1

1.83333333333333333333


x=1.5 とするのが最適です． 1.5 円支払ったあと，以下の 3 つのシナリオが等確率で起こります．

• シナリオ 1: 3 円失ったあと，\min(3,2x)=3 円が補填される． 最終的にすぬけくんが失う金額は，x+A_1-\min(A_1,2x)=1.5+3-3=1.5 円である．

• シナリオ 2: 1 円失ったあと，\min(1,2x)=1 円が補填される． 最終的にすぬけくんが失う金額は，x+A_2-\min(A_2,2x)=1.5+1-1=1.5 円である．

• シナリオ 3: 4 円失ったあと，\min(4,2x)=3 円が補填される． 最終的にすぬけくんが失う金額は，x+A_3-\min(A_3,2x)=1.5+4-3=2.5 円である．

よって，失う金額の期待値は，(1.5+1.5+2.5)/3=1.833333\cdots です．

### 入力例 2

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117


### 出力例 2

362925658.10000000000000000000


Score : 500 points

### Problem Statement

Snuke has read his own fortune for tomorrow, and learned that there are N scenarios that can happen, one of which will happen tomorrow with equal probability. The i-th scenario will cost him A_i yen (Japanese currency).

Following this, Snuke has decided to get insurance today. If he pays x yen to his insurance company, he will get compensation of \min(A_i,2x) yen when A_i yen is lost. Here, he can choose any non-negative real number as x.

Snuke wants to minimize the expected value of the amount of money he loses, which is x+A_i-\min(A_i,2x). Find the minimized value.

### Constraints

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

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N


### Output

Print the answer. Your answer will be judged correct when its absolute or relative error is at most 10^{-6}.

### Sample Input 1

3
3 1 4


### Sample Output 1

1.83333333333333333333


The optimum choice is x=1.5. After paying 1.5 yen, one of the following three scenarios will happen with equal probability:

• Scenario 1: Lose 3 yen and get compensation of \min(3,2x)=3 yen. After all, Snuke loses x+A_1-\min(A_1,2x)=1.5+3-3=1.5 yen.

• Scenario 2: Lose 1 yen and get compensation of \min(1,2x)=1 yen. After all, Snuke loses x+A_2-\min(A_2,2x)=1.5+1-1=1.5 yen.

• Scenario 3: Lose 4 yen and get compensation of \min(4,2x)=3 yen. After all, Snuke loses x+A_3-\min(A_3,2x)=1.5+4-3=2.5 yen.

Thus, the expected amount of money lost is (1.5+1.5+2.5)/3=1.833333\cdots yen.

### Sample Input 2

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117


### Sample Output 2

362925658.10000000000000000000

C - Calculator

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

すぬけくんは整数 x,y を持っています． 最初 x=0,y=0 です．

すぬけくんは，以下の 4 つの操作を好きな順で好きな回数行なえます．

• 操作 1: x の値を x+1 で置き換える

• 操作 2: y の値を y+1 で置き換える

• 操作 3: x の値を x+y で置き換える

• 操作 4: y の値を x+y で置き換える

130 回以内の操作で，x の値を N にしてください． このとき，y にはどんな値が入っていても構いません． この問題の制約下で，このような操作列が存在することは証明できます．

### 制約

• 1 \leq N \leq 10^{18}
• 入力される値はすべて整数である

### 入力

N


### 出力

K
t_1
t_2
\vdots
t_K


ここで，K (0 \leq K \leq 130) は操作回数を表し，t_i (1 \leq t_i \leq 4)i 番目に行う操作を表す整数である．

### 入力例 1

4


### 出力例 1

5
1
4
2
3
1


(x,y) の値は， (0,0)\rightarrow (操作 1) \rightarrow (1,0) \rightarrow (操作 4) \rightarrow (1,1) \rightarrow (操作 2) \rightarrow (1,2) \rightarrow (操作 3) \rightarrow (3,2) \rightarrow (操作 1) \rightarrow (4,2) と変化し，最終的な x の値は N に一致しています．

Score : 600 points

### Problem Statement

Snuke has integers x and y. Initially, x=0,y=0.

Snuke can do the following four operations any number of times in any order:

• Operation 1: Replace the value of x with x+1.

• Operation 2: Replace the value of y with y+1.

• Operation 3: Replace the value of x with x+y.

• Operation 4: Replace the value of y with x+y.

You are given a positive integer N. Do at most 130 operations so that x will have the value N. Here, y can have any value. We can prove that such a sequence of operations exists under the constraints of this problem.

### Constraints

• 1 \leq N \leq 10^{18}
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N


### Output

K
t_1
t_2
\vdots
t_K


Here, K (0 \leq K \leq 130) denotes the number of operations, and t_i(1 \leq t_i \leq 4) represents the i-th operation to be done.

### Sample Input 1

4


### Sample Output 1

5
1
4
2
3
1


Here, the values of x and y change as follows: (0,0)\rightarrow (Operation 1) \rightarrow (1,0) \rightarrow (Operation 4) \rightarrow (1,1) \rightarrow (Operation 2) \rightarrow (1,2) \rightarrow (Operation 3) \rightarrow (3,2) \rightarrow (Operation 1) \rightarrow (4,2), and the final value of x matches N.

D - XOR Game

Time Limit: 4 sec / Memory Limit: 1024 MB

### 問題文

Alice と Bob がゲームをします． ゲームは N ラウンドにわたって行われ，各ラウンドでは以下の操作を行います．

• まず，Alice が黒板に書かれている整数を一つ選び，消す． ここで選ばれた整数を x とする．

• 次に，Bob が黒板に書かれている整数を一つ選び，消す． ここで選ばれた整数を y とする．

• x \oplus y の値をノートに記録する．ただしここで \oplus はビットごとの排他的論理和を表す．

### 制約

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i < 2^{30}
• 入力される値はすべて整数である

### 入力

N
A_1 A_2 \cdots A_{2N}


### 入力例 1

2
0 1 3 5


### 出力例 1

4


• ラウンド 1:

• Alice が A_1=0 を選択する．
• Bob が A_3=3 を選択する．
• ノートに 0 \oplus 3=3 が記録される．
• ラウンド 2:

• Alice が A_4=5 を選択する．
• Bob が A_2=1 を選択する．
• ノートに 5 \oplus 1=4 が記録される．
• ゲームのスコアが \max(3,4)=4 になる．

### 入力例 2

2
0 0 0 0


### 出力例 2

0


### 入力例 3

10
974654030 99760550 750234695 255777344 907989127 917878091 818948631 690392797 579845317 549202360 511962375 203530861 491981716 64663831 561104719 541423175 301832976 252317904 471905694 350223945


### 出力例 3

268507123


Score : 700 points

### Problem Statement

There are 2N integers written on a blackboard. The i-th integer is A_i.

Alice and Bob will play a game consisting of N rounds. In each round, they do the following:

• First, Alice chooses an integer on the blackboard and erases it. Let x be the integer erased here.
• Second, Bob chooses an integer on the blackboard and erases it. Let y be the integer erased here.
• Finally, write the value x \oplus y on a notebook, where \oplus denotes the bitwise XOR.

In the end, all the integers on the blackboard will be erased, and the notebook will have N integers written on it. The greatest integer written on the notebook will be the score of the game. Alice wants to maximize this score, while Bob wants to minimize it. Find the score of the game when both players play optimally under their objectives.

### Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i < 2^{30}
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_{2N}


### Sample Input 1

2
0 1 3 5


### Sample Output 1

4


Below is one possible progress of the game (it may contain suboptimal choices).

• Round 1:

• Alice chooses A_1=0.
• Bob chooses A_3=3.
• They write 0 \oplus 3=3 on the notebook.
• Round 2:

• Alice chooses A_4=5.
• Bob chooses A_2=1.
• They write 5 \oplus 1=4 on the notebook.
• The score of the game is \max(3,4)=4.

### Sample Input 2

2
0 0 0 0


### Sample Output 2

0


### Sample Input 3

10
974654030 99760550 750234695 255777344 907989127 917878091 818948631 690392797 579845317 549202360 511962375 203530861 491981716 64663831 561104719 541423175 301832976 252317904 471905694 350223945


### Sample Output 3

268507123

E - Increasing LCMs

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• y_i=\operatorname{LCM}(x_1,x_2,\cdots,x_i) と定義する．ここで，\operatorname{LCM} は与えられた整数たちの最小公倍数を返す関数である．このとき，y は狭義単調増加である．つまり，y_1<y_2<\cdots<y_N が成り立つ．

### 制約

• 1 \leq N \leq 100
• 2 \leq A_1 < A_2 \cdots < A_N \leq 10^{18}
• 入力される値はすべて整数である

### 入力

N
A_1 A_2 \cdots A_N


### 出力

Yes
x_1 x_2 \cdots x_N


### 入力例 1

3
3 4 6


### 出力例 1

Yes
3 6 4


x=(3,6,4) のとき，

• y_1=\operatorname{LCM}(3)=3
• y_2=\operatorname{LCM}(3,6)=6
• y_3=\operatorname{LCM}(3,6,4)=12

となり，y_1<y_2<y_3 を満たします．

### 入力例 2

3
2 3 6


### 出力例 2

No


どのように A を並び替えても条件を満たすことができません．

### 入力例 3

10
922513 346046618969 3247317977078471 4638516664311857 18332844097865861 81706734998806133 116282391418772039 134115264093375553 156087536381939527 255595307440611247


### 出力例 3

Yes
922513 346046618969 116282391418772039 81706734998806133 255595307440611247 156087536381939527 134115264093375553 18332844097865861 3247317977078471 4638516664311857


Score : 800 points

### Problem Statement

We have a sequence of N positive integers: A_1,A_2,\cdots,A_N. You are to rearrange these integers into another sequence x_1,x_2,\cdots,x_N, where x must satisfy the following condition:

• Let us define y_i=\operatorname{LCM}(x_1,x_2,\cdots,x_i), where the function \operatorname{LCM} returns the least common multiple of the given integers. Then, y is strictly increasing. In other words, y_1<y_2<\cdots<y_N holds.

Determine whether it is possible to form a sequence x satisfying the condition, and show one such sequence if it is possible.

### Constraints

• 1 \leq N \leq 100
• 2 \leq A_1 < A_2 \cdots < A_N \leq 10^{18}
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N


### Output

If it is possible to form a sequence x satisfying the condition, print your answer in the following format:

Yes
x_1 x_2 \cdots x_N


If it is impossible, print No.

### Sample Input 1

3
3 4 6


### Sample Output 1

Yes
3 6 4


For x=(3,6,4), we have:

• y_1=\operatorname{LCM}(3)=3
• y_2=\operatorname{LCM}(3,6)=6
• y_3=\operatorname{LCM}(3,6,4)=12

Here, y_1<y_2<y_3 holds.

### Sample Input 2

3
2 3 6


### Sample Output 2

No


No permutation of A would satisfy the condition.

### Sample Input 3

10
922513 346046618969 3247317977078471 4638516664311857 18332844097865861 81706734998806133 116282391418772039 134115264093375553 156087536381939527 255595307440611247


### Sample Output 3

Yes
922513 346046618969 116282391418772039 81706734998806133 255595307440611247 156087536381939527 134115264093375553 18332844097865861 3247317977078471 4638516664311857

F - Domination

Time Limit: 7 sec / Memory Limit: 1024 MB

### 問題文

あなたは，青い石を一つ選んで好きな座標へ動かす，という操作を何度でも行えます． 座標 (x,y) にある青い石を座標 (x',y') へ動かす時，かかるコストは |x-x'|+|y-y'| です．

あなたの目標は，以下の条件が達成されることです．

• すべての 1 \leq i \leq N について，i 番目の赤い石の右上領域に，K 個以上の青い石が存在している． より厳密には，RX_i \leq BX'_j かつ RY_i \leq BY'_j を満たす 1 \leq j \leq M の個数が K 以上である． ただしここで，(BX'_j,BY'_j) は，j 番目の青い石の操作後の座標である．

### 制約

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq K \leq \min(M,10)
• 0 \leq RX_i,RY_i,BX_j,BY_j \leq 10^9
• 入力される値はすべて整数である

### 入力

N M K
RX_1 RY_1
RX_2 RY_2
\vdots
RX_N RY_N
BX_1 BY_1
BX_2 BY_2
\vdots
BX_M BY_M


### 入力例 1

3 2 1
0 0
2 0
0 2
1 0
0 1


### 出力例 1

2


• 1 番目の青い石を座標 (2,0) に動かす．コストが |1-2|+|0-0|=1 かかる．
• 2 番目の青い石を座標 (0,2) に動かす．コストが |0-0|+|1-2|=1 かかる．

### 入力例 2

3 2 2
0 0
2 0
0 2
1 0
0 1


### 出力例 2

6


• 1 番目の青い石を座標 (2,2) に動かす．コストが |1-2|+|0-2|=3 かかる．
• 2 番目の青い石を座標 (2,2) に動かす．コストが |0-2|+|1-2|=3 かかる．

### 入力例 3

10 10 3
985971569 9592031
934345597 151698665
212173157 492617927
623299445 288193327
381549360 462770084
681791249 242910920
569404932 353061961
357882677 463919940
110389433 533715995
9639432 700209424
771167518 75925290
439954587 566974581
738467799 122646638
267815107 900808287
886340750 70087431
434010239 822484872
388269208 879859813
393002209 874330449
154134229 924857472
667626345 460737380


### 出力例 3

1165266772


Score : 1200 points

### Problem Statement

There are N red stones and M blue stones on a two-dimensional plane. The i-th red stone is at coordinates (RX_i,RY_i), and the j-th blue stone is at (BX_j,BY_j). There may be multiple stones at the same coordinates.

You can choose a blue stone and move it to anywhere you like, any number of times. The cost of moving a blue stone from (x, y) to (x',y') is |x-x'|+|y-y'|.

You want to meet the following condition:

• For every 1 \leq i \leq N, there are K or more blue stones to the upper right of the i-th red stone. More formally, there are K or more indices 1 \leq j \leq M such that RX_i \leq BX'_j and RY_i \leq BY'_j, where (BX'_j,BY'_j) are the coordinates of the j-th blue stone after your operations.

Find the minimum total cost needed to achieve your objective.

### Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq K \leq \min(M,10)
• 0 \leq RX_i,RY_i,BX_j,BY_j \leq 10^9
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N M K
RX_1 RY_1
RX_2 RY_2
\vdots
RX_N RY_N
BX_1 BY_1
BX_2 BY_2
\vdots
BX_M BY_M


### Sample Input 1

3 2 1
0 0
2 0
0 2
1 0
0 1


### Sample Output 1

2


The optimal moves are as follows.

• Move the first blue stone to (2,0), for the cost of |1-2|+|0-0|=1.
• Move the second blue stone to (0,2), for the cost of |0-0|+|1-2|=1.

### Sample Input 2

3 2 2
0 0
2 0
0 2
1 0
0 1


### Sample Output 2

6


The optimal moves are as follows.

• Move the first blue stone to (2,2), for the cost of |1-2|+|0-2|=3.
• Move the second blue stone to (2,2), for the cost of |0-2|+|1-2|=3.

### Sample Input 3

10 10 3
985971569 9592031
934345597 151698665
212173157 492617927
623299445 288193327
381549360 462770084
681791249 242910920
569404932 353061961
357882677 463919940
110389433 533715995
9639432 700209424
771167518 75925290
439954587 566974581
738467799 122646638
267815107 900808287
886340750 70087431
434010239 822484872
388269208 879859813
393002209 874330449
154134229 924857472
667626345 460737380


### Sample Output 3

1165266772