Problem Statement

You are given a string S consisting of uppercase and lowercase English letters. Print the string obtained by concatenating only the uppercase letters of S in their original order.

Constraints

• S is a string of uppercase and lowercase English letters.
• The length of S is between 1 and 100, inclusive.

Sample Input 1

AtCoderBeginnerContest

Sample Output 1

ACBC

The string obtained by concatenating only the uppercase letters of S in their original order is ACBC. Hence, print ACBC.

Sample Input 2

PaymentRequired

Sample Output 2

PR

Sample Input 3

program

Sample Output 3

Note that S may contain no uppercase letters.

Problem Statement

You are given a string S of length between 1 and 25 consisting of lowercase English letters.
Output one lowercase English letter that does not appear in S.
If there are multiple such letters, you may output any one of them.

Constraints

• S is a string of length between 1 and 25 (inclusive) consisting of lowercase English letters.

Sample Input 1

a

Sample Output 1

d

S= a.
Any lowercase English letter other than a (that is, b, c, …, or z) is a correct answer.

Sample Input 2

abcdfhijklmnopqrstuvwxyz

Sample Output 2

e

The lowercase English letters not included in S are e and g.

Sample Input 3

qazplwsxokmedcijnrfvuhbgt

Sample Output 3

y

Problem Statement

You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.

Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.

Constraints

• 1 \leq N, M \leq 1000
• N and M are integers.
• S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
• T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.

Sample Input 1

3 3
142857
004159
071028
159
287
857

Sample Output 1

2

The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.

Thus, the answer is 2.

Sample Input 2

5 4
235983
109467
823476
592801
000333
333
108
467
983

Sample Output 2

3

Sample Input 3

4 4
000000
123456
987111
000000
000
111
999
111

Sample Output 3

3

Problem Statement

People 1,2,\dots,N (where N is odd) conducted M votes where each person chooses either 0 or 1.
Each person's vote for each round is given as N strings S_1,S_2,\dots,S_N of length M consisting of 0 and 1, where the j-th character of S_i represents person i's vote content for the j-th vote.

In each vote, people who were in the minority receive 1 point.
More precisely, points are given according to the following rules:

• Suppose x people chose 0 and y people chose 1 in that vote.
  • If x=0 or y=0, everyone receives 1 point for that vote.
  • Otherwise, if x<y, only people who voted 0 in that vote receive 1 point.
  • Otherwise, only people who voted 1 in that vote receive 1 point.
  • Note that since N is odd, x=y never occurs.

After finishing M votes, find all people who have the highest total score from those votes.

Constraints

• N is an odd number satisfying 1 \le N \le 99.
• M is an integer satisfying 1 \le M \le 100.
• S_i is a string of length M consisting of 0 and 1.

Sample Input 1

3 5
11100
10101
01110

Sample Output 1

2 3

In this case, three people conducted five votes.

• In the 1st vote, person 1 voted 1, person 2 voted 1, person 3 voted 0. Thus, only person 3 receives 1 point.
• In the 2nd vote, person 1 voted 1, person 2 voted 0, person 3 voted 1. Thus, only person 2 receives 1 point.
• In the 3rd vote, person 1 voted 1, person 2 voted 1, person 3 voted 1. Thus, everyone receives 1 point.
• In the 4th vote, person 1 voted 0, person 2 voted 0, person 3 voted 1. Thus, only person 3 receives 1 point.
• In the 5th vote, person 1 voted 0, person 2 voted 1, person 3 voted 0. Thus, only person 2 receives 1 point.

As a result, person 1 received a total of 1 points, person 2 received a total of 3 points, and person 3 received a total of 3 points.
Therefore, persons 2 and 3 have the highest total score. Output these in ascending order of person number.

Sample Input 2

5 4
0000
0000
0000
0000
0000

Sample Output 2

1 2 3 4 5

Sample Input 3

7 8
11010011
01000000
01111100
10111000
10011110
10100101
10010110

Sample Output 3

1 2 3

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

• Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

• 1\leq H \leq 100
• 2\leq W \leq 100
• H and W are integers.
• S_i is a string of length W consisting of . and T.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

Problem Statement

Takahashi and Aoki each have a toy made by attaching M cords to N balls.

In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.

Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.

• P is a permutation of (1, \dots, N).
• For every pair of integers i, j between 1 and N (inclusive), the following holds.
  • Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
• 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
• (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

4 4
1 2
1 3
1 4
3 4
1 3
1 4
2 3
3 4

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.

Sample Input 2

5 6
1 2
1 3
1 4
3 4
3 5
4 5
1 2
1 3
1 4
1 5
3 5
4 5

Sample Output 2

No

The two toys do not have the same shape.

Sample Input 3

8 0

Sample Output 3

Yes

Problem Statement

This is an interactive task (where your program and the judge interact via Standard Input and Output).

You are given an integer N and an odd number K.
The judge has a hidden length-N sequence A = (A_1, A_2, \dots, A_N) consisting of 0 and 1.

While you cannot directly access the elements of sequence A, you are allowed to ask the judge the following query at most N times.

• Choose distinct integers x_1, x_2, \dots, and x_K between 1 and N, inclusive, to ask the parity of A_{x_1} + A_{x_2} + \dots + A_{x_K}.

Determine (A_1, A_2, \dots, A_N) by at most N queries, and print the answer.
Here, the judge is adaptive. In other words, the judge may modify the contents of A as long as it is consistent with the responses to the past queries.
Therefore, your program is considered correct if the output satisfies the following condition, and incorrect otherwise:

• your program prints a sequence consistent with the responses to the queries so far, and that is the only such sequence.

Constraints

• 1 \leq K \lt N \leq 1000
• K is odd.
• A_i is 0 or 1.

Input and Output

This is an interactive task (where your program and the judge interact via Standard Input and Output).

First of all, receive N and K from Standard Input.

N K

Then, repeat asking queries until you can uniquely determine (A_1, A_2, \dots, A_N).
Each query should be printed to Standard Output in the following format, where x_1, x_2, \dots, and x_K are K distinct integers between 1 and N, inclusive.

? x_1 x_2 \dots x_K

The response to the query is given from Standard Input in the following format.

T

Here, T denotes the response to the query.

• T is 0 when A_{x_1} + A_{x_2} + \dots + A_{x_K} is even, and
• T is 1 when A_{x_1} + A_{x_2} + \dots + A_{x_K} is odd.

However, if x_1, x_2, \dots and x_K do not satisfy the constraints, or the number of queries exceeds N, then T is -1.

If the judge returns -1, your program is already considered incorrect, so terminate the program immediately.

When you can determine all the elements of A, print those elements in the following format, and terminate the program immediately.

! A_1 A_2 \dots A_N

Notes

• Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
• The verdict will be indeterminate if there is malformed output during the interaction or your program quits prematurely.
• Terminate the program immediately after printing the answer, or the verdict will be indeterminate.
• The judge for this problem is adaptive. This means that the judge may modify the contents of A as long as it is consistent with the responses to the past queries.

Sample Interaction

In the following interaction, N=5 and K=3. Note that the following output itself will result in WA.
Here, A = (1, 0, 1, 1, 0) is indeed consistent with the responses, but so is (0, 0, 1, 0, 0), so sequence A is not uniquely determined. Thus, this program is considered incorrect.

Problem Statement

There is a town divided into a grid of cells with H rows and W columns. The cell at the i-th row from the top and j-th column from the left is a passable space if S_{i,j} is . and a block if S_{i,j} is #.

Takahashi will go from his house to a fish market. His house is in the cell at the top-left corner, and the fish market is in the cell at the bottom-right corner.

Takahashi can move one cell up, down, left, or right to a passable cell. He cannot leave the town. He cannot enter a block, either. However, his physical strength allows him to destroy all blocks in a square region with 2\times 2 cells of his choice with one punch, making these cells passable.

Find the minimum number of punches needed for Takahashi to reach the fish market.

Constraints

• 2 \leq H,W \leq 500
• H and W are integers.
• S_{i,j} is . or #.
• S_{1,1} and S_{H,W} are ..

Sample Input 1

5 5
..#..
#.#.#
##.##
#.#.#
..#..

Sample Output 1

1

He can reach the fish market by, for example, destroying the blocks in the square region with 2\times 2 cells marked * below.

..#..
#.**#
##**#
#.#.#
..#..

It is not required that all of the 2\times 2 cells in the region to punch are blocks.

Sample Input 2

5 7
.......
######.
.......
.######
.......

Sample Output 2

0

He can reach the fish market without destroying blocks, though he has to go a long way around.

Sample Input 3

8 8
.#######
########
########
########
########
########
########
#######.

Sample Output 3

5

Problem Statement

The Republic of AtCoder has N islands. Initially, none of the islands has an airport or harbor, and there is no road between any two of them. Takahashi, the king, will provide some means of transportation between these islands. Specifically, he can do the following operations any number of times in any order.

• Choose an integer i such that 1\leq i\leq N and pay a cost of X_i to build an airport on island i.
• Choose an integer i such that 1\leq i\leq N and pay a cost of Y_i to build a harbor on island i.
• Choose an integer i such that 1\leq i\leq M and pay a cost of Z_i to build a road that bidirectionally connects island A_i and island B_i.

Takahashi's objective is to make it possible, for every pair of different islands U and V, to reach island V from island U when one can perform the following actions any number of times in any order.

• When islands S and T both have airports, go from island S to island T.
• When islands S and T both have harbors, go from island S to island T.
• When islands S and T are connected by a road, go from island S to island T.

Find the minimum total cost Takahashi needs to pay to achieve his objective.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1\leq X_i\leq 10^9
• 1\leq Y_i\leq 10^9
• 1\leq A_i<B_i\leq N
• 1\leq Z_i\leq 10^9
• (A_i,B_i)\neq (A_j,B_j), if i\neq j.
• All values in the input are integers.

Sample Input 1

4 2
1 20 4 7
20 2 20 3
1 3 5
1 4 6

Sample Output 1

16

Takahashi will build the following infrastructure.

• Pay a cost of X_1=1 to build an airport on island 1.
• Pay a cost of X_3=4 to build an airport on island 3.
• Pay a cost of Y_2=2 to build a harbor on island 2.
• Pay a cost of Y_4=3 to build a harbor on island 4.
• Pay a cost of Z_2=6 to build a road connecting island 1 and island 4.

Then, the objective will be achieved at a cost of 16. There is no way to achieve the objective for a cost of 15 or less, so 16 should be printed.

Sample Input 2

3 1
1 1 1
10 10 10
1 2 100

Sample Output 2

3

It is not mandatory to build all three types of facilities at least once.

Sample Input 3

7 8
35 29 36 88 58 15 25
99 7 49 61 67 4 57
2 3 3
2 5 36
2 6 89
1 6 24
5 7 55
1 3 71
3 4 94
5 6 21

Sample Output 3

160