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

You are given a sequence of N positive numbers, A = (A_1, A_2, \dots, A_N). Find the sequence B = (B_1, B_2, \dots, B_N) of length N defined as follows.

• For i = 1, 2, \dots, N, define B_i as follows:
  • Let B_i be the most recent position before i where an element equal to A_i appeared. If such a position does not exist, let B_i = -1.
    More precisely, if there exists a positive integer j such that A_i = A_j and j < i, let B_i be the largest such j. If no such j exists, let B_i = -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5
1 2 1 1 3

Sample Output 1

-1 -1 1 3 -1

• i = 1: There is no 1 before A_1 = 1, so B_1 = -1.
• i = 2: There is no 2 before A_2 = 2, so B_2 = -1.
• i = 3: The most recent occurrence of 1 before A_3 = 1 is A_1, so B_3 = 1.
• i = 4: The most recent occurrence of 1 before A_4 = 1 is A_3, so B_4 = 3.
• i = 5: There is no 3 before A_5 = 3, so B_5 = -1.

Sample Input 2

4
1 1000000000 1000000000 1

Sample Output 2

-1 -1 2 1

Problem Statement

There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.

For each i=1, 2, \ldots, N in this order, the following will be done.

• If s_i is L, insert i to the immediate left of i-1 in A.
• If s_i is R, insert i to the immediate right of i-1 in A.

Find the final contents of A.

Constraints

• 1\leq N \leq 5\times 10^5
• N is an integer.
• |S| = N
• s_i is L or R.

Sample Input 1

5
LRRLR

Sample Output 1

1 2 4 5 3 0

Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).

Sample Input 2

7
LLLLLLL

Sample Output 2

7 6 5 4 3 2 1 0

Problem Statement

There is a length-N sequence A=(A_1,\ldots,A_N) that is a permutation of 1,\ldots,N.

While you do not know A, you know that A_{X_i}<A_{Y_i} for M pairs of integers (X_i,Y_i).

Can A be uniquely determined? If it is possible, find A.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1\leq X_i,Y_i \leq N
• All values in the input are integers.
• There is an A consistent with the input.

Sample Input 1

3 2
3 1
2 3

Sample Output 1

Yes
3 1 2

We can uniquely determine that A=(3,1,2).

Sample Input 2

3 2
3 1
3 2

Sample Output 2

No

Two sequences (2,3,1) and (3,2,1) can be A.

Sample Input 3

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

Sample Output 3

Yes
1 2 3 4

Problem Statement

There is a tree T with N vertices. The vertices are labeled as vertex 1, vertex 2, \ldots, vertex N, and the edges are labeled as edge 1, edge 2, \ldots, edge (N-1).
Edge i (1\leq i\leq N-1) connects vertices U_i and V_i.
Each vertex has a weight; initially, the weight of every vertex is 1.

You are given Q queries to process in order. Each query is of one of the following two types:

• 1 x w : Increase the weight of vertex x by w.
• 2 y : If edge y were removed, the tree T would be split into two subtrees (connected components). For each subtree, let its weight be the sum of the weights of its vertices. Output the difference between the weights of the two subtrees.

For a query of the second type, it can be proved that removing any edge of T always splits it into exactly two subtrees.
Note that queries of the second type do not actually delete remove the edge.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq U_i, V_i \leq N
• 1 \leq Q \leq 3 \times 10^5
• 1 \leq x \leq N
• 1 \leq w \leq 1000
• 1 \leq y \leq N-1
• All input values are integers.
• The given graph is a tree.
• There is at least one query of the second type.

Sample Input 1

6
1 2
1 3
2 4
4 5
4 6
5
2 1
1 1 3
2 1
1 4 10
2 5

Sample Output 1

2
1
17

The structure of the tree T and the vertex numbering are as shown on the left of the figure below. Initially, the weight of every vertex is 1.

In the 1st query, consider deleting edge 1.
The tree splits into the subtree containing vertex 1 and the subtree containing vertex 2. The subtree with vertex 1 has weight 2; the subtree with vertex 2 has weight 4. Output the difference, 2 (figure below, right).

The 2nd query increases the weight of vertex 1 by 3.

In the 3rd query, consider deleting edge 1.
The subtree with vertex 1 has weight 5; the subtree with vertex 2 has weight 4. Output the difference, 1 (figure below, left).

The 4th query increases the weight of vertex 4 by 10.

In the 5th query, consider deleting edge 5.
The tree splits into the subtree containing vertex 4 and the subtree consisting only of vertex 6.
The subtree with vertex 4 has weight 18; the subtree with vertex 6 has weight 1. Output the difference, 17 (figure below, right).

Thus, output the answers to the queries of second type in order: 2, 1, and 17, separated by newlines.