Problem Statement

N of us are going on a trip, by train or taxi.

The train will cost each of us A yen (the currency of Japan).

The taxi will cost us a total of B yen.

How much is our minimum total travel expense?

Constraints

• All values in input are integers.
• 1 \leq N \leq 20
• 1 \leq A \leq 50
• 1 \leq B \leq 50

Sample Input 1

4 2 9

Sample Output 1

8

The train will cost us 4 \times 2 = 8 yen, and the taxi will cost us 9 yen, so the minimum total travel expense is 8 yen.

Sample Input 2

4 2 7

Sample Output 2

7

Sample Input 3

4 2 8

Sample Output 3

8

Problem Statement

There are N points in a D-dimensional space.

The coordinates of the i-th point are (X_{i1}, X_{i2}, ..., X_{iD}).

The distance between two points with coordinates (y_1, y_2, ..., y_D) and (z_1, z_2, ..., z_D) is \sqrt{(y_1 - z_1)^2 + (y_2 - z_2)^2 + ... + (y_D - z_D)^2}.

How many pairs (i, j) (i < j) are there such that the distance between the i-th point and the j-th point is an integer?

Constraints

• All values in input are integers.
• 2 \leq N \leq 10
• 1 \leq D \leq 10
• -20 \leq X_{ij} \leq 20
• No two given points have the same coordinates. That is, if i \neq j, there exists k such that X_{ik} \neq X_{jk}.

Sample Input 1

3 2
1 2
5 5
-2 8

Sample Output 1

1

The number of pairs with an integer distance is one, as follows:

• The distance between the first point and the second point is \sqrt{|1-5|^2 + |2-5|^2} = 5, which is an integer.
• The distance between the second point and the third point is \sqrt{|5-(-2)|^2 + |5-8|^2} = \sqrt{58}, which is not an integer.
• The distance between the third point and the first point is \sqrt{|-2-1|^2+|8-2|^2} = 3\sqrt{5}, which is not an integer.

Sample Input 2

3 4
-3 7 8 2
-12 1 10 2
-2 8 9 3

Sample Output 2

2

Sample Input 3

5 1
1
2
3
4
5

Sample Output 3

10

Problem Statement

You are given two non-negative integers L and R. We will choose two integers i and j such that L \leq i < j \leq R. Find the minimum possible value of (i \times j) \text{ mod } 2019.

Constraints

• All values in input are integers.
• 0 \leq L < R \leq 2 \times 10^9

Sample Input 1

2020 2040

Sample Output 1

2

When (i, j) = (2020, 2021), (i \times j) \text{ mod } 2019 = 2.

Sample Input 2

4 5

Sample Output 2

20

We have only one choice: (i, j) = (4, 5).

Problem Statement

There are N mountains in a circle, called Mountain 1, Mountain 2, ..., Mountain N in clockwise order. N is an odd number.

Between these mountains, there are N dams, called Dam 1, Dam 2, ..., Dam N. Dam i (1 \leq i \leq N) is located between Mountain i and i+1 (Mountain N+1 is Mountain 1).

When Mountain i (1 \leq i \leq N) receives 2x liters of rain, Dam i-1 and Dam i each accumulates x liters of water (Dam 0 is Dam N).

One day, each of the mountains received a non-negative even number of liters of rain.

As a result, Dam i (1 \leq i \leq N) accumulated a total of A_i liters of water.

Find the amount of rain each of the mountains received. We can prove that the solution is unique under the constraints of this problem.

Constraints

• All values in input are integers.
• 3 \leq N \leq 10^5-1
• N is an odd number.
• 0 \leq A_i \leq 10^9
• The situation represented by input can occur when each of the mountains receives a non-negative even number of liters of rain.

Sample Input 1

3
2 2 4

Sample Output 1

4 0 4

If we assume Mountain 1, 2, and 3 received 4, 0, and 4 liters of rain, respectively, it is consistent with this input, as follows:

• Dam 1 should have accumulated \frac{4}{2} + \frac{0}{2} = 2 liters of water.
• Dam 2 should have accumulated \frac{0}{2} + \frac{4}{2} = 2 liters of water.
• Dam 3 should have accumulated \frac{4}{2} + \frac{4}{2} = 4 liters of water.

Sample Input 2

5
3 8 7 5 5

Sample Output 2

2 4 12 2 8

Sample Input 3

3
1000000000 1000000000 0

Sample Output 3

0 2000000000 0

Problem Statement

You are given a tree with N vertices and N-1 edges. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and b_i.

You have coloring materials of K colors. For each vertex in the tree, you will choose one of the K colors to paint it, so that the following condition is satisfied:

• If the distance between two different vertices x and y is less than or equal to two, x and y have different colors.

How many ways are there to paint the tree? Find the count modulo 1\ 000\ 000\ 007.

Constraints

• 1 \leq N,K \leq 10^5
• 1 \leq a_i,b_i \leq N
• The given graph is a tree.

Sample Input 1

4 3
1 2
2 3
3 4

Sample Output 1

6

There are six ways to paint the tree.

Sample Input 2

5 4
1 2
1 3
1 4
4 5

Sample Output 2

48

Sample Input 3

16 22
12 1
3 1
4 16
7 12
6 2
2 15
5 16
14 16
10 11
3 10
3 13
8 6
16 8
9 12
4 3

Sample Output 3

271414432

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i, and the color and length of that edge are c_i and d_i, respectively. Here the color of each edge is represented by an integer between 1 and N-1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.

Answer the following Q queries:

• Query j (1 \leq j \leq Q): assuming that the length of every edge whose color is x_j is changed to y_j, find the distance between Vertex u_j and Vertex v_j. (The changes of the lengths of edges do not affect the subsequent queries.)

Constraints

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq a_i, b_i \leq N
• 1 \leq c_i \leq N-1
• 1 \leq d_i \leq 10^4
• 1 \leq x_j \leq N-1
• 1 \leq y_j \leq 10^4
• 1 \leq u_j < v_j \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4

Sample Output 1

130
200
60

The graph in this input is as follows:

Here the edges of Color 1 are shown as solid red lines, the edge of Color 2 is shown as a bold green line, and the edge of Color 4 is shown as a blue dashed line.

• Query 1: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 4 is 100 + 30 = 130.
• Query 2: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 5 is 100 + 100 = 200.
• Query 3: Assuming that the length of every edge whose color is 3 is changed to 1000 (there is no such edge), the distance between Vertex 3 and Vertex 4 is 20 + 10 + 30 = 60. Note that the edges of Color 1 now have their original lengths.