Problem Statement

In Japan, there are four major categories of ice cream type products:

• an ice cream type product with at least 15 percent milk solids and at least 8 percent milk fat is called an ice cream;
• an ice cream type product with at least 10 percent milk solids and at least 3 percent milk fat that is not an ice cream is called an ice milk;
• an ice cream type product with at least 3 percent milk solids that is not an ice cream or an ice milk is called a lacto ice;
• an ice cream type product that is not an ice cream, an ice milk, or a lacto ice is called a flavored ice.

Here, milk solids consist of milk fat and milk solids-not-fat.
AtCoder's famous product Snuke Ice contains A percent milk solids-not-fat and B percent milk fat.
Which of the categories above does Snuke Ice fall into?
Print your answer as an integer according to the Output section.

Constraints

• 0 \le A \le 100
• 0 \le B \le 100
• A + B \le 100
• A and B are integers.

Sample Input 1

10 8

Sample Output 1

1

This product contains 10 percent milk solids-not-fat and 8 percent milk fat, for a total of 18 percent milk solids.
Since it contains not less than 15 percent milk solids and not less than 8 percent milk fat, it is an ice cream; the correct output is 1.

Sample Input 2

1 2

Sample Output 2

3

Since it contains exactly 3 percent milk solids, it is not an ice cream or an ice milk but is a lacto ice; the correct output is 3.

Sample Input 3

0 0

Sample Output 3

4

It is a flavored ice.

Problem Statement

Your company has N employees, called Employee 1 through N.
You have received two work orders, called Work A and B, which must be completed.
Employee i can complete Work A in A_i minutes and Work B in B_i minutes.

You will assign each work to one employee.
You can assign both works to the same employee, in which case the time it takes for him/her to complete them is the sum of the times it takes for him/her to do them individually.
If you assign the works to different employees, the time it takes for them to complete them is the longer of the times it takes for them to do their respective works.
Find the shortest possible time needed to complete the works.

Constraints

• 2 \le N \le 1000
• 1 \le A_i \le 10^5
• 1 \le B_i \le 10^5
• All values in input are integers.

Sample Input 1

3
8 5
4 4
7 9

Sample Output 1

5

If you assign Work A to Employee 2 and Work B to Employee 1, they will complete them in 4 and 5 minutes, respectively.
Since you assigned the works to different employees, it will take \max(4, 5) = 5 minutes for the two works to be finished.
It is impossible to finish them earlier.

Sample Input 2

3
11 7
3 2
6 7

Sample Output 2

5

It is optimal to assign both works to Employee 2.
Note that if you assign both works to the same employee, the time it takes for him/her to complete them is the sum of the times it takes for him/her to do them individually.

Problem Statement

Given is a number sequence A of length N.
Find the sum of squared differences of every pair of elements: \displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2.

Constraints

• 2 \le N \le 3 \times 10^5
• |A_i| \le 200
• All values in input are integers.

Sample Input 1

3
2 8 4

Sample Output 1

56

We have \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 = (8 - 2)^2 + (4 - 2) ^ 2 + (4 - 8) ^ 2 = 56.

Sample Input 2

5
-5 8 9 -4 -3

Sample Output 2

950

Problem Statement

We have a graph with N vertices called Vertex 1 through N. Takahashi is standing on Vertex 1.
The graph has no edges now.
Takahashi will repeatedly do the following operation:

1. Choose one of the N vertices (including the one on which Takahashi is standing now). Every vertex is chosen with probability \frac{1}{N}, independently from previous operations.
2. Add an edge between the vertex on which Takahashi is standing now and the chosen vertex, and go to the chosen vertex.

Find the expected value of the number of times he does the operation until the graph becomes connected.

Constraints

• 2 \le N \le 10^5

Sample Input 1

2

Sample Output 1

2.00000000000

The graph becomes connected when the operation chooses Vertex 2 for the first time.
By considering the case Vertex 2 is chosen for the first time in the i-th operation for each i, the answer is \sum_{i = 1}^{\infty} (i \times (\frac{1}{2})^i) = 2.

Sample Input 2

3

Sample Output 2

4.50000000000

Problem Statement

Let us define \mathrm{mex}(x_1, x_2, x_3, \dots, x_k) as the smallest non-negative integer that does not occur in x_1, x_2, x_3, \dots, x_k.
You are given an integer sequence of length N: A = (A_1, A_2, A_3, \dots, A_N).
For each integer i such that 0 \le i \le N - M, we compute \mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M}). Find the minimum among the results of these N - M + 1 computations.

Constraints

• 1 \le M \le N \le 1.5 \times 10^6
• 0 \le A_i \lt N
• All values in input are integers.

Sample Input 1

3 2
0 0 1

Sample Output 1

1

We have:

• for i = 0: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(0, 0) = 1
• for i = 1: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(0, 1) = 2

Thus, the answer is the minimum among 1 and 2, which is 1.

Sample Input 2

3 2
1 1 1

Sample Output 2

0

We have:

• for i = 0: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(1, 1) = 0
• for i = 1: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(1, 1) = 0

Sample Input 3

3 2
0 1 0

Sample Output 3

2

We have:

• for i = 0: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(0, 1) = 2
• for i = 1: \mathrm{mex}(A_{i + 1}, A_{i + 2}) = \mathrm{mex}(1, 0) = 2

Sample Input 4

7 3
0 0 1 2 0 1 0

Sample Output 4

2

Problem Statement

In this problem, hexadecimal notations use 0, ..., 9, A, ..., F, representing the values zero through fifteen, respectively.
Unless otherwise specified, all notations of numbers are decimal notations.

How many integers between 1 and N (inclusive) have exactly K distinct digits in the hexadecimal notation without leading zeros?
Print this count modulo (10^9 + 7).

Constraints

• 1 \le N \lt {16}^{2 \times 10^5}
• N is given in hexadecimal notation without leading 0s.
• 1 \le K \le 16
• All values in input are integers.

Sample Input 1

10 1

Sample Output 1

15

The hexadecimal number N is 16 in decimal.
In hexadecimal, the integers between 1 and 16 are written as follows:

• 1 through 15: are 1-digit numbers in hexadecimal, containing one distinct digit.
• 16: is 10 in hexadecimal, containing two distinct digits.

Thus, there are 15 numbers that contain one distinct digit in hexadecimal.

Sample Input 2

FF 2

Sample Output 2

225

All of the 255 numbers except the following 30 numbers contain two distinct digits in hexadecimal: 1, 2, 3, \dots, \mathrm{E}, \mathrm{F}, 11, 22, 33, \dots, \mathrm{EE}, \mathrm{FF} in hexadecimal.

Sample Input 3

100 2

Sample Output 3

226

Sample Input 4

1A8FD02 4

Sample Output 4

3784674

Sample Input 5

DEADBEEFDEADBEEEEEEEEF 16

Sample Output 5

153954073

Print the count modulo (10^9 + 7).