Problem Statement

We have a drink that has A kilocalories of energy per 100 milliliters. How many kilocalories of energy does B milliliters of this drink have?

Constraints

• 0 \leq A, B \leq 1000
• All values in input are integers.

Sample Input 1

45 200

Sample Output 1

90

We have a drink that has 45 kilocalories of energy per 100 milliliters. 200 milliliters of this drink has 90 kilocalories of energy.

Sample Input 2

37 450

Sample Output 2

166.5

The answer may not be an integer.

Sample Input 3

0 1000

Sample Output 3

0

Sample Input 4

50 0

Sample Output 4

0

Problem Statement

You are given a sequence of N integers between 1 and N (inclusive): A = (A_1, A_2, \dots, A_N).

Determine whether A is a permutation of (1, 2, \dots, N).

Constraints

• 1 \leq N \leq 10^3
• 1 \leq A_i \leq N
• All values in input are integers.

Sample Input 1

5
3 1 2 4 5

Sample Output 1

Yes

(3, 1, 2, 4, 5) is a permutation of (1, 2, 3, 4, 5), so we should print Yes.

Sample Input 2

6
3 1 4 1 5 2

Sample Output 2

No

(3, 1, 4, 1, 5, 2) is not a permutation of (1, 2, 3, 4, 5, 6), so we should print No.

Sample Input 3

3
1 2 3

Sample Output 3

Yes

Sample Input 4

1
1

Sample Output 4

Yes

Problem Statement

For a base number X, the product of multiplying it Y times is called X to the Y-th power and represented as \text{pow}(X, Y). For example, we have \text{pow}(2,3)=2\times 2\times 2=8.

Given three integers A, B, and C, compare \text{pow}(A,C) and \text{pow}(B,C) to determine which is greater.

Constraints

• -10^9 \leq A,B \leq 10^9
• 1 \leq C \leq 10^9
• All values in input are integers.

Sample Input 1

3 2 4

Sample Output 1

>

We have \text{pow}(3,4)=81 and \text{pow}(2,4)=16.

Sample Input 2

-7 7 2

Sample Output 2

=

We have \text{pow}(-7,2)=49 and \text{pow}(7,2)=49.

Sample Input 3

-8 6 3

Sample Output 3

<

We have \text{pow}(-8,3)=-512 and \text{pow}(6,3)=216.

Problem Statement

You are given a sequence of N positive integers: A = (A_1, A_2, \dots, A_N), and Q queries.

In the i-th query (1 \leq i \leq Q), given a positive integer K_i, find the K_i-th smallest integer among the positive integers that differ from all of A_1, A_2, \dots, A_N.

Constraints

• 1 \leq N, Q \leq 10^5
• 1 \leq A_1 < A_2 < \dots < A_N \leq 10^{18}
• 1 \leq K_i \leq 10^{18}
• All values in input are integers.

Sample Input 1

4 3
3 5 6 7
2
5
3

Sample Output 1

2
9
4

The positive integers that differ from all of A_1, A_2, \dots, A_N are 1, 2, 4, 8, 9, 10, 11, \dots in ascending order. The second, fifth, and third smallest of them are 2, 9, and 4, respectively.

Sample Input 2

5 2
1 2 3 4 5
1
10

Sample Output 2

6
15

Problem Statement

How many ways are there to arrange N white balls and M black balls in a row from left to right to satisfy the following condition?

• For each i (1 \leq i \leq N + M), let w_i and b_i be the number of white balls and black balls among the leftmost i balls, respectively. Then, w_i \leq b_i + K holds for every i.

Since the count can be enormous, find it modulo (10^9 + 7).

Constraints

• 0 \leq N, M \leq 10^6
• 1 \leq N + M
• 0 \leq K \leq N
• All values in input are integers.

Sample Input 1

2 3 1

Sample Output 1

9

There are 10 ways to arrange 2 white balls and 3 black balls in a row, as shown below, where w and b stand for a white ball and a black ball, respectively.

wwbbb wbwbb wbbwb wbbbw bwwbb bwbwb bwbbw bbwwb bbwbw bbbww

Among them, wwbbb is the only one that does not satisfy the condition. Here, there are 2 white balls and 0 black balls among the 2 leftmost balls, and we have 2 > 0 + K = 1.

Sample Input 2

1 0 0

Sample Output 2

0

There may be no way to satisfy the condition.

Sample Input 3

1000000 1000000 1000000

Sample Output 3

192151600

Be sure to print the count modulo (10^9 + 7).

Problem Statement

There is a grid with H rows and W columns. Let (r, c) denote the square at the r-th row from the top and c-th column from the left.

We have N pieces. For the i-th piece, we can choose to do one of the following:

• Put it at a square (r, c) such that A_i \leq r \leq C_i and B_i \leq c \leq D_i.
• Do not put it on the grid.

However, we cannot put two pieces in the same row or the same column.

At most how many pieces can we put on the grid?

Constraints

• 1 \leq H, W, N \leq 100
• 1 \leq A_i \leq C_i \leq H
• 1 \leq B_i \leq D_i \leq W
• All values in input are integers.

Sample Input 1

2 3 3
1 1 2 2
1 2 2 3
1 1 1 3

Sample Output 1

2

By putting the first piece at (1, 1), the second piece at (2, 2), and not putting the third piece on the grid, we can put two pieces on the grid. We cannot put three, so we should print 2.

Sample Input 2

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

Sample Output 2

3