Problem Statement

You are given N strings.

The i-th string S_i (1 \leq i \leq N) is either Takahashi or Aoki.

How many i are there such that S_i is equal to Takahashi?

Constraints

• 1 \leq N \leq 100
• N is an integer.
• Each S_i is Takahashi or Aoki. (1 \leq i \leq N)

Sample Input 1

3
Aoki
Takahashi
Takahashi

Sample Output 1

2

S_2 and S_3 are equal to Takahashi, while S_1 is not.

Therefore, print 2.

Sample Input 2

2
Aoki
Aoki

Sample Output 2

0

It is possible that no S_i is equal to Takahashi.

Sample Input 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

Sample Output 3

7

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

Consider an xy-plane. The positive direction of the x-axis is in the direction of east, and the positive direction of the y-axis is in the direction of north.
Takahashi is initially at point (x, y) = (0, 0) and facing east (in the positive direction of the x-axis).

You are given a string T = t_1t_2\ldots t_N of length N consisting of S and R. Takahashi will do the following move for each i = 1, 2, \ldots, N in this order.

• If t_i = S, Takahashi advances in the current direction by distance 1.
• If t_i = R, Takahashi turns 90 degrees clockwise without changing his position. As a result, Takahashi's direction changes as follows.
  • If he is facing east (in the positive direction of the x-axis) before he turns, he will face south (in the negative direction of the y-axis) after he turns.
  • If he is facing south (in the negative direction of the y-axis) before he turns, he will face west (in the negative direction of the x-axis) after he turns.
  • If he is facing west (in the negative direction of the x-axis) before he turns, he will face north (in the positive direction of the y-axis) after he turns.
  • If he is facing north (in the positive direction of the y-axis) before he turns, he will face east (in the positive direction of the x-axis) after he turns.

Print the coordinates Takahashi is at after all the steps above have been done.

Constraints

• 1 \leq N \leq 10^5
• N is an integer.
• T is a string of length N consisting of S and R.

Sample Input 1

4
SSRS

Sample Output 1

2 -1

Takahashi is initially at (0, 0) facing east. Then, he moves as follows.

1. t_1 = S, so he advances in the direction of east by distance 1, arriving at (1, 0).
2. t_2 = S, so he advances in the direction of east by distance 1, arriving at (2, 0).
3. t_3 = R, so he turns 90 degrees clockwise, resulting in facing south.
4. t_4 = S, so he advances in the direction of south by distance 1, arriving at (2, -1).

Thus, Takahashi's final position, (x, y) = (2, -1), should be printed.

Sample Input 2

20
SRSRSSRSSSRSRRRRRSRR

Sample Output 2

0 1

Problem Statement

There are N stations 1, 2, \dots, N, arranged in a straight line from west to east in this order.
The AtCoder Railway train passes through these N stations and runs from west to east.
For any two integers i, j satisfying 1 \leq i \lt j \leq N, the cost of boarding the train at station i and getting off at station j is C_{i,j}.

Determine whether there exist three integers a, b, c such that:

• 1 \leq a \lt b \lt c \leq N
• The total cost of boarding the train at station a, getting off at station b, then boarding the train again at station b, and getting off at station c is less than the cost of boarding the train at station a and getting off at station c.

Constraints

• 3 \leq N \leq 100
• 1 \leq C_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

3
45 450
45

Sample Output 1

Yes

Choosing (a, b, c) = (1, 2, 3),
C_{a,b}+C_{b,c}=C_{1,2}+C_{2,3}=45+45
C_{a,c}=C_{1,3}=450
so the conditions are satisfied.

Sample Input 2

4
25 40 65
30 55
25

Sample Output 2

No

No choice of (a, b, c) satisfies the conditions.

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

• Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
• Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

• 1 \leq N \leq 10
• 1 \leq X \leq 5
• 1 \leq Y \leq 5
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

12

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

• First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
  • After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
• Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
  • After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
• He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

0

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There are N people, labeled 1 to N. Person i has an integer A_i.

Among the people who satisfy the condition "None of the other N-1 people has the same integer as themselves," find the one with the greatest integer, and print that person's label.

If no person satisfies the condition, report that fact instead.

Constraints

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

Sample Input 1

9
2 9 9 7 9 2 4 5 8

Sample Output 1

9

Those who satisfy the condition are the persons labeled 4, 7, 8, and 9.
Their integers are 7, 4, 5, and 8, respectively, and the person with the largest integer is the person labeled 9.
Thus, the answer is 9.

Sample Input 2

4
1000000000 1000000000 998244353 998244353

Sample Output 2

-1

If no person satisfies the condition, print -1.

Problem Statement

You are given an integer sequence A = (A_1, \dots, A_N) of length N.

Find the number of triplets of integers (i, j, k) satisfying all of the conditions below.

• 1 \leq i, j, k \leq N
• \frac{A_i}{A_j} = A_k

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

3
6 2 3

Sample Output 1

2

(i, j, k) = (1, 2, 3), (1, 3, 2) satisfy the conditions.

Sample Input 2

1
2

Sample Output 2

0

Sample Input 3

10
1 3 2 4 6 8 2 2 3 7

Sample Output 3

62

Problem Statement

For a binary string B = B_1 B_2 \dots B_{3^n} of length 3^n (n \geq 1), we define an operation to obtain a binary string C = C_1 C_2 \dots C_{3^{n-1}} of length 3^{n-1} as follows:

• Partition the elements of B into groups of 3 and take the majority value from each group. That is, for i=1,2,\dots,3^{n-1}, let C_i be the value that appears most frequently among B_{3i-2}, B_{3i-1}, and B_{3i}.

You are given a binary string A = A_1 A_2 \dots A_{3^N} of length 3^N. Let A' = A'_1 be the length-1 string obtained by applying the above operation N times to A.

Determine the minimum number of elements of A that must be changed (from 0 to 1 or from 1 to 0) in order to change the value of A'_1.

Constraints

• N is an integer with 1 \leq N \leq 13.
• A is a string of length 3^N consisting of 0 and 1.

Sample Input 1

2
010011101

Sample Output 1

1

For example, with A=010011101, after applying the operation twice, we obtain:

• First operation: The majority of 010 is 0, of 011 is 1, and of 101 is 1, resulting in 011.
• Second operation: The majority of 011 is 1, yielding 1.

To change the final value from 1 to 0, one way is to change the 5th character of A from 1 to 0, yielding A=010001101. After the change, the operations yield:

• First operation: The majority of 010 is 0, of 001 is 0, and of 101 is 1, resulting in 001.
• Second operation: The majority of 001 is 0, yielding 0.

Thus, the minimum number of changes required is 1.

Sample Input 2

1
000

Sample Output 2

2

Problem Statement

You are given an integer array A=(a_1,a_2,\ldots,a_N).
You may perform the following operation any number of times (possibly zero).

• Choose a nonempty contiguous subarray of A, and delete it from the array.

For each x=1,2,\ldots,M, solve the following problem:

• Find the minimum possible number of operations to make the sum of elements of A equal x. If it is impossible to make the sum of elements of A equal x, print -1 instead.

Note that the sum of elements of an empty array is 0.

Constraints

• 1 \leq N,M \leq 3000
• 1 \leq a_i \leq 3000
• All values in the input are integers.

Sample Input 1

4 5
1 2 3 4

Sample Output 1

1
2
1
1
1

The followings are examples of minimum number of operations that achieve the goal.

• For x=1, delete a_2,a_3,a_4, and the sum of elements of A becomes x.
• For x=2, delete a_3,a_4, then delete a_1, and the sum of elements of A becomes x.
• For x=3, delete a_3,a_4, and the sum of elements of A becomes x.
• For x=4, delete a_1,a_2,a_3, and the sum of elements of A becomes x.
• For x=5, delete a_2,a_3, and the sum of elements of A becomes x.

Sample Input 2

1 5
3

Sample Output 2

-1
-1
0
-1
-1

Sample Input 3

12 20
2 5 6 5 2 1 7 9 7 2 5 5

Sample Output 3

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1