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: