Problem Statement

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

• 1 \leq a, b, c \leq 100
• All values in input are integers.

Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.

Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.

Sample Input 3

100 100 100

Sample Output 3

Yes

Problem Statement

You are given positive integers N and M.

If the following operation is repeated while the value of M is not 0, find the number of operations performed.

• Let x be the remainder when N is divided by M. Replace the value of M with x.

It can be proved that M becomes 0 after a finite number of operations.

Constraints

• 1 \leq N, M \leq 1000
• All input values are integers.

Sample Input 1

8 5

Sample Output 1

3

Initially, N = 8 and M = 5.

The remainder when 8 is divided by 5 is 3, so M = 3 after one operation.

The remainder when 8 is divided by 3 is 2, so M = 2 after two operations.

The remainder when 8 is divided by 2 is 0, so M = 0 after three operations.

Thus, output 3 as the answer.

Sample Input 2

14 6

Sample Output 2

2

Sample Input 3

460 33

Sample Output 3

5

Problem Statement

The AtCoder country has two official languages: Takahashi-go and Aoki-go.

Both Takahashi-go and Aoki-go use some lowercase English letters to write words in those languages. Takahashi-go uses only the characters contained in a string S of length N, and Aoki-go uses only the characters contained in a string T of length M.

You are given Q words w _ 1,w _ 2,\ldots,w _ Q that are in the official languages of the AtCoder country. For each word, determine which of the following applies based on the characters contained in that word:

• It is confirmed to be a word in Takahashi-go
• It is confirmed to be a word in Aoki-go
• Neither can be determined

Constraints

• 1\le N\le26
• 1\le M\le26
• S is a string of length N consisting of lowercase English letters.
• The characters in S are arranged in alphabetical order.
• All characters in S are distinct.
• T is a string of length M consisting of lowercase English letters.
• The characters in T are arranged in alphabetical order.
• All characters in T are distinct.
• 1\le Q\le100
• w _ i is a string of length at least 1 and at most 100 consisting of lowercase English letters. (1\le i\le Q)
• w _ i is a word in Takahashi-go or Aoki-go. (1\le i\le Q)
• N,M,Q are integers.

Sample Input 1

6 5
ahikst
aikot
5
asahi
okita
kiai
hash
it

Sample Output 1

Takahashi
Aoki
Unknown
Takahashi
Unknown

For example, all of a, s, h, i are used in Takahashi-go, and h is not used in Aoki-go, so it is confirmed that asahi is a word in Takahashi-go. Thus, print Takahashi on the first line.

Both i and t are used in both Takahashi-go and Aoki-go, so it cannot be determined whether it is a word in Takahashi-go or Aoki-go. Thus, print Unknown on the fifth line.

Sample Input 2

7 6
ahiknst
ahikos
5
kioki
ohiki
tashi
nishi
kashi

Sample Output 2

Aoki
Aoki
Takahashi
Takahashi
Unknown

o is not used in Takahashi-go, so the first two words are confirmed to be words in Aoki-go. Thus, print Aoki on the first and second lines.

t and n are not used in Aoki-go, so the following two words are confirmed to be words in Takahashi-go. Thus, print Takahashi on the third and fourth lines.

For the first four words, there is a rule that words ending in shi are Takahashi-go, and words ending in ki are Aoki-go. However, all of k, a, s, h, i are used in both Takahashi-go and Aoki-go, so it is impossible to determine which language the word kashi belongs to based on the characters used. Thus, print Unknown on the fifth line.

Sample Input 3

13 11
defghiqsvwxyz
acejmoqrtwx
15
qhsqzhd
jcareec
wwqxqew
wxqxwex
jxxrtwa
trtqjxe
sqyggse
xxqwxew
xewwxxw
wwqxwex
xqqxqwq
qxxexxe
teqeroc
eeeqqee
vxdevyy

Sample Output 3

Takahashi
Aoki
Unknown
Unknown
Aoki
Aoki
Takahashi
Unknown
Unknown
Unknown
Unknown
Unknown
Aoki
Unknown
Takahashi

Problem Statement

N examinees took an entrance exam.
The examinee numbered i scored A_i points in math and B_i points in English.

The admissions are determined as follows.

1. X examinees with the highest math scores are admitted.
2. Then, among the examinees who are not admitted yet, Y examinees with the highest English scores are admitted.
3. Then, among the examinees who are not admitted yet, Z examinees with the highest total scores in math and English are admitted.
4. Those examinees who are not admitted yet are rejected.

Here, in each of the steps 1. to 3., ties are broken by examinees' numbers: an examinee with the smaller examinee's number is prioritized. See also Sample Input and Output.

Print the examinees' numbers of the admitted examinees determined by the steps above in ascending order, separated by newlines.

Constraints

• All values in input are integers.
• 1 \le N \le 1000
• 0 \le X,Y,Z \le N
• 1 \le X+Y+Z \le N
• 0 \le A_i,B_i \le 100

Sample Input 1

6 1 0 2
80 60 80 60 70 70
40 20 50 90 90 80

Sample Output 1

1
4
5

• First, 1 examinee with the highest math score is admitted.
  • Examinee 1 is tied with Examinee 3, scoring the highest 80 points in math, and the tie is broken by the examinees' numbers, so Examinee 1 is admitted.
• Then, among the examinees who are not admitted yet, 0 examinees with the highest English scores are admitted.
  • Obviously, it does not affect the admissions.
• Then, among the examinees who are not admitted yet, 2 examinees with the highest total scores in math and English are admitted.
  • First, among the examinees who are not admitted yet, Examinee 5 is admitted, scoring the highest total score of 160 points.
  • Next, among the examinees who are not admitted yet, Examinee 4 is tied with Examinee 6, scoring a total score of 150 points. The tie is broken by the examinees' numbers, and Examinee 4 is admitted.

Therefore, the examinees' numbers of the admitted examinees are 1, 4, and 5. Print them in ascending order.

Sample Input 2

5 2 1 2
0 100 0 100 0
0 0 100 100 0

Sample Output 2

1
2
3
4
5

All examinees may be admitted.

Sample Input 3

15 4 3 2
30 65 20 95 100 45 70 85 20 35 95 50 40 15 85
0 25 45 35 65 70 80 90 40 55 20 20 45 75 100

Sample Output 3

2
4
5
6
7
8
11
14
15

Problem Statement

There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:

• M \geq 2
• The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
• The edge from vertex B_M to vertex B_1 exists.
• If i \neq j, then B_i \neq B_j.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N
• A_i \neq i

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.

Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

4

The figure below shows the table after one operation.

Here, there are four happy people:

• Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
• Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
• Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

There cannot be five or more happy people, so the answer is 4.

Sample Input 2

3
0 1 2

Sample Output 2

3

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

5

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

Takahashi is with N animals. The N animals are called Animal 1, Animal 2, \ldots, Animal N.

Takahashi will perform the following N kinds of action. Each action can be performed any number of (possibly zero) times.

• Pay A_1 yen (the currency in Japan) to feed Animals 1 and 2.
• Pay A_2 yen to feed Animals 2 and 3.
• Pay A_3 yen to feed Animals 3 and 4.
• \cdots
• Pay A_i yen to feed Animals i and (i+1).
• \cdots
• Pay A_{N-2} yen to feed Animals (N-2) and (N-1).
• Pay A_{N-1} yen to feed Animals (N-1) and N.
• Pay A_N yen to feed Animals N and 1.

Note that the N-th action above feeds "Animals N and 1."

Print the minimum possible total cost to feed every animal at least once.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

5
2 5 3 2 5

Sample Output 1

7

If Takahashi performs the 1-st, 3-rd, and 4-th actions once each, Animals 1, 2, 3, 4, and 5 are fed once, once, once, twice, once, respectively, so every animal is fed at least once. The total cost to do so is A_1 + A_3 + A_4 = 2 + 3 + 2 = 7 yen, which is the minimum possible.

Sample Input 2

20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62

Sample Output 2

426

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.