Problem Statement

You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.

For each i = 1, 2, \ldots, M in this order, let us perform the following operation.

• Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.

Print the final S after the above operations.

The constraints guarantee that at least one character of S is painted in each of the M colors.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq M
• N, M, and C_i are all integers.
• S is a string of length N consisting of lowercase English letters.
• For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.

Sample Input 1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

Sample Output 1

cszapqbr

Initially, S = apzbqrcs.

• For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S = cpzaqrbs.
• For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S = cszapqbr.
• For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S = cszapqbr (here, S is not changed).

Thus, you should print cszapqbr, the final S.

Sample Input 2

2 1
aa
1 1

Sample Output 2

aa

Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

• It is a string of length L+1 consisting of o and -.
• Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

• There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

• 1\leq N\leq 2\times10^5
• S is a string of length N consisting of o and -.

Sample Input 1

10
o-oooo---o

Sample Output 1

4

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.

Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.

Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

Sample Output 3

7

Problem Statement

There is a grid with N \times N squares. We denote by (i, j) the square at the i-th row from the top and j-th column from the left.

Initially, a piece is placed on (1, 1). You may repeat the following operation any number of times:

• Let (i, j) be the square the piece is currently on. Move the piece to the square whose distance from (i, j) is exactly \sqrt{M}.

Here, we define the distance between square (i, j) and square (k, l) as \sqrt{(i-k)^2+(j-l)^2}.

For all squares (i, j), determine if the piece can reach (i, j). If it can, find the minimum number of operations required to do so.

Constraints

• 1 \le N \le 400
• 1 \le M \le 10^6
• All values in the input are integers.

Sample Input 1

3 1

Sample Output 1

0 1 2
1 2 3
2 3 4

You can move the piece to four adjacent squares.

For example, we can move the piece to (2,2) with two operations as follows.

• The piece is now on (1,1). The distance between (1,1) and (1,2) is exactly \sqrt{1}, so move the piece to (1,2).
• The piece is now on (1,2). The distance between (1,2) and (2,2) is exactly \sqrt{1}, so move the piece to (2,2).

Sample Input 2

10 5

Sample Output 2

0 3 2 3 2 3 4 5 4 5
3 4 1 2 3 4 3 4 5 6
2 1 4 3 2 3 4 5 4 5
3 2 3 2 3 4 3 4 5 6
2 3 2 3 4 3 4 5 4 5
3 4 3 4 3 4 5 4 5 6
4 3 4 3 4 5 4 5 6 5
5 4 5 4 5 4 5 6 5 6
4 5 4 5 4 5 6 5 6 7
5 6 5 6 5 6 5 6 7 6

Problem Statement

In a coordinate space, we want to place three cubes with a side length of 7 so that the volumes of the regions contained in exactly one, two, three cube(s) are V_1, V_2, V_3, respectively.

For three integers a, b, c, let C(a,b,c) denote the cubic region represented by (a\leq x\leq a+7) \land (b\leq y\leq b+7) \land (c\leq z\leq c+7).

Determine whether there are nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 that satisfy all of the following conditions, and find one such tuple if it exists.

• |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| \leq 100
• Let C_i = C(a_i, b_i, c_i)\ (i=1,2,3).
  • The volume of the region contained in exactly one of C_1, C_2, C_3 is V_1.
  • The volume of the region contained in exactly two of C_1, C_2, C_3 is V_2.
  • The volume of the region contained in all of C_1, C_2, C_3 is V_3.

Constraints

• 0 \leq V_1, V_2, V_3 \leq 3 \times 7^3
• All input values are integers.

Sample Input 1

840 84 7

Sample Output 1

Yes
0 0 0 0 6 0 6 0 0

Consider the case (a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (0, 0, 0, 0, 6, 0, 6, 0, 0).

The figure represents the positional relationship of C_1, C_2, and C_3, corresponding to the orange, cyan, and green cubes, respectively.

Here,

• All of |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| are not greater than 100.
• The region contained in all of C_1, C_2, C_3 is (6\leq x\leq 7)\land (6\leq y\leq 7) \land (0\leq z\leq 7), with a volume of (7-6)\times(7-6)\times(7-0)=7.
• The region contained in exactly two of C_1, C_2, C_3 is ((0\leq x < 6)\land (6\leq y\leq 7) \land (0\leq z\leq 7))\lor((6\leq x\leq 7)\land (0\leq y < 6) \land (0\leq z\leq 7)), with a volume of (6-0)\times(7-6)\times(7-0)\times 2=84.
• The region contained in exactly one of C_1, C_2, C_3 has a volume of 840.

Thus, all conditions are satisfied.

(a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (-10, 0, 0, -10, 0, 6, -10, 6, 1) also satisfies all conditions and would be a valid output.

Sample Input 2

343 34 3

Sample Output 2

No

No nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 satisfy all of the conditions.

Problem Statement

There are N cities numbered city 1, city 2, \ldots, and city N.
There are also one-way teleporters that send you to different cities. Whether a teleporter can send you directly from city i (1\leq i\leq N) to another is represented by a length-M string S_i consisting of 0 and 1. Specifically, for 1\leq j\leq N,

• if 1\leq j-i\leq M and the (j-i)-th character of S_i is 1, then a teleporter can send you directly from city i to city j;
• otherwise, it cannot send you directly from city i to city j.

Solve the following problem for k=2,3,\ldots, N-1:

Can you travel from city 1 to city N without visiting city k by repeatedly using a teleporter? If you can, print the minimum number of times you need to use a teleporter; otherwise, print -1.

Constraints

• 3 \leq N \leq 10^5
• 1\leq M\leq 10
• M<N
• S_i is a string of length M consisting of 0 and 1.
• If i+j>N, then the j-th character of S_i is 0.
• N and M are integers.

Sample Input 1

5 2
11
01
11
10
00

Sample Output 1

2 3 2

A teleporter sends you

• from city 1 to cities 2 and 3;
• from city 2 to city 4;
• from city 3 to cities 4 and 5;
• from city 4 to city 5; and
• from city 5 to nowhere.

Therefore, there are three paths to travel from city 1 to city 5:

• path 1 : city 1 \to city 2 \to city 4 \to city 5;
• path 2 : city 1 \to city 3 \to city 4 \to city 5; and
• path 3 : city 1 \to city 3 \to city 5.

Among these paths,

• two paths, path 2 and path 3, do not visit city 2. Among them, path 3 requires the minimum number of teleporter uses (twice).
• Path 1 is the only path without city 3. It requires using a teleporter three times.
• Path 3 is the only path without city 4. It requires using a teleporter twice.

Thus, 2, 3, and 2, separated by spaces, should be printed.

Sample Input 2

6 3
101
001
101
000
100
000

Sample Output 2

-1 3 3 -1

The only path from city 1 to city 6 is city 1 \to city 2 \to city 5 \to city 6.
For k=2,5, there is no way to travel from city 1 to city 6 without visiting city k.
For k=3,4, the path above satisfies the condition; it requires using a teleporter three times.

Thus, -1, 3, 3, and -1, separated by spaces, should be printed.

Note that a teleporter is one-way; a teleporter can send you from city 3 to city 4, but not from city 4 to city 3,
so the following path, for example, is invalid: city 1 \to city 4 \to city 3 \to city 6.