Problem Statement

Takahashi will have N penalty kicks in a soccer match.

For the i-th penalty kick, he will fail if i is a multiple of 3, and succeed otherwise.

Print the results of his penalty kicks.

Constraints

• 1 \leq N \leq 100
• All inputs are integers.

Sample Input 1

7

Sample Output 1

ooxooxo

Takahashi fails the third and sixth penalty kicks, so the third and sixth characters will be x.

Sample Input 2

9

Sample Output 2

ooxooxoox

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

Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!

There are N integers from 1 through N arranged in a line in ascending order.
Between them are M "レ" marks. The i-th "レ" mark is between the integer a_i and integer (a_i + 1).

You read each of the N integers once by the following procedure.

• Consider an undirected graph G with N vertices numbered 1 through N and M edges. The i-th edge connects vertex a_i and vertex (a_i+1).
• Repeat the following operation until there is no unread integer:
  • let x be the minimum unread integer. Choose the connected component C containing vertex x, and read all the numbers of the vertices contained in C in descending order.

For example, suppose that integers and "レ" marks are arranged in the following order:

(In this case, N = 5, M = 3, and a = (1, 3, 4).)
Then, the order to read the integers is determined to be 2, 1, 5, 4, and 3, as follows:

• At first, the minimum unread integer is 1, and the connected component of G containing vertex 1 has vertices \lbrace 1, 2 \rbrace, so 2 and 1 are read in this order.
• Then, the minimum unread integer is 3, and the connected component of G containing vertex 3 has vertices \lbrace 3, 4, 5 \rbrace, so 5, 4, and 3 are read in this order.
• Now that all integers are read, terminate the procedure.

Given N, M, and (a_1, a_2, \dots, a_M), print the order to read the N integers.

Constraints

• 1 \leq N \leq 100
• 0 \leq M \leq N - 1
• 1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
• All values in the input are integers.

Sample Input 1

5 3
1 3 4

Sample Output 1

2 1 5 4 3

As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:

then the integers are read in the following order: 2, 1, 5, 4, and 3.

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

There may be no "レ" mark.

Sample Input 3

10 6
1 2 3 7 8 9

Sample Output 3

4 3 2 1 5 6 10 9 8 7

Problem Statement

There are N people whose IDs are 1, 2, \ldots, and N.

Each of person 1, person 2, \ldots, and person N performs the following action once in this order:

• If person i's ID has not been called out yet, call out person A_i's ID.

Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• A_i \neq i
• All values in the input are integers.

Sample Input 1

5
3 1 4 5 4

Sample Output 1

2
2 4

The five people's actions are as follows.

• Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
• Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
• Person 3's ID has already been called out by person 1, so nothing happens.
• Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
• Person 5's ID has already been called out by person 4, so nothing happens.

Therefore, person 2 and 4's IDs are not called out until the end.

Sample Input 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Sample Output 2

10
1 2 5 6 8 11 14 17 18 20

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

Constraints

• 2 \leq N \leq 100
• 1 \leq P_i \leq N \, (1 \leq i \leq N)
• P_i \neq P_j \, (i \neq j)
• (P_1, \dots, P_N) \neq (1, \dots, N)
• All values in the input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

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

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1

Problem Statement

There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.

Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.

• For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
• For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.

In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A \leq N
• 1 \leq B \leq N
• 1 \leq P \leq Q \leq N
• 1 \leq R \leq S \leq N
• (Q-P+1)\times(S-R+1)\leq 3\times 10^5
• All values in input are integers.

Sample Input 1

5 3 2
1 5 1 5

Sample Output 1

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

The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.

Sample Input 2

5 3 3
4 5 2 5

Sample Output 2

#.#.
...#

The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.

Sample Input 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

Sample Output 3

#.#
.#.
#.#

Note that the input may not fit into a 32-bit integer type.

Problem Statement

For positive integers x and y, define f(x, y) as follows:

• Interpret the decimal representations of x and y as strings and concatenate them in this order to obtain a string z. The value of f(x, y) is the value of z when interpreted as a decimal integer.

For example, f(3, 14) = 314 and f(100, 1) = 1001.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression modulo 998244353:

Constraints

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

Sample Input 1

3
3 14 15

Sample Output 1

2044

• f(A_1, A_2) = 314
• f(A_1, A_3) = 315
• f(A_2, A_3) = 1415

Thus, the answer is f(A_1, A_2) + f(A_1, A_3) + f(A_2, A_3) = 2044.

Sample Input 2

5
1001 5 1000000 1000000000 100000

Sample Output 2

625549048

Be sure to calculate the value modulo 998244353.

Problem Statement

You are given two strings: S, which consists of uppercase English letters and has length N, and T, which also consists of uppercase English letters and has length M\ (\leq N).

There is a string X of length N consisting only of the character #. Determine whether it is possible to make X match S by performing the following operation any number of times:

• Choose M consecutive characters in X and replace them with T.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq \min(N, 5)
• S is a string consisting of uppercase English letters with length N.
• T is a string consisting of uppercase English letters with length M.

Sample Input 1

7 3
ABCBABC
ABC

Sample Output 1

Yes

Below, let X[l:r] denote the part from the l-th through the r-th character of X.

You can make X match S by operating as follows.

1. Replace X[3:5] with T. X becomes ##ABC##.
2. Replace X[1:3] with T. X becomes ABCBC##.
3. Replace X[5:7] with T. X becomes ABCBABC.

Sample Input 2

7 3
ABBCABC
ABC

Sample Output 2

No

No matter how you operate, it is impossible to make X match S.

Sample Input 3

12 2
XYXXYXXYYYXY
XY

Sample Output 3

Yes

Problem Statement

You are given a string S of length N consisting of o and x, and integers M and K.
S is guaranteed to contain at least one x.

Let T be the string of length NM obtained by concatenating M copies of S. Consider replacing exactly K x's in T with o.
Your objective is to have as long a contiguous substring consisting of o as possible in the resulting T.
Find the maximum length of a contiguous substring consisting of o that you can obtain.

Constraints

• N, M, and K are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le M \le 10^9
• 1 \le K \le x, where x is the number of x's in the string T.
• S is a string of length N consisting of o and x.
• S has at least one x.

Sample Input 1

10 1 2
ooxxooooox

Sample Output 1

9

S= ooxxooooox and T= ooxxooooox.
Replacing x at the third and fourth characters with o makes T= ooooooooox.
Now we have a length-9 contiguous substring consisting of o, which is the longest possible.

Sample Input 2

5 3 4
oxxox

Sample Output 2

8

S= oxxox and T= oxxoxoxxoxoxxox.
Replacing x at the 5,7,8 and 10-th characters with o makes T= oxxooooooooxxox.
Now we have a length-8 contiguous substring consisting of o, which is the longest possible.

Sample Input 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

Sample Output 3

19964887064