Problem Statement

There are N people numbered 1 through N. Each person has a integer score called programming ability; person i's programming ability is P_i points. How many more points does person 1 need, so that person 1 becomes the strongest? In other words, what is the minimum non-negative integer x such that P_1 + x > P_i for all i \neq 1?

Constraints

• 1\leq N \leq 100
• 1\leq P_i \leq 100
• All input values are integers.

Sample Input 1

4
5 15 2 10

Sample Output 1

11

Person 1 becomes the strongest when their programming skill is 16 points or more, so the answer is 16-5=11.

Sample Input 2

4
15 5 2 10

Sample Output 2

0

Person 1 is already the strongest, so no more programming skill is needed.

Sample Input 3

3
100 100 100

Sample Output 3

1

Problem Statement

There are N competitive programmers numbered person 1, person 2, \ldots, and person N.
There is a relation called superiority between the programmers. For all pairs of distinct programmers (person X, person Y), exactly one of the following two relations holds: "person X is stronger than person Y" or "person Y is stronger than person X."
The superiority is transitive. In other words, for all triplets of distinct programmers (person X, person Y, person Z), it holds that:

• if person X is stronger than person Y and person Y is stronger than person Z, then person X is stronger than person Z.

A person X is said to be the strongest programmer if person X is stronger than person Y for all people Y other than person X. (Under the constraints above, we can prove that there is always exactly one such person.)

You have M pieces of information on their superiority. The i-th of them is that "person A_i is stronger than person B_i."
Can you determine the strongest programmer among the N based on the information?
If you can, print the person's number. Otherwise, that is, if there are multiple possible strongest programmers, print -1.

Constraints

• 2 \leq N \leq 50
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• If i \neq j, then (A_i, B_i) \neq (A_j, B_j).
• There is at least one way to determine superiorities for all pairs of distinct programmers, that is consistent with the given information.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1

You have two pieces of information: "person 1 is stronger than person 2" and "person 2 is stronger than person 3."
By the transitivity, you can also infer that "person 1 is stronger than person 3," so person 1 is the strongest programmer.

Sample Input 2

3 2
1 3
2 3

Sample Output 2

-1

Both person 1 and person 2 may be the strongest programmer. Since you cannot uniquely determine which is the strongest, you should print -1.

Sample Input 3

6 6
1 6
6 5
6 2
2 3
4 3
4 2

Sample Output 3

-1

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

• Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

Constraints

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

Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

• Choose i=2 and j=3 to make A=(4,6,4,7).
• Choose i=4 and j=1 to make A=(5,6,4,6).
• Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.

Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974

Problem Statement

This is an interactive task (where your program and the judge interact via Standard Input and Output).

You are given an integer N and an odd number K.
The judge has a hidden length-N sequence A = (A_1, A_2, \dots, A_N) consisting of 0 and 1.

While you cannot directly access the elements of sequence A, you are allowed to ask the judge the following query at most N times.

• Choose distinct integers x_1, x_2, \dots, and x_K between 1 and N, inclusive, to ask the parity of A_{x_1} + A_{x_2} + \dots + A_{x_K}.

Determine (A_1, A_2, \dots, A_N) by at most N queries, and print the answer.
Here, the judge is adaptive. In other words, the judge may modify the contents of A as long as it is consistent with the responses to the past queries.
Therefore, your program is considered correct if the output satisfies the following condition, and incorrect otherwise:

• your program prints a sequence consistent with the responses to the queries so far, and that is the only such sequence.

Constraints

• 1 \leq K \lt N \leq 1000
• K is odd.
• A_i is 0 or 1.

Input and Output

This is an interactive task (where your program and the judge interact via Standard Input and Output).

First of all, receive N and K from Standard Input.

N K

Then, repeat asking queries until you can uniquely determine (A_1, A_2, \dots, A_N).
Each query should be printed to Standard Output in the following format, where x_1, x_2, \dots, and x_K are K distinct integers between 1 and N, inclusive.

? x_1 x_2 \dots x_K

The response to the query is given from Standard Input in the following format.

T

Here, T denotes the response to the query.

• T is 0 when A_{x_1} + A_{x_2} + \dots + A_{x_K} is even, and
• T is 1 when A_{x_1} + A_{x_2} + \dots + A_{x_K} is odd.

However, if x_1, x_2, \dots and x_K do not satisfy the constraints, or the number of queries exceeds N, then T is -1.

If the judge returns -1, your program is already considered incorrect, so terminate the program immediately.

When you can determine all the elements of A, print those elements in the following format, and terminate the program immediately.

! A_1 A_2 \dots A_N

Notes

• Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
• The verdict will be indeterminate if there is malformed output during the interaction or your program quits prematurely.
• Terminate the program immediately after printing the answer, or the verdict will be indeterminate.
• The judge for this problem is adaptive. This means that the judge may modify the contents of A as long as it is consistent with the responses to the past queries.

Sample Interaction

In the following interaction, N=5 and K=3. Note that the following output itself will result in WA.
Here, A = (1, 0, 1, 1, 0) is indeed consistent with the responses, but so is (0, 0, 1, 0, 0), so sequence A is not uniquely determined. Thus, this program is considered incorrect.

Problem Statement

For a string S consisting of digits from 1 through 9, let f(S) be the string T obtained by the following procedure. (S_i denotes the i-th character of S.)

• Let T be an initially empty string.
• For i=1, 2, \dots, |S| - 1, perform the following operation:
  • Append n copies of S_i to the tail of T, where n is the value when S_{i+1} is interpreted as an integer.

For example, S = 313 yields f(S) = 3111 by the following steps.

• T is initially empty.
• For i=1, we have n = 1. Append one copy of 3 to T, which becomes 3.
• For i=2, we have n = 3. Append three copies of 1 to T, which becomes 3111.
• Terminate the procedure. We obtain T = 3111.

You are given a length-N string S consisting of digits from 1 through 9.
You repeat the following operation until the length of S becomes 1: replace S with f(S).
Find how many times, modulo 998244353, you perform the operation until you complete it. If you will repeat the operation indefinitely, print -1 instead.

Constraints

• 2 \leq N \leq 10^6
• S is a length-N string consisting of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Sample Input 1

3
313

Sample Output 1

4

If S = 313, the length of S be comes 1 after four operations.

• We have f(S) = 3111. Replace S with 3111.
• We have f(S) = 311. Replace S with 311.
• We have f(S) = 31. Replace S with 31.
• We have f(S) = 3. Replace S with 3.
• Now that the length of S is 1, terminate the repetition.

Sample Input 2

9
123456789

Sample Output 2

-1

If S = 123456789, you indefinitely repeat the operation. In this case, -1 should be printed.

Sample Input 3

2
11

Sample Output 3

1

Problem Statement

There are N cards numbered 1 through N. Each face of a card has an integer written on it; card i has A_i on its front and B_i on its back. Initially, all cards are face up.

There are M machines numbered 1 through M. Machine j has two (not necessarily distinct) integers X_j and Y_j between 1 and N. If you power up machine j, it flips card X_j with the probability of \frac{1}{2}, and flips card Y_j with the remaining probability of \frac{1}{2}. This probability is independent for each power-up.

Snuke will perform the following procedure.

1. Choose a set S consisting of integers from 1 through M.
2. For each element in S in ascending order, power up the machine with that number.

Among Snuke's possible choices of S, find the maximum expected value of the sum of the integers written on the face-up sides of the cards after the procedure.

Constraints

• 1\leq N \leq 40
• 1\leq M \leq 10^5
• 1\leq A_i,B_i \leq 10^4
• 1\leq X_j,Y_j \leq N
• All input values are integers.

Sample Input 1

3 1
3 10
10 6
5 2
1 2

Sample Output 1

19.500000

If S is chosen to be an empty set, no machine is powered up, so the expected sum of the integers written on the face-up sides of the cards after the procedure is 3+10+5=18.

If S is chosen to be \lbrace 1 \rbrace, machine 1 is powered up.

• If card X_1 = 1 is flipped, the expected sum of the integers written on the face-up sides of the cards after the procedure is 10+10+5=25.
• If card Y_1 = 2 is flipped, the expected sum of the integers written on the face-up sides of the cards after the procedure is 3+6+5=14.

Thus, the expected value is \frac{25+14}{2} = 19.5.

Therefore, the maximum expected value of the sum of the integers written on the face-up sides of the cards after the procedure is 19.5.

Sample Input 2

1 3
5 100
1 1
1 1
1 1

Sample Output 2

100.000000

Different machines may have the same (X_j,Y_j).

Sample Input 3

8 10
6918 9211
16 1868
3857 8537
3340 8506
6263 7940
1449 4593
5902 1932
310 6991
4 4
8 6
3 5
1 1
4 2
5 6
7 5
3 3
1 5
3 1

Sample Output 3

45945.000000

Problem Statement

There are N plates numbered 1 through N. Dish i has a_i stones on it. There is also an empty bag.
You can perform the following two kinds of operations any number of times (possibly zero) in any order.

• Remove one stone from each plate with one or more stones. Put the removed stones into the bag.
• Take N stones out of the bag, and put one stone to each plate. This operation can be performed only when the bag has N or more stones.

Let b_i be the number of stones on plate i after you finished the operations. Print the number, modulo 998244353, of sequences of integers (b_1, b_2, \dots, b_N) of length N that can result from the operations.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9

Sample Input 1

3
3 1 3

Sample Output 1

7

For example, b becomes (2, 1, 2) by the following procedure.

• Perform the first operation. b becomes (2, 0, 2).
• Perform the first operation. b becomes (1, 0, 1).
• Perform the second operation. b becomes (2, 1, 2).

The following seven sequences can be the resulting b.

• (0, 0, 0)
• (1, 0, 1)
• (1, 1, 1)
• (2, 0, 2)
• (2, 1, 2)
• (2, 2, 2)
• (3, 1, 3)

Sample Input 2

1
0

Sample Output 2

1

There are one sequence, (0), that can be the resulting b.

Sample Input 3

5
1 3 5 7 9

Sample Output 3

36

Sample Input 4

10
766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044

Sample Output 4

666174028

Problem Statement

(2N+1) people are forming two rows to take a group photograph. There are N people in the front row; the i-th of them has a height of A_i. There are (N+1) people in the back row; the i-th of them has a height of B_i. It is guaranteed that the heights of the (2N+1) people are distinct. Within each row, we can freely rearrange the people.

Suppose that the heights of the people in the front row are a_1,a_2,\dots,a_N from the left, and those in the back row are b_1,b_2,\dots,b_{N+1} from the left. This arrangement is said to be good if all of the following conditions are satisfied:

• a_i < b_i or a_{i-1} < b_i for all i\ (2 \leq i \leq N).
• a_1 < b_1.
• a_N < b_{N+1}.

Among the N! ways to rearrange the front row, how many of them, modulo 998244353, are such ways that we can rearrange the back row to make the arrangement good?

Constraints

• 1\leq N \leq 5000
• 1 \leq A_i,B_i \leq 10^9
• A_i \neq A_j\ (1 \leq i < j \leq N)
• B_i \neq B_j\ (1 \leq i < j \leq N+1)
• A_i \neq B_j\ (1 \leq i \leq N, 1 \leq j \leq N+1)
• All input values are integers.

Sample Input 1

3
1 12 6
4 3 10 9

Sample Output 1

2

• When a = (1,12,6), we can let, for example, b = (4,3,10,9) to make the arrangement good.
• When a = (6,12,1), we can let, for example, b = (10,9,4,3) to make the arrangement good.
• When a is one of the other four ways, no rearrangement of the back row (that is, none of the possible 24 candidates of b) makes the arrangement good.

Thus, the answer is 2.

Sample Input 2

1
5
1 10

Sample Output 2

0

Sample Input 3

10
189330739 910286918 802329211 923078537 492686568 404539679 822804784 303238506 650287940 1
125660016 430302156 982631932 773361868 161735902 731963982 317063340 880895728 1000000000 707723857 450968417

Sample Output 3

3542400