Problem Statement

Assuming that the horizon seen from a place x meters above the ground is \sqrt{x(12800000+x)} meters away, find how many meters away the horizon seen from a place H meters above the ground is.

Constraints

• 1 \leq H \leq 10^5
• H is an integer.

Sample Input 1

333

Sample Output 1

65287.907678222

We have \sqrt{333(12800000+333)} = 65287.9076782\ldots. Outputs such as 65287.91 would also be accepted.

Sample Input 2

634

Sample Output 2

90086.635834623

We have \sqrt{634(12800000+634)} = 90086.6358346\ldots.

Problem Statement

Given an integer X between -10^{18} and 10^{18} (inclusive), print \left\lfloor \dfrac{X}{10} \right\rfloor.

Notes

For a real number x, \left\lfloor x \right\rfloor denotes "the maximum integer not exceeding x". For example, we have \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, and \left\lfloor 5 \right\rfloor = 5. (For more details, please refer to the description in the Sample Input and Output.)

Constraints

• -10^{18} \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

47

Sample Output 1

4

The integers that do not exceed \frac{47}{10} = 4.7 are all the negative integers, 0, 1, 2, 3, and 4. The maximum integer among them is 4, so we have \left\lfloor \frac{47}{10} \right\rfloor = 4.

Sample Input 2

-24

Sample Output 2

-3

Since the maximum integer not exceeding \frac{-24}{10} = -2.4 is -3, we have \left\lfloor \frac{-24}{10} \right\rfloor = -3.
Note that -2 does not satisfy the condition, as -2 exceeds -2.4.

Sample Input 3

50

Sample Output 3

5

The maximum integer that does not exceed \frac{50}{10} = 5 is 5 itself. Thus, we have \left\lfloor \frac{50}{10} \right\rfloor = 5.

Sample Input 4

-30

Sample Output 4

-3

Just like the previous example, \left\lfloor \frac{-30}{10} \right\rfloor = -3.

Sample Input 5

987654321987654321

Sample Output 5

98765432198765432

The answer is 98765432198765432. Make sure that all the digits match.

If your program does not behave as intended, we recommend you checking the specification of the programming language you use.
If you want to check how your code works, you may use "Custom Test" above the Problem Statement.

Problem Statement

On an xy-coordinate plane, is there a lattice point whose distances from two lattice points (x_1, y_1) and (x_2, y_2) are both \sqrt{5}?

Notes

A point on an xy-coordinate plane whose x and y coordinates are both integers is called a lattice point.
The distance between two points (a, b) and (c, d) is defined to be the Euclidean distance between them, \sqrt{(a - c)^2 + (b-d)^2}.

The following figure illustrates an xy-plane with a black circle at (0, 0) and white circles at the lattice points whose distances from (0, 0) are \sqrt{5}. (The grid shows where either x or y is an integer.)

Constraints

• -10^9 \leq x_1 \leq 10^9
• -10^9 \leq y_1 \leq 10^9
• -10^9 \leq x_2 \leq 10^9
• -10^9 \leq y_2 \leq 10^9
• (x_1, y_1) \neq (x_2, y_2)
• All values in input are integers.

Sample Input 1

0 0 3 3

Sample Output 1

Yes

• The distance between points (2,1) and (x_1, y_1) is \sqrt{(0-2)^2 + (0-1)^2} = \sqrt{5};
• the distance between points (2,1) and (x_2, y_2) is \sqrt{(3-2)^2 + (3-1)^2} = \sqrt{5};
• point (2, 1) is a lattice point,

so point (2, 1) satisfies the condition. Thus, Yes should be printed.
One can also assert in the same way that (1, 2) also satisfies the condition.

Sample Input 2

0 1 2 3

Sample Output 2

No

No lattice point satisfies the condition, so No should be printed.

Sample Input 3

1000000000 1000000000 999999999 999999999

Sample Output 3

Yes

Point (10^9 + 1, 10^9 - 2) and point (10^9 - 2, 10^9 + 1) satisfy the condition.

Problem Statement

Takahashi and Aoki are playing a game.

• First, Takahashi chooses an integer between A and B (inclusive) and tells it to Aoki.
• Next, Aoki chooses an integer between C and D (inclusive).
• If the sum of these two integers is a prime, then Aoki wins; otherwise, Takahashi wins.

When the two players play optimally, which player will win?

Constraints

• 1 \leq A \leq B \leq 100
• 1 \leq C \leq D \leq 100
• All values in input are integers.

Sample Input 1

2 3 3 4

Sample Output 1

Aoki

For example, if Takahashi chooses 2, Aoki can choose 3 to make the sum 5, which is a prime.

Sample Input 2

1 100 50 60

Sample Output 2

Takahashi

If they play optimally, Takahashi always wins.

Sample Input 3

3 14 1 5

Sample Output 3

Aoki

Problem Statement

We have a rooted tree with N vertices. The vertices are numbered 1 through N, and the root is Vertex 1.
The i-th edge connects Vertices A_i and B_i.
Vertex i has an integer X_i written on it.

You are given Q queries. For the i-th query, given a pair of integers (V_i,K_i), answer the following question.

• Question: among the integers written on the vertices in the subtree rooted at Vertex V_i, find the K_i-th largest value.

Constraints

• 2 \leq N \leq 10^5
• 0\leq X_i\leq 10^9
• 1\leq A_i,B_i\leq N
• 1\leq Q \leq 10^5
• 1\leq V_i\leq N
• 1\leq K_i\leq 20
• The given graph is a tree.
• The subtree rooted at Vertex V_i has K_i or more vertices.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4
5

The tree given in this input is shown below.

For the 1-st query, the vertices in the subtree rooted at Vertex 1 are Vertices 1, 2, 3, 4, and 5, so print the 2-nd largest value of the numbers written on these vertices, 4.
For the 2-nd query, the vertices in the subtree rooted at Vertex 2 are Vertices 2, 3, and 5, so print the 1-st largest value of the numbers written on these vertices, 5.

Sample Input 2

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

Sample Output 2

9
10

Sample Input 3

4 4
1 10 100 1000
1 2
2 3
3 4
1 4
2 3
3 2
4 1

Sample Output 3

1
10
100
1000

Problem Statement

The Republic of Atcoder has N towns numbered 1 through N, and M highways numbered 1 through M.
Highway i connects Town A_i and Town B_i bidirectionally.

King Takahashi is going to construct (N-M-1) new highways so that the following two conditions are satisfied:

• One can travel between every pair of towns using some number of highways
• For each i=1,\ldots,N, exactly D_i highways are directly connected to Town i

Determine if there is such a way of construction. If it exists, print one.

Constraints

• 2 \leq N \leq 2\times 10^5
• 0 \leq M \lt N-1
• 1 \leq D_i \leq N-1
• 1\leq A_i \lt B_i \leq N
• If i\neq j, then (A_i, B_i) \neq (A_j,B_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

6 2
5 6
4 5

As in the Sample Output, the conditions can be satisfied by constructing highways connecting Towns 6 and 2, Towns 5 and 6, and Towns 4 and 5, respectively.

Another example to satisfy the conditions is to construct highways connecting Towns 6 and 4, Towns 5 and 6, and Towns 2 and 5, respectively.

Sample Input 2

5 1
1 1 1 1 4
2 3

Sample Output 2

-1

Sample Input 3

4 0
3 3 3 3

Sample Output 3

-1

Problem Statement

We have a simple connected undirected graph with N vertices and M edges.
The vertices are numbered as Vertex 1, Vertex 2, \dots, Vertex N.
The edges are numbered as Edge 1, Edge 2, \dots, Edge M. Edge i connects Vertex a_i and Vertex b_i bidirectionally. There is no edge that directly connects Vertex 1 and Vertex N.
Each vertex is either empty or occupied by a wall. Initially, every vertex is empty.

Aoki is going to travel from Vertex 1 to Vertex N along the edges on the graph. However, Aoki is not allowed to move to a vertex occupied by a wall.

Takahashi has decided to choose some of the vertices to build walls on, so that Aoki cannot travel to Vertex N no matter which route he takes.
Building a wall on Vertex i costs Takahashi c_i yen (the currency of Japan). He cannot build a wall on Vertex 1 and Vertex N.

How many yens is required for Takahashi to build walls so that the conditions is satisfied? Also, print the way of building walls to achieve the minimum cost.

Constraints

• 3 \leq N \leq 100
• N - 1 \leq M \leq \frac{N(N-1)}{2} - 1
• 1 \leq a_i \lt b_i \leq N (1 \leq i \leq M)
• (a_i, b_i) \neq (1, N)
• The given graph is simple and connected.
• 1 \leq c_{i} \leq 10^9 (2 \leq i \leq N-1)
• c_1 = c_N = 0
• All values in input are integers.

Sample Input 1

5 5
1 2
2 3
3 5
2 4
4 5
0 8 3 4 0

Sample Output 1

7
2
3 4

If Takahashi builds walls on Vertex 3 and Vertex 4, paying 3 + 4 = 7 yen, Aoki is unable to travel from Vertex 1 to Vertex 5.
There is no way to satisfy the condition with less cost, so 7 yen is the answer.

Sample Input 2

3 2
1 2
2 3
0 1 0

Sample Output 2

1
1
2

Sample Input 3

5 9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
0 1000000000 1000000000 1000000000 0

Sample Output 3

3000000000
3
2 3 4

Problem Statement

Snuke has a die (singular of dice) that shows integers from 1 through N with equal probability, and an integer 1.
He repeats the following operation while his integer is less than or equal to M.

• He rolls the die. If the die shows an integer x, he multiplies his integer by x.

Find the expected value of the number of times he rolls the die until he stops, modulo 10^9+7.

Constraints

• 2 \leq N \leq 10^9
• 1 \leq M \leq 10^9

Sample Input 1

2 1

Sample Output 1

2

The answer is the expected value of the number of rolls until it shows 2 for the first time. Thus, 2 should be printed.

Sample Input 2

2 39

Sample Output 2

12

The answer is the expected value of the number of rolls until it shows 2 six times. Thus, 12 should be printed.

Sample Input 3

3 2

Sample Output 3

250000004

The answer is \frac{9}{4}. We have 4 \times 250000004 \equiv 9 \pmod{10^9+7}, so 250000004 should be printed.
Note that the answer should be printed modulo \bf{10^9 + 7 = 1000000007}.

Sample Input 4

2392 39239

Sample Output 4

984914531

Sample Input 5

1000000000 1000000000

Sample Output 5

776759630