Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

There are N users on WAtCoder, numbered from 1 to N, and M contest pages, numbered from 1 to M. Initially, no user has view permission for any contest page.

You are given Q queries to process in order. Each query is of one of the following three types:

• 1 X Y: Grant user X view permission for contest page Y.
• 2 X: Grant user X view permission for all contest pages.
• 3 X Y: Answer whether user X can view contest page Y.

It is possible for a user to be granted permission for the same contest page multiple times.

Constraints

• 1 \le N \le 2\times 10^5
• 1 \le M \le 2\times 10^5
• 1 \le Q \le 2\times 10^5
• 1 \le X \le N
• 1 \le Y \le M
• All input values are integers.

Sample Input 1

2 3 5
1 1 2
3 1 1
3 1 2
2 2
3 2 3

Sample Output 1

No
Yes
Yes

• In the first query, user 1 is granted permission to view contest page 2.
• At the second query, user 1 can view only page 2; they cannot view page 1, so print No.
• At the third query, user 1 can view page 2, so print Yes.
• In the fourth query, user 2 is granted permission to view all pages.
• At the fifth query, user 2 can view pages 1,2,3; they can view page 3, so print Yes.

Sample Input 2

5 5 10
2 2
3 4 4
1 1 1
1 4 1
1 4 2
1 4 4
1 2 4
3 3 2
3 5 4
3 2 1

Sample Output 2

No
No
No
Yes

Problem Statement

You initially have an empty string S.
Additionally, there are bags 1, 2, \dots, N, each containing some strings.
Bag i contains A_i strings S_{i,1}, S_{i,2}, \dots, S_{i,A_i}.

You will repeat the following steps for i = 1, 2, \dots, N:

• Choose and perform one of the following two actions:
  • Pay 1 yen, select exactly one string from bag i, and concatenate it to the end of S.
  • Do nothing.

Given a string T, find the minimum amount of money required to make the final S equal T.
If there is no way to make the final S equal T, print -1.

Constraints

• T is a string consisting of lowercase English letters with length between 1 and 100, inclusive.
• N is an integer between 1 and 100, inclusive.
• A_i is an integer between 1 and 10, inclusive.
• S_{i,j} is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Sample Input 1

abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de

Sample Output 1

2

For example, doing the following makes the final S equal T with two yen, which can be shown to be the minimum amount required.

• For i=1, select abc from bag 1 and concatenate it to the end of S, making S= abc.
• For i=2, do nothing.
• For i=3, select de from bag 3 and concatenate it to the end of S, making S= abcde.

Sample Input 2

abcde
3
2 ab abc
3 f c bcde
1 e

Sample Output 2

-1

There is no way to make the final S equal T, so print -1.

Sample Input 3

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

Sample Output 3

4

Problem Statement

There are N 7's drawn in the first quadrant of a plane.

The i-th 7 is a figure composed of a segment connecting (x_i-1,y_i) and (x_i,y_i), and a segment connecting (x_i,y_i-1) and (x_i,y_i).

You can choose zero or more from the N 7's and delete them.

What is the maximum possible number of 7's that are wholly visible from the origin after the optimal deletion?

Here, the i-th 7 is wholly visible from the origin if and only if:

• the interior (excluding borders) of the quadrilateral whose vertices are the origin, (x_i-1,y_i), (x_i,y_i), (x_i,y_i-1) does not intersect with the other 7's.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq x_i,y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3
1 1
2 1
1 2

Sample Output 1

2

If the first 7 is deleted, the other two 7's ― the second and third ones ― will be wholly visible from the origin, which is optimal.

If no 7's are deleted, only the first 7 is wholly visible from the origin.

Sample Input 2

10
414598724 87552841
252911401 309688555
623249116 421714323
605059493 227199170
410455266 373748111
861647548 916369023
527772558 682124751
356101507 249887028
292258775 110762985
850583108 796044319

Sample Output 2

10

It is best to keep all 7's.

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.