Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:

• remove the initial element of A and append a 0 to the tail of A.

Print all the elements of A after the operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 100
• 1 \leq A_i \leq 100
• All values in the input are integers.

Sample Input 1

3 2
2 7 8

Sample Output 1

8 0 0

Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.

Sample Input 2

3 4
9 9 9

Sample Output 2

0 0 0

Sample Input 3

9 5
1 2 3 4 5 6 7 8 9

Sample Output 3

6 7 8 9 0 0 0 0 0

Problem Statement

Naohiro has a monster. The monster's current health is H.
He also has N kinds of potions, numbered from 1 to N in ascending order of effectiveness.
If you give the monster potion n, its health will increase by P_n. Here, P_1 \lt P_2 \lt \dots \lt P_N.

He wants to increase the monster's health to X or above by giving it one of the potions.
Print the number of the least effective potion that can achieve the purpose. (The constraints guarantee that such a potion exists.)

Constraints

• 2 \leq N \leq 100
• 1 \leq H \lt X \leq 999
• 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
• All input values are integers.

Sample Input 1

3 100 200
50 200 999

Sample Output 1

2

Below is the change in the monster's health when one of the potions is given to the monster.

• If potion 1 is given, the monster's health becomes 100 + 50 = 150.
• If potion 2 is given, the monster's health becomes 100 + 200 = 300.
• If potion 3 is given, the monster's health becomes 100 + 999 = 1099.

The potions that increase the monster's health to at least X = 200 are potions 2 and 3. The answer is the least effective of them, which is potion 2.

Sample Input 2

2 10 21
10 999

Sample Output 2

2

Sample Input 3

10 500 999
38 420 490 585 613 614 760 926 945 999

Sample Output 3

4

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

• 1 \leq R, C \leq 15
• R and C are integers.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

Problem Statement

Takahashi has N teeth, one in each of the holes numbered 1, 2, \dots, N.
Dentist Aoki will perform Q treatments on these teeth and holes.
In the i-th treatment, hole T_i is treated as follows:

• If there is a tooth in hole T_i, remove the tooth from hole T_i.
• If there is no tooth in hole T_i (i.e., the hole is empty), grow a tooth in hole T_i.

After all treatments are completed, how many teeth does Takahashi have?

Constraints

• All input values are integers.
• 1 \le N, Q \le 1000
• 1 \le T_i \le N

Sample Input 1

30 6
2 9 18 27 18 9

Sample Output 1

28

Initially, Takahashi has 30 teeth, and Aoki performs six treatments.

• In the first treatment, hole 2 is treated. There is a tooth in hole 2, so it is removed.
• In the second treatment, hole 9 is treated. There is a tooth in hole 9, so it is removed.
• In the third treatment, hole 18 is treated. There is a tooth in hole 18, so it is removed.
• In the fourth treatment, hole 27 is treated. There is a tooth in hole 27, so it is removed.
• In the fifth treatment, hole 18 is treated. There is no tooth in hole 18, so a tooth is grown.
• In the sixth treatment, hole 9 is treated. There is no tooth in hole 9, so a tooth is grown.

The final count of teeth is 28.

Sample Input 2

1 7
1 1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

9 20
9 5 1 2 2 2 8 9 2 1 6 2 6 5 8 7 8 5 9 8

Sample Output 3

5

Problem Statement

You have an unlimited supply of two types of candies: small candies and large candies. The weight of a small candy is X grams, and the weight of a large candy is Y grams. Large candies are heavier than small candies (that is, X < Y).

There are N children, numbered 1 to N.

You have decided to distribute candies so that the following conditions are satisfied:

• For i=1,\dots,N, child i receives exactly A_i candies in total of the two types.
• The total weights of candies distributed to the N children are all equal.

Determine whether there exists a distribution method that satisfies the conditions. If it exists, find the maximum possible value for the number of large candies distributed.

Constraints

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

Sample Input 1

3 6 8
11 10 13

Sample Output 1

18

You can distribute candies as follows so that the total weights of candies distributed to the children are all equal.

• Child 1 receives 4 small candies and 7 large candies. The total weight is 6 \times 4 + 8 \times 7 = 80 grams.
• Child 2 receives 0 small candies and 10 large candies. The total weight is 6 \times 0 + 8 \times 10 = 80 grams.
• Child 3 receives 12 small candies and 1 large candy. The total weight is 6 \times 12 + 8 \times 1 = 80 grams.

In this distribution method, a total of 18 large candies are distributed.

There is no distribution method that satisfies the conditions and distributes more than 18 large candies. Therefore, the answer is 18.

Sample Input 2

2 3 4
3 5

Sample Output 2

-1

There is no distribution method that satisfies the conditions.

Sample Input 3

8 4 32
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

8000000000

The answer may not fit in a 32-bit integer.

Problem Statement

You are given a length-N integer sequence A = (A_1, A_2, \dots, A_N).

Compute the value of \displaystyle \sum_{1\leq i< j\leq N} A_iA_j.

Constraints

• 2 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^4
• All input values are integers.

Sample Input 1

3
4 2 3

Sample Output 1

26

We have \displaystyle \sum_{1\leq i< j\leq N} A_iA_j=A_1A_2+A_1A_3+A_2A_3=4\cdot 2+4\cdot 3+2\cdot 3=26.

Sample Input 2

2
9 45

Sample Output 2

405

Sample Input 3

10
7781 8803 8630 9065 8831 9182 8593 7660 7548 8617

Sample Output 3

3227530139

Problem Statement

You are given a length-N sequence of positive integers A = (A_1, A_2, \dots, A_N) and a length-M sequence of positive integers B = (B_1, B_2, \dots, B_M).

Find the value of \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} |A_i - B_j|, modulo 998244353.

Constraints

• 1 \leq N,M \leq 3 \times 10^5
• 1 \leq A_i, B_j < 998244353
• All input values are integers.

Sample Input 1

4 2
1 6 9 2
3 1

Sample Output 1

26

The answer is |1-3| + |1-1| + |6-3| + |6-1| + |9-3| + |9-1| + |2-3| + |2-1| = 2+0+3+5+6+8+1+1 = 26.

Sample Input 2

8 8
185991676 311812083 311812083 84357963 185991676 185991676 724020528 369175631
455049197 387671868 4361724 724020528 724020528 455049197 455049197 724020528

Sample Output 2

529117255

Problem Statement

You are given strings A and B of equal length consisting of 0 and 1.

You can perform the following operation on A zero or more times.

• Move the first character of A to the end.

Find the minimum number of operations required to make A=B.
If it is impossible to make A=B no matter how you operate, print -1 instead.

You are given T test cases; find the answer for each of them.

Constraints

• 1 \le T \le 10000
• A and B are strings consisting of 0 and 1.
• 2 \le |A|=|B| \le 10^6
• For a single input, the sum of |A| does not exceed 10^6.

Sample Input 1

5
1010001
1000110
000
111
01010
01010
0101
0011
100001101110000001010110110001
101100011000011011100000010101

Sample Output 1

2
-1
0
-1
22

This input contains five test cases.

• For the first test case, A= 1010001 and B= 1000110.
  • By performing the operation on A twice, A becomes 1010001 \rightarrow 0100011 \rightarrow 1000110, which makes A=B.
• For the second test case, no matter how you perform the operation, you cannot change 000 to 111.
• For the third test case, A=B from the beginning.

Problem Statement

You are given two sequences of N numbers: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

Takahashi can repeat the following operation any number of times (possibly zero).

Choose three pairwise distinct integers i, j, and k between 1 and N.
Swap the i-th and j-th elements of A, and swap the i-th and k-th elements of B.

If there is a way for Takahashi to repeat the operation to make A and B equal, print Yes; otherwise, print No.
Here, A and B are said to be equal when, for every 1\leq i\leq N, the i-th element of A and that of B are equal.

Constraints

• 3 \leq N \leq 2\times 10^5
• 1\leq A_i,B_i\leq N
• All values in the input are integers.

Sample Input 1

3
1 2 1
1 1 2

Sample Output 1

Yes

Performing the operation once with (i,j,k)=(1,2,3) swaps A_1 and A_2, and swaps B_1 and B_3,
making both A and B equal to (2,1,1). Thus, you should print Yes.

Sample Input 2

3
1 2 2
1 1 2

Sample Output 2

No

There is no way to perform the operation to make A and B equal, so you should print No.

Sample Input 3

5
1 2 3 2 1
3 2 2 1 1

Sample Output 3

Yes

Sample Input 4

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

Sample Output 4

No