Problem Statement

You are given a string s consisting of two kinds of characters, 0 and 1. Print the string obtained by replacing 0 with 1 and 1 with 0 in s.

Constraints

• The length of s is between 1 and 10, inclusive.
• s consists of two kinds of characters, 0 and 1.

Sample Input 1

01

Sample Output 1

10

The 1-st character of s is 1, so the 1-st character to print is 0. The 2-nd character of s is 0, so the 2-nd character to print is 1.

Sample Input 2

1011

Sample Output 2

0100

Sample Input 3

100100001

Sample Output 3

011011110

Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

• 0\leq A,B \leq 7
• A and B are integers.

Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.

Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.

Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

Problem Statement

There is a grid with H rows and W columns; initially, all cells are painted white. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

This grid is considered to be toroidal. That is, (i, 1) is to the right of (i, W) for each 1 \leq i \leq H, and (1, j) is below (H, j) for each 1 \leq j \leq W.

Takahashi is at (1, 1) and facing upwards. Print the color of each cell in the grid after Takahashi repeats the following operation N times.

• If the current cell is painted white, repaint it black, rotate 90^\circ clockwise, and move forward one cell in the direction he is facing. Otherwise, repaint the current cell white, rotate 90^\circ counterclockwise, and move forward one cell in the direction he is facing.

Constraints

• 1 \leq H, W \leq 100
• 1 \leq N \leq 1000
• All input values are integers.

Sample Input 1

3 4 5

Sample Output 1

.#..
##..
....

The cells of the grid change as follows due to the operations:

....   #...   ##..   ##..   ##..   .#..
.... → .... → .... → .#.. → ##.. → ##..
....   ....   ....   ....   ....   ....

Sample Input 2

2 2 1000

Sample Output 2

..
..

Sample Input 3

10 10 10

Sample Output 3

##........
##........
..........
..........
..........
..........
..........
..........
..........
#........#

Problem Statement

There is a parking lot. The fee for parking in this lot is as follows:

• During the period from exactly L o'clock to exactly R o'clock, a fee of X is charged for each hour parked.
• During the period not covered above, a fee of Y is charged for each hour parked.

If a car is parked in this lot from exactly A o'clock to exactly B o'clock without crossing midnight, how much is the fee?

Constraints

• 1 \leq X, Y \leq 1000
• 1 \leq L < R \leq 23
• 1 \leq A < B \leq 23
• All input values are integers.

Sample Input 1

700 300 9 17 7 21

Sample Output 1

7400

If a car is parked from 7 o'clock to 21 o'clock, the fee is as follows.

• For the 2 hours from 7 o'clock to 9 o'clock, a fee of 300 \times 2 = 600 is charged.
• For the 8 hours from 9 o'clock to 17 o'clock, a fee of 700 \times 8 = 5600 is charged.
• For the 4 hours from 17 o'clock to 21 o'clock, a fee of 300 \times 4 = 1200 is charged.

The answer is 600 + 5600 + 1200 = 7400.

Sample Input 2

600 500 9 17 17 20

Sample Output 2

1500

If a car is parked from 17 o'clock to 20 o'clock, the fee is as follows.

• For the 3 hours from 17 o'clock to 20 o'clock, a fee of 500 \times 3 = 1500 is charged.

The answer is 1500.

Sample Input 3

900 200 12 14 11 13

Sample Output 3

1100

Problem Statement

The AtCoder Restaurant uses N types of ingredients numbered from 1 to N.

The restaurant offers M dishes numbered from 1 to M. Dish i uses K_i types of ingredients, namely A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}.

Snuke currently dislikes all N ingredients. He cannot eat any dish that uses one or more ingredients he dislikes, and he can eat a dish that uses none of the disliked ingredients.

Over the next N days, he will overcome his dislikes one ingredient per day. On day i, he overcomes ingredient B_i, and from then on he no longer dislikes it.

For each i=1,2,\ldots,N, find:

• the number of dishes at the AtCoder Restaurant that he can eat immediately after overcoming ingredient B_i on day i.

Constraints

• 1 \leq N \leq 3 \times 10^{5}
• 1 \leq M \leq 3 \times 10^{5}
• 1 \leq K_i \leq N (1 \leq i \leq M)
• The sum of K_i is at most 3 \times 10^{5}.
• 1 \leq A_{i,j} \leq N (1 \leq i \leq M, 1 \leq j \leq K_i)
• A_{i,j} \neq A_{i,k} (1 \leq i \leq M, j \neq k)
• 1 \leq B_i \leq N (1 \leq i \leq N)
• B_i \neq B_j (i \neq j )
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
2
3
4

Snuke overcomes his disliked ingredients as follows:

• Day 1: He overcomes ingredient 1. At this time, every dish still uses a disliked ingredient, so print 0.
• Day 2: He overcomes ingredient 3. Dish 4 no longer uses any disliked ingredient and becomes edible; all other dishes still use disliked ingredients, so print 1.
• Day 3: He overcomes ingredient 2. Dish 1 no longer uses any disliked ingredient and becomes edible; all dishes except 1 and 4 still use disliked ingredients, so print 2.
• Day 4: He overcomes ingredient 5. Dish 3 no longer uses any disliked ingredient and becomes edible; all dishes except 1, 3, and 4 still use disliked ingredients, so print 3.
• Day 5: He overcomes ingredient 4. Dish 2 no longer uses any disliked ingredient and becomes edible; now all dishes have no disliked ingredients, so print 4.

Sample Input 2

9 8
1 4
5 6 9 7 4 3
4 2 4 1 3
1 1
5 7 9 8 1 5
2 9 8
1 2
1 1
6 5 2 7 8 4 1 9 3

Sample Output 2

0
0
1
1
1
2
4
6
8

Problem Statement

There are N pieces of shari (vinegared rice) and M pieces of neta (toppings) as ingredients for sushi.

The weight of the i-th shari is A_i, and the weight of the j-th neta is B_j.

You will make sushi by combining shari and neta.

To make one piece of sushi, you need to combine one shari with one neta. Here, the weight of the neta must be at most twice the weight of the shari. Also, the same shari or neta cannot be used in multiple pieces of sushi.

Find the maximum number of sushi that can be made.

Constraints

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

Sample Input 1

4 5
4 2 1 8
14 9 3 2 9

Sample Output 1

3

By combining the 1st shari with the 3rd neta, the 2nd shari with the 4th neta, and the 4th shari with the 1st neta, for example, you can make three pieces of sushi. It is impossible to make four or more pieces of sushi, so output 3.

Sample Input 2

3 3
5 5 3
11 1000 1000

Sample Output 2

0

Sample Input 3

8 7
2 3 4 4 4 3 2 3
8 5 5 9 9 7 1

Sample Output 3

5

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

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices of G are numbered vertex 1, vertex 2, \ldots, vertex N, and the i-th (1\leq i\leq M) edge connects vertices U_i and V_i.

Find the lexicographically smallest simple path from vertex X to vertex Y in G.
That is, find the lexicographically smallest among the integer sequences P=(P_1,P_2,\ldots,P_{\lvert P\rvert}) that satisfy the following conditions:

• 1\leq P_i\leq N
• If i\neq j, then P_i\neq P_j.
• P_1=X and P_{\lvert P\rvert}=Y.
• For 1\leq i\leq \lvert P\rvert-1, there exists an edge connecting vertices P_i and P_{i+1}.

One can prove that such a path always exists under the constraints of this problem.

You are given T test cases, so find the answer for each.

Constraints

• 1\leq T\leq 500
• 2\leq N\leq 1000
• N-1\leq M\leq \min\left( \frac{N(N-1)}{2},5\times 10^4\right)
• 1\leq X,Y \leq N
• X\neq Y
• 1\leq U_i<V_i \leq N
• If i\neq j, then (U_i,V_i)\neq (U_j,V_j).
• The given graph is connected.
• The sum of N over all test cases in each input is at most 1000.
• The sum of M over all test cases in each input is at most 5\times 10^4.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3 1 2 5
3 2

For the first test case, graph G is as follows:

The simple paths from vertex 3 to vertex 5 on G, listed in lexicographic order, are as follows:

• (3,1,2,5)
• (3,1,2,6,5)
• (3,1,5)
• (3,1,6,2,5)
• (3,1,6,5)
• (3,4,2,1,5)
• (3,4,2,1,6,5)
• (3,4,2,5)
• (3,4,2,6,1,5)
• (3,4,2,6,5)
• (3,5)

Among these, the lexicographically smallest is (3,1,2,5), so output 3,1,2,5 separated by spaces on the first line.

For the second test case, (3,2) is the only simple path from vertex 3 to vertex 2.

Problem Statement

You are given an integer sequence A = (A_1, A_2, \dots, A_N).
Calculate the following expression:

The constraints guarantee that the answer is less than 2^{63}.

Constraints

• 2 \leq N \leq 4 \times 10^5
• 0 \leq A_i \leq 10^8
• All input values are integers.

Sample Input 1

3
2 5 3

Sample Output 1

4

For (i, j) = (1, 2), we have \max(A_j - A_i, 0) = \max(3, 0) = 3.
For (i, j) = (1, 3), we have \max(A_j - A_i, 0) = \max(1, 0) = 1.
For (i, j) = (2, 3), we have \max(A_j - A_i, 0) = \max(-2, 0) = 0.
Adding these together gives 3 + 1 + 0 = 4, which is the answer.

Sample Input 2

10
5 9 3 0 4 8 7 5 4 0

Sample Output 2

58