Problem Statement

N people, person 1, person 2, \ldots, person N, are playing roulette. The outcome of a spin is one of the 37 integers from 0 to 36. For each i = 1, 2, \ldots, N, person i has bet on C_i of the 37 possible outcomes: A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i}.

The wheel has been spun, and the outcome is X. Print the numbers of all people who have bet on X with the fewest bets, in ascending order.

More formally, print all integers i between 1 and N, inclusive, that satisfy both of the following conditions, in ascending order:

• Person i has bet on X.
• For each j = 1, 2, \ldots, N, if person j has bet on X, then C_i \leq C_j.

Note that there may be no number to print (see Sample Input 2).

Constraints

• 1 \leq N \leq 100
• 1 \leq C_i \leq 37
• 0 \leq A_{i, j} \leq 36
• A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} are all different for each i = 1, 2, \ldots, N.
• 0 \leq X \leq 36
• All input values are integers.

Sample Input 1

4
3
7 19 20
4
4 19 24 0
2
26 10
3
19 31 24
19

Sample Output 1

2
1 4

The wheel has been spun, and the outcome is 19. The people who has bet on 19 are person 1, person 2, and person 4, and the number of their bets are 3, 4, and 3, respectively. Therefore, among the people who has bet on 19, the ones with the fewest bets are person 1 and person 4.

Sample Input 2

3
1
1
1
2
1
3
0

Sample Output 2

0

The wheel has been spun and the outcome is 0, but no one has bet on 0, so there is no number to print.

Problem Statement

Takahashi generated 10 strings S_1,S_2,\dots,S_{10} as follows.

• First, let S_i (1 \le i \le 10)= .......... (10 .s in a row).
• Next, choose four integers A, B, C, and D satisfying all of the following.
  • 1 \le A \le B \le 10.
  • 1 \le C \le D \le 10.
• Then, for every pair of integers (i,j) satisfying all of the following, replace the j-th character of S_i with #.
  • A \le i \le B.
  • C \le j \le D.

You are given S_1,S_2,\dots,S_{10} generated as above. Find the integers A, B, C, and D Takahashi chose.
It can be proved that such integers A, B, C, and D uniquely exist (there is just one answer) under the Constraints.

Constraints

• S_1,S_2,\dots,S_{10} are strings, each of length 10, that can be generated according to the Problem Statement.

Sample Input 1

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

Sample Output 1

5 8
4 9

Here, Takahashi chose A=5, B=8, C=4, D=9.
This choice generates 10 strings S_1,S_2,\dots,S_{10}, each of length 10, where the 4-th through 9-th characters of S_5,S_6,S_7,S_8 are #, and the other characters are ..
These are equal to the strings given in the input.

Sample Input 2

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

Sample Output 2

2 2
3 3

Sample Input 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

Sample Output 3

1 10
1 10

Problem Statement

2N players, with ID numbers 1 through 2N, will participate in a rock-scissors-paper contest.

The contest has M rounds. Each round has N one-on-one matches, where each player plays in one of them.

For each i=0, 1, \ldots, M, the players' ranks at the end of the i-th round are determined as follows.

• A player with more wins in the first i rounds ranks higher.
• Ties are broken by ID numbers: a player with a smaller ID number ranks higher.

Additionally, for each i=1, \ldots, M, the matches in the i-th round are arranged as follows.

• For each k=1, 2, \ldots, N, a match is played between the players who rank (2k-1)-th and 2k-th at the end of the (i-1)-th round.

In each match, the two players play a hand just once, resulting in one player's win and the other's loss, or a draw.

Takahashi, who can foresee the future, knows that Player i will play A_{i, j} in their match in the j-th round, where A_{i,j} is G, C, or P.
Here, G stands for rock, C stands for scissors, and P stands for paper. (These derive from Japanese.)

Find the players' ranks at the end of the M-th round.

Constraints

• 1 \leq N \leq 50
• 1 \leq M \leq 100
• A_{i,j} is G, C, or P.

Sample Input 1

2 3
GCP
PPP
CCC
PPC

Sample Output 1

3
1
2
4

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. Player 3 wins the former, and Player 1 wins the latter.
In the third round, matches are played between Players 3 and 1, and between Players 2 and 4. Player 3 wins the former, and Player 4 wins the latter.
Therefore, in the end, the players are ranked in the following order: 3,1,2,4, from highest to lowest.

Sample Input 2

2 2
GC
PG
CG
PP

Sample Output 2

1
2
3
4

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. The former is drawn, and Player 1 wins the latter.
Therefore, in the end, the players are ranked in the following order: 1,2,3,4, from highest to lowest.

Problem Statement

There are N stations on a certain line operated by AtCoder Railway. The i-th station (1 \leq i \leq N) from the starting station is named S_i.

Local trains stop at all stations, while express trains may not. Specifically, express trains stop at only M \, (M \leq N) stations, and the j-th stop (1 \leq j \leq M) is the station named T_j.
Here, it is guaranteed that T_1 = S_1 and T_M = S_N, that is, express trains stop at both starting and terminal stations.

For each of the N stations, determine whether express trains stop at that station.

Constrains

• 2 \leq M \leq N \leq 10^5
• N and M are integers.
• S_i (1 \leq i \leq N) is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
• S_i \neq S_j \, (i \neq j)
• T_1 = S_1 and T_M = S_N.
• (T_1, \dots, T_M) is obtained by removing zero or more strings from (S_1, \dots, S_N) and lining up the remaining strings without changing the order.

Sample Input 1

5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

Sample Output 1

Yes
No
Yes
No
Yes

Sample Input 2

7 7
a t c o d e r
a t c o d e r

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes
Yes

Express trains may stop at all stations.

Problem Statement

Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.

Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.

Constraints

• 1\leq N\leq 50
• 1\leq X\leq 10^4
• 1\leq A_i\leq 100
• 1\leq B_i\leq 50
• A_i are pairwise distinct.
• All values in the input are integers.

Sample Input 1

2 19
2 3
5 6

Sample Output 1

Yes

Takahashi has three 2-yen coins and six 5-yen coins. He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen. Thus, Yes should be printed.

Sample Input 2

2 18
2 3
5 6

Sample Output 2

No

There is no combination of the coins that he can use to pay exactly 18 yen. Thus, No should be printed.

Sample Input 3

3 1001
1 1
2 1
100 10

Sample Output 3

Yes

He need not use all kinds of coins.