Problem Statement

You are given positive integers X and Y. If there exists a positive integer not greater than 10^{18} that is a multiple of X but not a multiple of Y, choose one such integer and print it. If it does not exist, print -1.

Constraints

• 1 ≤ X,Y ≤ 10^9
• X and Y are integers.

Sample Input 1

8 6

Sample Output 1

16

For example, 16 is a multiple of 8 but not a multiple of 6.

Sample Input 2

3 3

Sample Output 2

-1

A multiple of 3 is a multiple of 3.

Problem Statement

You are given two integer sequences of length N: a_1,a_2,..,a_N and b_1,b_2,..,b_N. Determine if we can repeat the following operation zero or more times so that the sequences a and b become equal.

Operation: Choose two integers i and j (possibly the same) between 1 and N (inclusive), then perform the following two actions simultaneously:

• Add 2 to a_i.
• Add 1 to b_j.

Constraints

• 1 ≤ N ≤ 10 000
• 0 ≤ a_i,b_i ≤ 10^9 (1 ≤ i ≤ N)
• All input values are integers.

Sample Input 1

3
1 2 3
5 2 2

Sample Output 1

Yes

For example, we can perform three operations as follows to do our job:

• First operation: i=1 and j=2. Now we have a = \{3,2,3\}, b = \{5,3,2\}.
• Second operation: i=1 and j=2. Now we have a = \{5,2,3\}, b = \{5,4,2\}.
• Third operation: i=2 and j=3. Now we have a = \{5,4,3\}, b = \{5,4,3\}.

Sample Input 2

5
3 1 4 1 5
2 7 1 8 2

Sample Output 2

No

Sample Input 3

5
2 7 1 8 2
3 1 4 1 5

Sample Output 3

No

Problem Statement

This is an interactive task.

Let N be an odd number at least 3.

There are N seats arranged in a circle. The seats are numbered 0 through N-1. For each i (0 ≤ i ≤ N - 2), Seat i and Seat i + 1 are adjacent. Also, Seat N - 1 and Seat 0 are adjacent.

Each seat is either vacant, or oppupied by a man or a woman. However, no two adjacent seats are occupied by two people of the same sex. It can be shown that there is at least one empty seat where N is an odd number at least 3.

You are given N, but the states of the seats are not given. Your objective is to correctly guess the ID number of any one of the empty seats. To do so, you can repeatedly send the following query:

• Choose an integer i (0 ≤ i ≤ N - 1). If Seat i is empty, the problem is solved. Otherwise, you are notified of the sex of the person in Seat i.

Guess the ID number of an empty seat by sending at most 20 queries.

Constraints

• N is an odd number.
• 3 ≤ N ≤ 99 999

Input and Output

First, N is given from Standard Input in the following format:

N

Then, you should send queries. A query should be printed to Standart Output in the following format. Print a newline at the end.

i

The response to the query is given from Standard Input in the following format:

s

Here, s is Vacant, Male or Female. Each of these means that Seat i is empty, occupied by a man and occupied by a woman, respectively.

Notice

• Flush Standard Output each time you print something. Failure to do so may result in TLE.
• Immediately terminate the program when s is Vacant. Otherwise, the verdict is indeterminate.
• The verdict is indeterminate if more than 20 queries or ill-formatted queries are sent.

Sample Input / Output 1

In this sample, N = 3, and Seat 0, 1, 2 are occupied by a man, occupied by a woman and vacant, respectively.

Problem Statement

You are given a forest with N vertices and M edges. The vertices are numbered 0 through N-1. The edges are given in the format (x_i,y_i), which means that Vertex x_i and y_i are connected by an edge.

Each vertex i has a value a_i. You want to add edges in the given forest so that the forest becomes connected. To add an edge, you choose two different vertices i and j, then span an edge between i and j. This operation costs a_i + a_j dollars, and afterward neither Vertex i nor j can be selected again.

Find the minimum total cost required to make the forest connected, or print Impossible if it is impossible.

Constraints

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ N-1
• 1 ≤ a_i ≤ 10^9
• 0 ≤ x_i,y_i ≤ N-1
• The given graph is a forest.
• All input values are integers.

Sample Input 1

7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6

Sample Output 1

7

If we connect vertices 0 and 5, the graph becomes connected, for the cost of 1 + 6 = 7 dollars.

Sample Input 2

5 0
3 1 4 1 5

Sample Output 2

Impossible

We can't make the graph connected.

Sample Input 3

1 0
5

Sample Output 3

0

The graph is already connected, so we do not need to add any edges.

Problem Statement

We have a tree with N vertices. The vertices are numbered 0 through N - 1, and the i-th edge (0 ≤ i < N - 1) comnnects Vertex a_i and b_i. For each pair of vertices u and v (0 ≤ u, v < N), we define the distance d(u, v) as the number of edges in the path u-v.

It is expected that one of the vertices will be invaded by aliens from outer space. Snuke wants to immediately identify that vertex when the invasion happens. To do so, he has decided to install an antenna on some vertices.

First, he decides the number of antennas, K (1 ≤ K ≤ N). Then, he chooses K different vertices, x_0, x_1, ..., x_{K - 1}, on which he installs Antenna 0, 1, ..., K - 1, respectively. If Vertex v is invaded by aliens, Antenna k (0 ≤ k < K) will output the distance d(x_k, v). Based on these K outputs, Snuke will identify the vertex that is invaded. Thus, in order to identify the invaded vertex no matter which one is invaded, the following condition must hold:

• For each vertex u (0 ≤ u < N), consider the vector (d(x_0, u), ..., d(x_{K - 1}, u)). These N vectors are distinct.

Find the minumum value of K, the number of antennas, when the condition is satisfied.

Constraints

• 2 ≤ N ≤ 10^5
• 0 ≤ a_i, b_i < N
• The given graph is a tree.

Sample Input 1

5
0 1
0 2
0 3
3 4

Sample Output 1

2

For example, install an antenna on Vertex 1 and 3. Then, the following five vectors are distinct:

• (d(1, 0), d(3, 0)) = (1, 1)
• (d(1, 1), d(3, 1)) = (0, 2)
• (d(1, 2), d(3, 2)) = (2, 2)
• (d(1, 3), d(3, 3)) = (2, 0)
• (d(1, 4), d(3, 4)) = (3, 1)

Sample Input 2

2
0 1

Sample Output 2

1

For example, install an antenna on Vertex 0.

Sample Input 3

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

Sample Output 3

3

For example, install an antenna on Vertex 0, 4, 9.

Problem Statement

You are given a tree with N vertices. The vertices are numbered 0 through N-1, and the edges are numbered 1 through N-1. Edge i connects Vertex x_i and y_i, and has a value a_i. You can perform the following operation any number of times:

• Choose a simple path and a non-negative integer x, then for each edge e that belongs to the path, change a_e by executing a_e ← a_e ⊕ x (⊕ denotes XOR).

Your objective is to have a_e = 0 for all edges e. Find the minimum number of operations required to achieve it.

Constraints

• 2 ≤ N ≤ 10^5
• 0 ≤ x_i,y_i ≤ N-1
• 0 ≤ a_i ≤ 15
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

The objective can be achieved in three operations, as follows:

• First, choose the path connecting Vertex 1, 2, and x = 1.
• Then, choose the path connecting Vertex 2, 3, and x = 2.
• Lastly, choose the path connecting Vertex 0, 4, and x = 4.

Sample Input 2

2
1 0 0

Sample Output 2

0

Problem Statement

There is a bridge that connects the left and right banks of a river. There are 2 N doors placed at different positions on this bridge, painted in some colors. The colors of the doors are represented by integers from 1 through N. For each k (1 \leq k \leq N), there are exactly two doors painted in Color k.

Snuke decides to cross the bridge from the left bank to the right bank. He will keep on walking to the right, but the following event will happen while doing so:

• At the moment Snuke touches a door painted in Color k (1 \leq k \leq N), he teleports to the right side of the other door painted in Color k.

It can be shown that he will eventually get to the right bank.

For each i (1 \leq i \leq 2 N - 1), the section between the i-th and (i + 1)-th doors from the left will be referred to as Section i. After crossing the bridge, Snuke recorded whether or not he walked through Section i, for each i (1 \leq i \leq 2 N - 1). This record is given to you as a string s of length 2 N - 1. For each i (1 \leq i \leq 2 N - 1), if Snuke walked through Section i, the i-th character in s is 1; otherwise, the i-th character is 0.

Figure: A possible arrangement of doors for Sample Input 3

Determine if there exists an arrangement of doors that is consistent with the record. If it exists, construct one such arrangement.

Constraints

• 1 \leq N \leq 10^5
• |s| = 2 N - 1
• s consists of 0 and 1.

Sample Input 1

2
010

Sample Output 1

Yes
1 1 2 2

Sample Input 2

2
001

Sample Output 2

No

Sample Input 3

3
10110

Sample Output 3

Yes
1 3 2 1 2 3

The figure below is identical to the one in the statement.

Sample Input 4

3
10101

Sample Output 4

No

Sample Input 5

6
00111011100

Sample Output 5

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

Problem Statement

You are given a rooted tree with N vertices. The vertices are numbered 0, 1, ..., N-1. The root is Vertex 0, and the parent of Vertex i (i = 1, 2, ..., N-1) is Vertex p_i.

Initially, an integer a_i is written in Vertex i. Here, (a_0, a_1, ..., a_{N-1}) is a permutation of (0, 1, ..., N-1).

You can execute the following operation at most 25 000 times. Do it so that the value written in Vertex i becomes i.

• Choose a vertex and call it v. Consider the path connecting Vertex 0 and v.
• Rotate the values written on the path. That is, For each edge (i, p_i) along the path, replace the value written in Vertex p_i with the value written in Vertex i (just before this operation), and replace the value of v with the value written in Vertex 0 (just before this operation).
• You may choose Vertex 0, in which case the operation does nothing.

Constraints

• 2 \leq N \leq 2000
• 0 \leq p_i \leq i-1
• (a_0, a_1, ..., a_{N-1}) is a permutation of (0, 1, ..., N-1).

Sample Input 1

5
0 1 2 3
2 4 0 1 3

Sample Output 1

2
3
4

• After the first operation, the values written in Vertex 0, 1, .., 4 are 4, 0, 1, 2, 3.

Sample Input 2

5
0 1 2 2
4 3 1 2 0

Sample Output 2

3
4
3
1

• After the first operation, the values written in Vertex 0, 1, .., 4 are 3, 1, 0, 2, 4.
• After the second operation, the values written in Vertex 0, 1, .., 4 are 1, 0, 2, 3, 4.

Problem Statement

You are given an H \times W grid. The square at the top-left corner will be represented by (0, 0), and the square at the bottom-right corner will be represented by (H-1, W-1).

Of those squares, N squares (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) are painted black, and the other squares are painted white.

Let the shortest distance between white squares A and B be the minimum number of moves required to reach B from A visiting only white squares, where one can travel to an adjacent square sharing a side (up, down, left or right) in one move.

Since there are H × W - N white squares in total, there are _{(H×W-N)}C_2 ways to choose two of the white squares.

For each of these _{(H×W-N)}C_2 ways, find the shortest distance between the chosen squares, then find the sum of all those distances, modulo 1 000 000 007=10^9+7.

Constraints

• 1 \leq H, W \leq 10^6
• 1 \leq N \leq 30
• 0 \leq x_i \leq H-1
• 0 \leq y_i \leq W-1
• If i \neq j, then either x_i \neq x_j or y_i \neq y_j.
• There is at least one white square.
• For every pair of white squares A and B, it is possible to reach B from A visiting only white squares.

Sample Input 1

2 3
1
1 1

Sample Output 1

20

We have the following grid (.: a white square, #: a black square).

...
.#.

Let us assign a letter to each white square as follows:

ABC
D#E

Then, we have:

• dist(A, B) = 1
• dist(A, C) = 2
• dist(A, D) = 1
• dist(A, E) = 3
• dist(B, C) = 1
• dist(B, D) = 2
• dist(B, E) = 2
• dist(C, D) = 3
• dist(C, E) = 1
• dist(D, E) = 4

where dist(A, B) is the shortest distance between A and B. The sum of these distances is 20.

Sample Input 2

2 3
1
1 2

Sample Output 2

16

Let us assign a letter to each white square as follows:

ABC
DE#

Then, we have:

• dist(A, B) = 1
• dist(A, C) = 2
• dist(A, D) = 1
• dist(A, E) = 2
• dist(B, C) = 1
• dist(B, D) = 2
• dist(B, E) = 1
• dist(C, D) = 3
• dist(C, E) = 2
• dist(D, E) = 1

The sum of these distances is 16.

Sample Input 3

3 3
1
1 1

Sample Output 3

64

Sample Input 4

4 4
4
0 1
1 1
2 1
2 2

Sample Output 4

268

Sample Input 5

1000000 1000000
1
0 0

Sample Output 5

333211937

Problem Statement

We have a rectangular parallelepiped of dimensions A×B×C, divided into 1×1×1 small cubes. The small cubes have coordinates from (0, 0, 0) through (A-1, B-1, C-1).

Let p, q and r be integers. Consider the following set of abc small cubes:

\{(\ (p + i) mod A, (q + j) mod B, (r + k) mod C\ ) | i, j and k are integers satisfying 0 ≤ i < a, 0 ≤ j < b, 0 ≤ k < c \}

A set of small cubes that can be expressed in the above format using some integers p, q and r, is called a torus cuboid of size a×b×c.

Find the number of the sets of torus cuboids of size a×b×c that satisfy the following condition, modulo 10^9+7:

• No two torus cuboids in the set have intersection.
• The union of all torus cuboids in the set is the whole rectangular parallelepiped of dimensions A×B×C.

Constraints

• 1 ≤ a < A ≤ 100
• 1 ≤ b < B ≤ 100
• 1 ≤ c < C ≤ 100
• All input values are integers.

Sample Input 1

1 1 1 2 2 2

Sample Output 1

1

Sample Input 2

2 2 2 4 4 4

Sample Output 2

744

Sample Input 3

2 3 4 6 7 8

Sample Output 3

0

Sample Input 4

2 3 4 98 99 100

Sample Output 4

471975164