Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

• Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i \leq N
• All values in input are integers.

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
• Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
• Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9

Problem Statement

Takahashi has N pairs of socks, and the i-th pair consists of two socks of color i. One day, after organizing his chest of drawers, Takahashi realized that he had lost one sock each of colors A_1, A_2, \dots, A_K, so he decided to use the remaining 2N-K socks to make \lfloor\frac{2N-K}{2}\rfloor new pairs of socks, each pair consisting of two socks. The weirdness of a pair of a sock of color i and a sock of color j is defined as |i-j|, and Takahashi wants to minimize the total weirdness.

Find the minimum possible total weirdness when making \lfloor\frac{2N-K}{2}\rfloor pairs from the remaining socks. Note that if 2N-K is odd, there will be one sock that is not included in any pair.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• 1\leq A_1 < A_2 < \dots < A_K \leq N
• All input values are integers.

Sample Input 1

4 2
1 3

Sample Output 1

2

Below, let (i,j) denote a pair of a sock of color i and a sock of color j.

There are 1, 2, 1, 2 socks of colors 1, 2, 3, 4, respectively. Creating the pairs (1,2),(2,3),(4,4) results in a total weirdness of |1-2|+|2-3|+|4-4|=2, which is the minimum.

Sample Input 2

5 1
2

Sample Output 2

0

The optimal solution is to make the pairs (1,1),(3,3),(4,4),(5,5) and leave one sock of color 2 as a surplus (not included in any pair).

Sample Input 3

8 5
1 2 4 7 8

Sample Output 3

2

Problem Statement

You are given a string S of length N consisting of 0 and 1. It is guaranteed that S contains at least one 1.

You may perform the following operation any number of times (possibly zero):

• Choose an integer i (1 \leq i \leq N-1) and swap the i-th and (i+1)-th characters of S.

Find the minimum number of operations needed so that all 1s are contiguous.

Here, all 1s are said to be contiguous if and only if there exist integers l and r (1 \leq l \leq r \leq N) such that the i-th character of S is 1 if and only if l \leq i \leq r, and 0 otherwise.

Constraints

• 2 \leq N \leq 5 \times 10^5
• N is an integer.
• S is a length N string of 0 and 1.
• S contains at least one 1.

Sample Input 1

7
0101001

Sample Output 1

3

For example, the following three operations make all 1s contiguous:

• Choose i=2 and swap the 2nd and 3rd characters. Then, S= 0011001.
• Choose i=6 and swap the 6th and 7th characters. Then, S= 0011010.
• Choose i=5 and swap the 5th and 6th characters. Then, S= 0011100.

It is impossible to do this in two or fewer swaps, so the answer is 3.

Sample Input 2

3
100

Sample Output 2

0

All 1s are already contiguous, so no swaps are needed.

Sample Input 3

10
0101001001

Sample Output 3

7

Problem Statement

An election is being held with N candidates numbered 1, 2, \ldots, N. There are K votes, some of which have been counted so far.

Up until now, candidate i has received A_i votes.

After all ballots are counted, candidate i (1 \leq i \leq N) will be elected if and only if the number of candidates who have received more votes than them is less than M. There may be multiple candidates elected.

For each candidate, find the minimum number of additional votes they need from the remaining ballots to guarantee their victory regardless of how the other candidates receive votes.

Formally, solve the following problem for each i = 1,2,\ldots,N.

Determine if there is a non-negative integer X not exceeding K - \displaystyle{\sum_{i=1}^{N}} A_i satisfying the following condition. If it exists, find the minimum possible such integer.

• If candidate i receives X additional votes, then candidate i will always be elected.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{12}
• 0 \leq A_i \leq 10^{12}
• \displaystyle{\sum_{i=1}^{N} A_i} \leq K
• All input values are integers.

Sample Input 1

5 2 16
3 1 4 1 5

Sample Output 1

2 -1 1 -1 0

14 votes have been counted so far, and 2 votes are left.
The C to output is (2, -1, 1, -1, 0). For example:

• Candidate 1 can secure their victory by obtaining 2 more votes, while not by obtaining 1 more vote. Thus, C_1 = 2.
• Candidate 2 can never (even if they obtain 2 more votes) secure their victory, so C_2 = -1.

Sample Input 2

12 1 570
81 62 17 5 5 86 15 7 79 26 6 28

Sample Output 2

79 89 111 117 117 74 112 116 80 107 117 106

Problem Statement

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

You and the judge will follow the procedure below. The procedure consists of phases 1 and 2; phase 1 is immediately followed by phase 2.

(Phase 1)

• The judge decides an integer N between 1 and 10^9 (inclusive), which is hidden.
• You print an integer M between 1 and 110 (inclusive).
• You also print an integer sequence A=(A_1,A_2,\ldots,A_M) of length M such that 1 \leq A_i \leq M for all i = 1, 2, \ldots, M.

(Phase 2)

• The judge gives you an integer sequence B=(B_1,B_2,\ldots,B_M) of length M. Here, B_i = f^N(i). f(i) is defined by f(i)=A_i for all integers i between 1 and M (inclusive), and f^N(i) is the integer resulting from replacing i with f(i) N times.
• Based on the given B, you identify the integer N that the judge has decided, and print N.

After the procedure above, terminate the program immediately to be judged correct.

Constraints

• N is an integer between 1 and 10^9 (inclusive).

Input and Output

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

(Phase 1)

• First, print an integer M between 1 and 110 (inclusive). It must be followed by a newline.

M

• Then, print a sequence A=(A_1,A_2,\ldots,A_M) of length M consisting of integers between 1 and M (inclusive), with spaces in between. It must be followed by a newline.

A_1 A_2 \ldots A_M

(Phase 2)

• First, an integer sequence B=(B_1,B_2,\ldots,B_M) of length M is given from the input.

B_1 B_2 \ldots B_M

• Find the integer N and print it. It must be followed by a newline.

N

If you print something illegal, the judge prints -1. In that case, your submission is already considered incorrect. Since the judge program terminates at this point, it is desirable that your program terminates too.

Notes

• After each output, add a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
• If an invalid output is printed during the interaction, or if the program terminates halfway, the verdict will be indeterminate.
• After you print the answer (or you receive -1), immediately terminate the program normally. Otherwise, the verdict will be indeterminate.
• Note that an excessive newline is also considered an invalid input.

Sample Interaction

The following is a sample interaction with N = 2.