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.

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

Thus, the answer is 4+2+2+2+0=10.

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).

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.

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

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.

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.

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.

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

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.

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

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.

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