Problem Statement

Takahashi wants a beverage called AtCoder Drink in a restaurant. It can be ordered at a regular price of P yen.

He also has a discount coupon that allows him to order it at a lower price of Q yen. However, he must additionally order one of the restaurant's N dishes to use that coupon. For each i = 1, 2, \ldots, N, the price of the i-th dish is D_i yen.

Print the minimum total amount of money that he must pay to get the drink.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \lt P \leq 10^5
• 1 \leq D_i \leq 10^5
• All input values are integers.

Sample Input 1

3 100 50
60 20 40

Sample Output 1

70

If he uses the coupon and orders the second dish, he can get the drink by paying 50 yen for it and 20 yen for the dish, for a total of 70 yen, which is the minimum total payment needed.

Sample Input 2

3 100 50
60000 20000 40000

Sample Output 2

100

The total payment will be minimized by not using the coupon and paying the regular price of 100 yen.

Problem Statement

You are given a string S of length N consisting of three kinds of characters: ., |, and *. S contains exactly two | and exactly one *.

Determine whether the * is between the two |, and if so, print in; otherwise, print out.

More formally, determine whether one of the characters before the * is | and one of the characters after the * is |.

Constraints

• 3\leq N\leq 100
• N is an integer.
• S is a string of length N consisting of ., |, and *.
• S contains exactly two |.
• S contains exactly one *.

Sample Input 1

10
.|..*...|.

Sample Output 1

in

Between the two |, we have |..*...|, which contains *, so you should print in.

Sample Input 2

10
.|..|.*...

Sample Output 2

out

Between the two |, we have |..|, which does not contain *, so you should print out.

Sample Input 3

3
|*|

Sample Output 3

in

Problem Statement

You are given positive integers A and B.
Let us calculate A+B (in decimal). If it does not involve a carry, print Easy; if it does, print Hard.

Constraints

• A and B are integers.
• 1 \le A,B \le 10^{18}

Sample Input 1

229 390

Sample Output 1

Hard

When calculating 229+390, we have a carry from the tens digit to the hundreds digit, so the answer is Hard.

Sample Input 2

123456789 9876543210

Sample Output 2

Easy

We do not have a carry here; the answer is Easy.
Note that the input may not fit into a 32-bit integer.

Problem Statement

Takahashi wants to manage the waiting line in front of the AtCoder Restaurant. Initially, the waiting line is empty. Each person who joins the line holds a meal ticket with the menu number of the dish they will order.

Process Q queries in order. There are two types of queries, given in the following formats:

• 1 X: One person joins the end of the waiting line holding a ticket with menu number X.
• 2: Takahashi guides the person at the front of the waiting line into the restaurant. Print the menu number on that person’s ticket.

Constraints

• 1 \leq Q \leq 100
• 1 \leq X \leq 100
• For each query of the second type, there is at least one person in the line before guiding.
• All input values are integers.

Sample Input 1

6
1 3
1 1
1 15
2
1 3
2

Sample Output 1

3
1

Initially, the waiting line is empty.

• For the first query, a person holding a ticket with menu number 3 joins the end of the line. The sequence of menu numbers held by people in line from front to back is 3.
• For the second query, a person holding a ticket with menu number 1 joins the end of the line. The sequence becomes 3,1.
• For the third query, a person holding a ticket with menu number 15 joins the end of the line. The sequence becomes 3,1,15.
• For the fourth query, guide the person at the front into the restaurant. That person holds menu number 3, so print 3. The sequence becomes 1,15.
• For the fifth query, a person holding a ticket with menu number 3 joins the end of the line. The sequence becomes 1,15,3.
• For the sixth query, guide the person at the front into the restaurant. That person holds menu number 1, so print 1. The sequence becomes 15,3.

Sample Input 2

7
1 3
1 1
1 4
1 1
1 5
1 9
1 2

Sample Output 2

Note that there may be no queries of the second type.

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

• Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

• 1\leq N \leq 10^5
• 1 \leq A_j \leq N
• i occurs in A exactly three times, for each i=1,2,\dots,N.
• All input values are integers.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

• 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
• 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
• 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3 4 1 2

Problem Statement

You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

Constraints

• 1 \le N \le 15
• 1 \le K \le N
• N and K are integers.
• S_i is a non-empty string consisting of lowercase English alphabets.
• For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
• If i \neq j, then S_i \neq S_j.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

3

When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

Sample Input 2

2 2
a
b

Sample Output 2

0

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy

Sample Output 3

7

Problem Statement

You are given N circles on the xy-coordinate plane. For each i = 1, 2, \ldots, N, the i-th circle is centered at (x_i, y_i) and has a radius of r_i.

Determine whether it is possible to get from (s_x, s_y) to (t_x, t_y) by only passing through points that lie on the circumference of at least one of the N circles.

Constraints

• 1 \leq N \leq 3000
• -10^9 \leq x_i, y_i \leq 10^9
• 1 \leq r_i \leq 10^9
• (s_x, s_y) lies on the circumference of at least one of the N circles.
• (t_x, t_y) lies on the circumference of at least one of the N circles.
• All values in input are integers.

Sample Input 1

4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3

Sample Output 1

Yes

Here is one way to get from (0, -2) to (3, 3).

• From (0, -2), pass through the circumference of the 1-st circle counterclockwise to reach (1, -\sqrt{3}).
• From (1, -\sqrt{3}), pass through the circumference of the 2-nd circle clockwise to reach (2, 2).
• From (2, 2), pass through the circumference of the 3-rd circle counterclockwise to reach (3, 3).

Thus, Yes should be printed.

Sample Input 2

3
0 1 0 3
0 0 1
0 0 2
0 0 3

Sample Output 2

No

It is impossible to get from (0, 1) to (0, 3) by only passing through points on the circumference of at least one of the circles, so No should be printed.

Problem Statement

You are given integers N, M and an integer sequence A=(A_1,A_2,\ldots,A_N) of length N where each element is between 1 and M, inclusive.

The following operation is performed 10^{100} times on this integer sequence A:

• Let v be the integer between 1 and M, inclusive, with the fewest occurrences in A. If there are multiple such v, take the smallest among them. Then, append v to the end of A.

You are given Q queries. The i-th query gives an integer X_i, so find the value of A_{X_i} after performing the operation 10^{100} times.

Constraints

• 1\le N,M\le 5\times 10^5
• 1\le A_i \le M
• 1\le Q\le 2\times 10^5
• 1\le X_i \le 10^{18}
• All input values are integers.

Sample Input 1

3 3
1 1 2
8
1
2
3
4
5
6
7
8

Sample Output 1

1
1
2
3
2
3
1
2

Initially, A=(1,1,2). With each operation, A changes as follows:

• First operation: The counts of 1, 2, 3 in A are 2, 1, 0 respectively, so v=3. Append v to the end of A, giving A=(1,1,2,3).
• Second operation: The counts of 1, 2, 3 in A are 2, 1, 1 respectively, so v=2. Append v to the end of A, giving A=(1,1,2,3,2).
• Third operation: The counts of 1, 2, 3 in A are 2, 2, 1 respectively, so v=3. Append v to the end of A, giving A=(1,1,2,3,2,3).
• \vdots

After performing the operation 10^{100} times, A becomes A=(1,1,2,3,2,3,1,2,\ldots).

Sample Input 2

7 30
20 26 3 14 4 4 9
10
31
9
21
23
97
99
30
79
57
3

Sample Output 2

30
2
18
21
7
9
29
19
27
3

Problem Statement

There is an empty array A. For i = 1,2,\ldots,N, perform the following operation in order:

• Insert the number i into A so that it becomes the P_i-th element from the beginning.
  • More precisely, replace A with the concatenation of the first P_i-1 elements of A, then i, then the remaining elements of A starting from the P_i-th element, in this order.

Output the final array A after all operations have been completed.

Constraints

• 1 \leq N \leq 5\times 10^5
• 1 \leq P_i \leq i
• All input values are integers.

Sample Input 1

4
1 1 2 1

Sample Output 1

4 2 3 1

The operations are performed as follows:

• Insert the number 1 so that it becomes the 1st element of A. Now, A = (1).
• Insert the number 2 so that it becomes the 1st element of A. Now, A = (2, 1).
• Insert the number 3 so that it becomes the 2nd element of A. Now, A = (2, 3, 1).
• Insert the number 4 so that it becomes the 1st element of A. Now, A = (4, 2, 3, 1).

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1 2 3 4 5