Problem Statement

You are given a string S of length 16 consisting of 0 and 1.

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Constraints

• S is a string of length 16 consisting of 0 and 1.

Sample Input 1

1001000000001010

Sample Output 1

No

The 4-th character of S= 1001000000001010 is 1, so you should print No.

Sample Input 2

1010100000101000

Sample Output 2

Yes

Every even-positioned character in S= 1010100000101000 is 0, so you should print Yes.

Sample Input 3

1111111111111111

Sample Output 3

No

Every even-positioned character in S is 1. Particularly, they are not all 0, so you should print No.

Problem Statement

You are given a string S consisting of uppercase English letters. Separate each character of S with a space and print them one by one in order.

Constraints

• S is a string consisting of uppercase English letters with a length between 2 and 100, inclusive.

Sample Input 1

ABC

Sample Output 1

A B C

Separate A, B, and C with spaces and print them one by one.

There is no need to print a space after C.

Sample Input 2

ZZZZZZZ

Sample Output 2

Z Z Z Z Z Z Z

Sample Input 3

OOXXOO

Sample Output 3

O O X X O O

Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

• If the L_i-th piece from the left is on its rightmost square, do nothing.
• Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

• 1\leq K\leq N\leq 200
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1\leq Q\leq 1000
• 1\leq L_i\leq K
• All values in input are integers.

Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

• The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
• The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
• The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
• The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
• The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.

Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

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

Sample Output 3

2 5 6 7 9 10

Problem Statement

You are given a string S of length N consisting of o and x.
N chairs are arranged in a row from left to right. If the i-th character of S is o, a person is sitting in the i-th chair from the left; if it is x, no person is sitting there.
Find the number of chairs that satisfy all of the following conditions.

• No person is sitting in it.
• There is no chair to its left, or no person is sitting in the chair to its left.
• There is no chair to its right, or no person is sitting in the chair to its right.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• S is a string of length N consisting of o and x.

Sample Input 1

8
xxoxxxox

Sample Output 1

2

Only the first and fifth chairs from the left satisfy the conditions.

Sample Input 2

5
ooooo

Sample Output 2

0

Sample Input 3

1
x

Sample Output 3

1

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

• 1 \leq N \leq 10^4
• 1 \leq M \leq 7
• 1 \leq B_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.

Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.

Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes

Problem Statement

You are given an integer X. The following action on this integer is called an operation.

• Choose and do one of the following.
  • Add 1 to X.
  • Subtract 1 from X.

The terms in the arithmetic progression S with N terms whose initial term is A and whose common difference is D are called good numbers.
Consider performing zero or more operations to make X a good number. Find the minimum number of operations required to do so.

Constraints

• All values in input are integers.
• -10^{18} \le X,A \le 10^{18}
• -10^6 \le D \le 10^6
• 1 \le N \le 10^{12}

Sample Input 1

6 2 3 3

Sample Output 1

1

Since A=2,D=3,N=3, we have S=(2,5,8).
You can subtract 1 from X once to make X=6 a good number.
It is impossible to make X good in zero operations.

Sample Input 2

0 0 0 1

Sample Output 2

0

We might have D=0. Additionally, no operation might be required.

Sample Input 3

998244353 -10 -20 30

Sample Output 3

998244363

Sample Input 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

Sample Output 4

444445

Problem Statement

There is a deck consisting of N face-down cards with an integer from 1 through N written on them. The integer on the i-th card from the top is P_i.

Using this deck, you will perform N moves, each consisting of the following steps:

• Draw the topmost card from the deck. Let X be the integer written on it.
• Stack the drawn card, face up, onto the card with the smallest integer among the face-up topmost cards on the table with an integer greater than or equal to X written on them. If there is no such card on the table, put the drawn card on the table, face up, without stacking it onto any card.
• Then, if there is a pile consisting of K face-up cards on the table, eat all those cards. The eaten cards all disappear from the table.

For each card, find which of the N moves eats it. If the card is not eaten until the end, report that fact.

Constraints

• All values in input are integers.
• 1 \le K \le N \le 2 \times 10^5
• P is a permutation of (1,2,\dots,N) (i.e. a sequence obtained by rearranging (1,2,\dots,N)).

Sample Input 1

5 2
3 5 2 1 4

Sample Output 1

4
3
3
-1
4

In this input, P=(3,5,2,1,4) and K=2.

• In the 1-st move, the card with 3 written on it is put on the table, face up, without stacked onto any card.
• In the 2-nd move, the card with 5 written on it is put on the table, face up, without stacked onto any card.
• In the 3-rd move, the card with 2 written on it is stacked, face up, onto the card with 3 written on it.
  • Now there is a pile consisting of K=2 face-up cards, on which 2 and 3 from the top are written, so these cards are eaten.
• In the 4-th move, the card with 1 written on it is stacked, face up, onto the card with 5 written on it.
  • Now there is a pile consisting of K=2 face-up cards, on which 1 and 5 from the top are written, so these cards are eaten.
• In the 5-th move, the card with 4 written on it is put on the table, face up, without stacked onto any card.
• The card with 4 written on it was not eaten until the end.

Sample Input 2

5 1
1 2 3 4 5

Sample Output 2

1
2
3
4
5

If K=1, every card is eaten immediately after put on the table within a single move.

Sample Input 3

15 3
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

Sample Output 3

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15

Problem Statement

We have N cards. The i-th card (1 \leq i \leq N) has an integer A_i written on it.

Takahashi will choose any number of cards from these. However, for each i (1 \leq i \leq N - 1), at least one of the i-th and (i+1)-th cards must be chosen.

Find the following values.

• The maximum possible average of the integers written on the chosen cards
• The maximum possible median of the integers written on the chosen cards

Here, the median of the n integers is defined to be the \lceil \frac{n}{2} \rceil-th smallest of them, where \lceil x \rceil is the smallest integer not less than x.

Constraints

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

Sample Input 1

6
2 1 2 1 1 10

Sample Output 1

4
2

Choosing the 2-nd, 4-th, and 6-th cards makes the average of the written integers \frac{12}{3} = 4, which is the maximum possible.

Choosing the 1-st, 3-rd, 5-th, and 6-th cards makes the median of the written integers 2, which is the maximum possible.

Sample Input 2

7
3 1 4 1 5 9 2

Sample Output 2

5.250000000
4

For the average, your output may contain some degree of error: for example, the output 5.2491 is still considered correct. For the median, however, the exact value must be printed.

Problem Statement

You are given positive integers N, M, K, and a sequence of positive integers of length N, (C_1, C_2, \ldots, C_N). For each r = 0, 1, 2, \ldots, N-1, print the answer to the following problem.

There is a sequence of N colored balls. For i = 1, 2, \ldots, N, the color of the i-th ball from the beginning of the sequence is C_i. Additionally, there are M empty boxes numbered 1 to M.

Determine the total number of balls in the boxes after performing the following steps.

• First, perform the following operation r times.

  • Move the frontmost ball in the sequence to the end of the sequence.

• Then, repeat the following operation as long as at least one ball remains in the sequence.

  • If there is a box that already contains at least one but fewer than K balls of the same color as the frontmost ball in the sequence, put the frontmost ball into that box.
  • If there is no such box,
    • If there is an empty box, put the frontmost ball into the one with the smallest box number.
    • If there are no empty boxes, eat the frontmost ball without putting it into any box.

Constraints

• All input values are integers.
• 1 \leq N \leq 2 \times 10^5
• 1 \leq M, K \leq N
• 1 \leq C_i \leq N

Sample Input 1

7 2 2
1 2 3 5 2 5 4

Sample Output 1

3
3
3
4
4
3
2

For example, let us explain the procedure for r = 1. First, perform the operation "Move the frontmost ball in the sequence to the end of the sequence" once, and the sequence of ball colors becomes (2, 3, 5, 2, 5, 4, 1). Then, proceed with the operation of putting balls into boxes as follows:

• First operation: The color of the frontmost ball is 2. There is no box with at least one but fewer than two balls of color 2, so put the frontmost ball into the empty box with the smallest box number, box 1.
• Second operation: The color of the frontmost ball is 3. There is no box with at least one but fewer than two balls of color 3, so put the frontmost ball into the empty box with the smallest box number, box 2.
• Third operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
• Fourth operation: The color of the frontmost ball is 2. There is a box, box 1, with at least one but fewer than two balls of color 2, so put the frontmost ball into box 1.
• Fifth operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
• Sixth operation: The color of the frontmost ball is 4. There is no box with at least one but fewer than two balls of color 4 and no empty boxes, so eat the frontmost ball.
• Seventh operation: The color of the frontmost ball is 1. There is no box with at least one but fewer than two balls of color 1 and no empty boxes, so eat the frontmost ball.

The final total number of balls in the boxes is 3, so the answer to the problem for r = 1 is 3.

Sample Input 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

Sample Output 2

14
14
14
14
13
13
13
11
8
9
9
11
13
14
14
14
14
14
14
13