Problem Statement

There is a programming contest with N problems. For each i = 1, 2, \ldots, N, the score for the i-th problem is S_i.

Print the total score for all problems with a score of X or less.

Constraints

• All input values are integers.
• 4 \leq N \leq 8
• 100 \leq S_i \leq 675
• 100 \leq X \leq 675

Sample Input 1

6 200
100 675 201 200 199 328

Sample Output 1

499

Three problems have a score of 200 or less: the first, fourth, and fifth, for a total score of S_1 + S_4 + S_5 = 100 + 200 + 199 = 499.

Sample Input 2

8 675
675 675 675 675 675 675 675 675

Sample Output 2

5400

Sample Input 3

8 674
675 675 675 675 675 675 675 675

Sample Output 3

0

Problem Statement

You are given a 3-character string S, where the first character is a digit, the second character is the character x, and the third character is a digit.

Find the product of the two numbers in S.

Constraints

• S is a 3-character string where the first character is an integer between 1 and 9, inclusive, the second character is the character x, and the third character is an integer between 1 and 9, inclusive.

Sample Input 1

3x8

Sample Output 1

24

From 3 \times 8 = 24, print 24.

Sample Input 2

9x9

Sample Output 2

81

From 9 \times 9 = 81, print 81.

Problem Statement

There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.

Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.

Constraints

• 2 \leq N \leq 1000
• N is an integer.
• Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.

Sample Input 1

3
tanaka taro
sato hanako
tanaka taro

Sample Output 1

Yes

The first and third persons have the same family and given names.

Sample Input 2

3
saito ichiro
saito jiro
saito saburo

Sample Output 2

No

No two persons have the same family and given names.

Sample Input 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

Sample Output 3

No

Problem Statement

A regular pentagon P is shown in the figure below.

Determine whether the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2.

Constraints

• Each of S_1, S_2, T_1, and T_2 is one of the characters A, B, C, D, and E.
• S_1 \neq S_2
• T_1 \neq T_2

Sample Input 1

AC
EC

Sample Output 1

Yes

The length of the line segment connecting point A and point C of P equals the length of the line segment connecting point E and point C.

Sample Input 2

DA
EA

Sample Output 2

No

The length of the line segment connecting point D and point A of P does not equal the length of the line segment connecting point E and point A.

Sample Input 3

BD
BD

Sample Output 3

Yes

Problem Statement

There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).

Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.

Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.

After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.

Constraints

• 1 \leq N, D \leq 2000
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4 5
2 -1
3 1
8 8
0 5

Sample Output 1

Yes
Yes
No
Yes

The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.

Sample Input 2

3 1
0 0
-1000 -1000
1000 1000

Sample Output 2

Yes
No
No

Sample Input 3

9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6

Sample Output 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No

Problem Statement

Takahashi observed N birds, numbered 1, 2, \dots, N, over M days.
Each of the birds that Takahashi observed has one of N colors, numbered 1, 2, \dots, N, and these birds have an interesting characteristic: their color can change during the observation period.

Bird i had color A_i in observations on or before day D_i - 1, and color B_i in observations on or after day D_i.
Here, if D_i = 1, then the bird's color was B_i from the observation on day 1, and if A_i = B_i, then the bird's color did not change during the observation period.

For each j = 1, 2, \dots, M, find the number of different colors of birds on day j.

Constraints

• 1 \le N \le 3 \times 10^5
• 1 \le M \le 3 \times 10^5
• 1 \le A_i, B_i \le N
• 1 \le D_i \le M
• All input values are integers.

Sample Input 1

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

Sample Output 1

5
5
3
3
4
4
4

In this input, six birds are observed over seven days.

• On day 1, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
• On day 2, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
• On day 3, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
• On day 4, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
• On day 5, the color of each bird was 2, 2, 1, 5, 6, 6. There are 4 different colors in total.
• On day 6, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.
• On day 7, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.

Problem Statement

How many positive integers no greater than N can be represented as a^2 \times b \times c^2 with three primes a,b, and c such that a<b<c?

Constraints

• N is an integer satisfying 300 \le N \le 10^{12}.

Sample Input 1

1000

Sample Output 1

3

The conforming integers no greater than 1000 are the following three.

• 300 = 2^2 \times 3 \times 5^2
• 588 = 2^2 \times 3 \times 7^2
• 980 = 2^2 \times 5 \times 7^2

Sample Input 2

1000000000000

Sample Output 2

2817785

Problem Statement

There are N foods, each containing exactly one of vitamins 1, 2, and 3.
Specifically, eating the i-th food gives you A_i units of vitamin V_i, and C_i calories.

Takahashi can choose any subset of these N foods as long as the total calorie consumption does not exceed X.
Find the maximum possible value of this: the minimum intake among vitamins 1, 2, and 3.

Constraints

• 1 \leq N \leq 5000
• 1 \leq X \leq 5000
• 1 \leq V_i \leq 3
• 1 \leq A_i \leq 2 \times 10^5
• 1 \leq C_i \leq X
• All input values are integers.

Sample Input 1

5 25
1 8 5
2 3 5
2 7 10
3 2 5
3 3 10

Sample Output 1

3

Each food provides the following if eaten:

• 1st food: 8 units of vitamin 1, and 5 calories
• 2nd food: 3 units of vitamin 2, and 5 calories
• 3rd food: 7 units of vitamin 2, and 10 calories
• 4th food: 2 units of vitamin 3, and 5 calories
• 5th food: 3 units of vitamin 3, and 10 calories

Eating the 1st, 2nd, 4th, and 5th foods gives 8 units of vitamin 1, 3 units of vitamin 2, 5 units of vitamin 3, and 25 calories.
In this case, the minimum among the three vitamin intakes is 3 (vitamin 2).

It is impossible to get 4 or more units of each vitamin without exceeding 25 calories, so the answer is 3.

Sample Input 2

2 5000
1 200000 1
2 200000 1

Sample Output 2

0

Problem Statement

We have a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

There are M kinds of operations available to you. Operation i swaps the a_i-th and b_i-th elements of P.

Is it possible to sort P in ascending order by doing at most 5\times 10^5 operations in total in any order?

If it is possible, give one such sequence of operations. Otherwise, report so.

Constraints

• 2\leq N \leq 1000
• P is a permutation of (1,2,\ldots,N).
• 1\leq M \leq \min(2\times 10^5, \frac{N(N-1)}{2})
• 1\leq a_i \lt b_i\leq N
• (a_i,b_i)\neq (a_j,b_j) if i\neq j.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3
4 2 1

P changes as follows: (5,3,2,4,6,1)\to (5,2,3,4,6,1)\to (5,2,3,4,1,6)\to (1,2,3,4,5,6).

Sample Input 2

5
3 4 1 2 5
2
1 3
2 5

Sample Output 2

-1

We cannot sort P in ascending order.

Sample Input 3

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

Sample Output 3

0

P may already be sorted in ascending order.

Additionally, here is another accepted output:

4
5 5 5 5

Note that it is not required to minimize the number of operations.