Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

1. Let N be the current length of S, and S = S_1S_2\ldots S_N.
2. Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)
3. Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

• Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

• First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
• Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
• Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Find the number of non-empty substrings of S that are repetitions of one character. Here, two substrings that are equal as strings are not distinguished even if they are obtained differently.

A non-empty substring of S is a string of length at least one obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S. For example, ab and abc are non-empty substrings of abc, while ac and the empty string are not.

Constraints

• 1 \leq N \leq 2\times 10^5
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
aaabaa

Sample Output 1

4

The non-empty substrings of S that are repetitions of one character are a, aa, aaa, and b; there are four of them. Note that there are multiple ways to obtain a or aa from S, but each should only be counted once.

Sample Input 2

1
x

Sample Output 2

1

Sample Input 3

12
ssskkyskkkky

Sample Output 3

8

Problem Statement

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

Each cell contains one of the characters o, x, and .. The characters written in each cell are represented by H strings S_1, S_2, \ldots, S_H of length W; the character written in cell (i, j) is the j-th character of the string S_i.

For this grid, you may repeat the following operation any number of times, possibly zero:

• Choose one cell with the character . and change the character in that cell to o.

Determine if it is possible to have a sequence of K horizontally or vertically consecutive cells with o written in all cells (in other words, satisfy at least one of the following two conditions). If it is possible, print the minimum number of operations required to achieve this.

• There is an integer pair (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W-K+1 such that the characters in cells (i, j), (i, j+1), \ldots, (i, j+K-1) are all o.
• There is an integer pair (i, j) satisfying 1 \leq i \leq H-K+1 and 1 \leq j \leq W such that the characters in cells (i, j), (i+1, j), \ldots, (i+K-1, j) are all o.

Constraints

• H, W, and K are integers.
• 1 \leq H
• 1 \leq W
• H \times W \leq 2 \times 10^5
• 1 \leq K \leq \max\lbrace H, W \rbrace
• S_i is a string of length W consisting of the characters o, x, and ..

Sample Input 1

3 4 3
xo.x
..o.
xx.o

Sample Output 1

2

By operating twice, for example, changing the characters in cells (2, 1) and (2, 2) to o, you can satisfy the condition in the problem statement, and this is the minimum number of operations required.

Sample Input 2

4 2 3
.o
.o
.o
.o

Sample Output 2

0

The condition is satisfied without performing any operations.

Sample Input 3

3 3 3
x..
..x
.x.

Sample Output 3

-1

It is impossible to satisfy the condition, so print -1.

Sample Input 4

10 12 6
......xo.o..
x...x.....o.
x...........
..o...x.....
.....oo.....
o.........x.
ox.oox.xx..x
....o...oox.
..o.....x.x.
...o........

Sample Output 4

3

Problem Statement

You are given a simple directed graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i is a directed edge from vertex u_i to vertex v_i.

You may perform the following operation zero or more times.

• Choose distinct vertices x and y such that there is no directed edge from vertex x to vertex y, and add a directed edge from vertex x to vertex y.

Find the minimum number of times you need to perform the operation to make the graph satisfy the following condition.

• For every triple of distinct vertices a, b, and c, if there are directed edges from vertex a to vertex b and from vertex b to vertex c, there is also a directed edge from vertex a to vertex c.

Constraints

• 3 \leq N \leq 2000
• 0 \leq M \leq 2000
• 1 \leq u_i ,v_i \leq N
• u_i \neq v_i
• (u_i,v_i) \neq (u_j,v_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4 3
2 4
3 1
4 3

Sample Output 1

3

Initially, the condition is not satisfied because, for instance, for vertices 2, 4, and 3, there are directed edges from vertex 2 to vertex 4 and from vertex 4 to vertex 3, but not from vertex 2 to vertex 3.

You can make the graph satisfy the condition by adding the following three directed edges:

• one from vertex 2 to vertex 3,
• one from vertex 2 to vertex 1, and
• one from vertex 4 to vertex 1.

On the other hand, the condition cannot be satisfied by adding two or fewer edges, so the answer is 3.

Sample Input 2

292 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

12

Problem Statement

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

You and the judge will follow the procedure below. The procedure consists of phases 1 and 2; phase 1 is immediately followed by phase 2.

(Phase 1)

• The judge decides an integer N between 1 and 10^9 (inclusive), which is hidden.
• You print an integer M between 1 and 110 (inclusive).
• You also print an integer sequence A=(A_1,A_2,\ldots,A_M) of length M such that 1 \leq A_i \leq M for all i = 1, 2, \ldots, M.

(Phase 2)

• The judge gives you an integer sequence B=(B_1,B_2,\ldots,B_M) of length M. Here, B_i = f^N(i). f(i) is defined by f(i)=A_i for all integers i between 1 and M (inclusive), and f^N(i) is the integer resulting from replacing i with f(i) N times.
• Based on the given B, you identify the integer N that the judge has decided, and print N.

After the procedure above, terminate the program immediately to be judged correct.

Constraints

• N is an integer between 1 and 10^9 (inclusive).

Input and Output

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

(Phase 1)

• First, print an integer M between 1 and 110 (inclusive). It must be followed by a newline.

M

• Then, print a sequence A=(A_1,A_2,\ldots,A_M) of length M consisting of integers between 1 and M (inclusive), with spaces in between. It must be followed by a newline.

A_1 A_2 \ldots A_M

(Phase 2)

• First, an integer sequence B=(B_1,B_2,\ldots,B_M) of length M is given from the input.

B_1 B_2 \ldots B_M

• Find the integer N and print it. It must be followed by a newline.

N

If you print something illegal, the judge prints -1. In that case, your submission is already considered incorrect. Since the judge program terminates at this point, it is desirable that your program terminates too.

Notes

• After each output, add a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
• If an invalid output is printed during the interaction, or if the program terminates halfway, the verdict will be indeterminate.
• After you print the answer (or you receive -1), immediately terminate the program normally. Otherwise, the verdict will be indeterminate.
• Note that an excessive newline is also considered an invalid input.

Sample Interaction

The following is a sample interaction with N = 2.