Problem Statement

Let us assume that water pressure depends only on depth and is \dfrac{x}{100} megapascal at a depth of x meters.

What is the water pressure in megapascals at a depth of D meters?

Constraints

• 1 \leq D \leq 10000
• D is an integer.

Sample Input 1

1000

Sample Output 1

10

The water pressure at a depth of 1000 meters is 10 megapascal. Outputs such as 10.0 and 9.999999 would also be accepted.

Sample Input 2

50

Sample Output 2

0.5

Sample Input 3

3141

Sample Output 3

31.41

Problem Statement

An election is taking place.

N people voted. The i-th person (1 \leq i \leq N) cast a vote to the candidate named S_i.

Find the name of the candidate who received the most votes. The given input guarantees that there is a unique candidate with the most votes.

Constraints

• 1 \leq N \leq 100
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
• N is an integer.
• There is a unique candidate with the most votes.

Sample Input 1

5
snuke
snuke
takahashi
takahashi
takahashi

Sample Output 1

takahashi

takahashi got 3 votes, and snuke got 2, so we print takahashi.

Sample Input 2

5
takahashi
takahashi
aoki
takahashi
snuke

Sample Output 2

takahashi

Sample Input 3

1
a

Sample Output 3

a

Problem Statement

There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.

For each j=1,2,\ldots,Q, answer the following question.

• How many of the N students have a height of at least x_j?

Constraints

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

Sample Input 1

3 1
100 160 130
120

Sample Output 1

2

The students with a height of at least 120 are the 2-nd and 3-rd ones.

Sample Input 2

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

Sample Output 2

0
1
2
3
4

Sample Input 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

Sample Output 3

5
3
5
5
5

Problem Statement

Determine whether there is a way to line up N people, numbered 1 to N, in a row side by side to satisfy all of the M conditions in the following format.

• Condition: Person A_i and Person B_i are adjacent.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq 10^5
• 1\leq A_i < B_i \leq N
• All pairs (A_i,B_i) are distinct.

Sample Input 1

4 2
1 3
2 3

Sample Output 1

Yes

One way to satisfy all the conditions is to line them up in the order 4,1,3,2.

Sample Input 2

4 3
1 4
2 4
3 4

Sample Output 2

No

There is no way to line them up to satisfy all the conditions.

Problem Statement

There are N kinds of coins used in the Kingdom of Atcoder: A_1-yen, A_2-yen, \ldots, A_N-yen coins.
Here, 1=A_1 < \ldots < A_N holds, and A_{i+1} is a multiple of A_i for every 1\leq i \leq N-1.

When paying for a product worth X yen using just these coins, what is the minimum total number of coins used in payment and returned as change?

Accurately, when Y is an integer at least X, find the minimum sum of the number of coins needed to represent exactly Y yen and the number of coins needed to represent exactly Y-X yen.

Constraints

• All values in input are integers.
• 1 \leq N \leq 60
• 1=A_1 < \ldots <A_N \leq 10^{18}
• A_{i+1} is a multiple of A_i for every 1\leq i \leq N-1.
• 1\leq X \leq 10^{18}

Sample Input 1

3 87
1 10 100

Sample Output 1

5

If we pay with one 100-yen coin and receive one 10-yen coin and three 1-yen coins as the change, the total number of coins will be 5.

Sample Input 2

2 49
1 7

Sample Output 2

7

It is optimal to pay with seven 7-yen coins.

Sample Input 3

10 123456789012345678
1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

Sample Output 3

233

Problem Statement

Snuke is planning on giving one gift each to Takahashi and Aoki.
There are N candidates for the gifts. Takahashi's impression of the i-th candidate is A_i, and Aoki's impression of it is B_i.

The two are very jealous. If Takahashi's impression of the gift Aoki gets is greater than Takahashi's impression of the gift Takahashi gets, Takahashi gets jealous of Aoki and starts fighting, and vice versa.

Among the N^2 possible ways of giving the gifts, how many do not lead to fighting?

Constraints

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

Sample Input 1

3
50 100 150
1 3 2

Sample Output 1

4

For example, if we give the 1-st candidate to Takahashi and the 2-nd candidate to Aoki, Takahashi's impression of the gift Aoki gets is 100, while Takahashi's impression of the gift Takahashi gets is 50, so Takahashi gets jealous of Aoki and starts fighting.

As another example, if we give the 3-rd candidate to Takahashi and the 2-nd candidate to Aoki, the two will not start fighting.

Note that it is allowed to give the same gift to the two.

Sample Input 2

3
123456789 123456 123
987 987654 987654321

Sample Output 2

6

Sample Input 3

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

Sample Output 3

37

Problem Statement

We have N boxes numbered 1 to N. Initially, Box i contains A_i balls.

You will repeat the following operation K times.

• Choose one box out of the N uniformly at random (each time independently). Add one ball to the chosen box.

Let B_i be the number of balls in Box i after the K operations, and the score be the product of the numbers of balls, \prod_{i=1}^{N}B_i.

Find the expected value of the score modulo 998244353.

Notes

When the expected value in question is represented as an irreducible fraction p/q, there uniquely exists an integer r such that rq\equiv p \pmod{998244353} and 0\leq r < 998244353 under the Constraints of this problem. This r is the value we seek.

Constraints

• 1 \leq N \leq 1000
• 1 \leq K \leq 10^9
• 0 \leq A_i \leq 10^9

Sample Input 1

3 1
1 2 3

Sample Output 1

665496245

After the operation, the score will be as follows.

• When choosing Box 1 in the operation, 2\times 2\times 3=12.
• When choosing Box 2 in the operation, 1\times 3\times 3=9.
• When choosing Box 3 in the operation, 1\times 2\times 4=8.

Therefore, the expected value in question is \frac{1}{3}(12+9+8)=\frac{29}{3}. This value modulo 998244353 is 665496245.

Sample Input 2

2 2
1 2

Sample Output 2

499122182

After the operations, the score will be as follows.

• When choosing Box 1 in the first operation and Box 1 in the second, 3\times 2=6.
• When choosing Box 1 in the first operation and Box 2 in the second, 2\times 3=6.
• When choosing Box 2 in the first operation and Box 1 in the second, 2\times 3=6.
• When choosing Box 2 in the first operation and Box 2 in the second, 1\times 4=4.

Therefore, the expected value in question is \frac{1}{4}(6+6+6+4)=\frac{11}{2}.

Sample Input 3

10 1000000000
998244350 998244351 998244352 998244353 998244354 998244355 998244356 998244357 998244358 998244359

Sample Output 3

138512322

Problem Statement

We have a grid with H rows and W columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

On this grid, there are N white pieces numbered 1 to N. Piece i is on (A_i,B_i).

You can pay the cost of C_i to change Piece i to a black piece.

Find the minimum total cost needed to have at least one black piece in every row and every column.

Constraints

• 1 \leq H,W \leq 10^3
• 1 \leq N \leq 10^3
• 1 \leq A_i \leq H
• 1 \leq B_i \leq W
• 1 \leq C_i \leq 10^9
• All pairs (A_i,B_i) are distinct.
• There is at least one white piece in every row and every column.
• All values in input are integers.

Sample Input 1

2 3 6
1 1 1
1 2 10
1 3 100
2 1 1000
2 2 10000
2 3 100000

Sample Output 1

1110

By paying the cost of 1110 to change Pieces 2, 3, 4 to black pieces, we can have a black piece in every row and every column.

Sample Input 2

1 7 7
1 2 200000000
1 7 700000000
1 4 400000000
1 3 300000000
1 6 600000000
1 5 500000000
1 1 100000000

Sample Output 2

2800000000

Sample Input 3

3 3 8
3 2 1
3 1 2
2 3 1
2 2 100
2 1 100
1 3 2
1 2 100
1 1 100

Sample Output 3

6