Problem Statement

There are N users on WAtCoder, numbered from 1 to N, and M contest pages, numbered from 1 to M. Initially, no user has view permission for any contest page.

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

• 1 X Y: Grant user X view permission for contest page Y.
• 2 X: Grant user X view permission for all contest pages.
• 3 X Y: Answer whether user X can view contest page Y.

It is possible for a user to be granted permission for the same contest page multiple times.

Constraints

• 1 \le N \le 2\times 10^5
• 1 \le M \le 2\times 10^5
• 1 \le Q \le 2\times 10^5
• 1 \le X \le N
• 1 \le Y \le M
• All input values are integers.

Sample Input 1

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

Sample Output 1

No
Yes
Yes

• In the first query, user 1 is granted permission to view contest page 2.
• At the second query, user 1 can view only page 2; they cannot view page 1, so print No.
• At the third query, user 1 can view page 2, so print Yes.
• In the fourth query, user 2 is granted permission to view all pages.
• At the fifth query, user 2 can view pages 1,2,3; they can view page 3, so print Yes.

Sample Input 2

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

Sample Output 2

No
No
No
Yes

Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

• 1 \leq N \leq 2\times 10^5
• The records are consistent. That is:
  • 1\leq A_i \leq 2i-1.
  • A_i are distinct integers.

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

• Amoeba 1 is zero generations away from amoeba 1.
• Amoeba 2 is one generation away from amoeba 1.
• Amoeba 3 is one generation away from amoeba 1.
• Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
• Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is ice or rock, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

• if the j-th character of S_i is ., square (i,j) is ice;
• if the j-th character of S_i is #, square (i,j) is rock.

The outer periphery of this grid (all squares in the 1-st row, N-th row, 1-st column, M-th column) is rock.

Initially, the player rests on the square (2,2), which is ice.
The player can make the following move zero or more times.

• First, specify the direction of movement: up, down, left, or right.
• Then, keep moving in that direction until the player bumps against a rock. Formally, keep doing the following:
  • if the next square in the direction of movement is ice, go to that square and keep moving;
  • if the next square in the direction of movement is rock, stay in the current square and stop moving.

Find the number of ice squares the player can touch (pass or rest on).

Constraints

• 3 \le N,M \le 200
• S_i is a string of length M consisting of # and ..
• Square (i, j) is rock if i=1, i=N, j=1, or j=M.
• Square (2,2) is ice.

Sample Input 1

6 6
######
#....#
#.#..#
#..#.#
#....#
######

Sample Output 1

12

For instance, the player can rest on (5,5) by moving as follows:

• (2,2) \rightarrow (5,2) \rightarrow (5,5).

The player can pass (2,4) by moving as follows:

• (2,2) \rightarrow (2,5), passing (2,4) in the process.

The player cannot pass or rest on (3,4).

Sample Input 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

Sample Output 2

215

Problem Statement

A country has N cities and M power plants, which we collectively call places.
The places are numbered 1,2,\dots,N+M, among which Places 1,2,\dots,N are the cities and Places N+1,N+2,\dots,N+M are the power plants.

This country has E power lines. Power Line i (1 \le i \le E) connects Place U_i and Place V_i bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.

Now, Q events will happen. In the i-th (1 \le i \le Q) event, Power Line X_i breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.

Find the number of electrified cities right after each events.

Constraints

• All values in input are integers.
• 1 \le N,M
• N+M \le 2 \times 10^5
• 1 \le Q \le E \le 5 \times 10^5
• 1 \le U_i < V_i \le N+M
• If i \neq j, then U_i \neq U_j or V_i \neq V_j.
• 1 \le X_i \le E
• X_i are distinct.

Sample Input 1

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

Sample Output 1

4
4
2
2
2
1

Initially, all cities are electrified.

• The 1-st event breaks Power Line 3 that connects Point 5 and Point 10.
  • Now City 5 is no longer electrified, while 4 cities remain electrified.
• The 2-nd event breaks Power Line 5 that connects Point 2 and Point 9.
• The 3-rd event breaks Power Line 8 that connects Point 3 and Point 6.
  • Now Cities 2 and 3 are no longer electrified, while 2 cities remain electrified.
• The 4-th event breaks Power Line 10 that connects Point 1 and Point 8.
• The 5-th event breaks Power Line 2 that connects Point 4 and Point 10.
• The 6-th event breaks Power Line 7 that connects Point 1 and Point 7.
  • Now City 1 is no longer electrified, while 1 city remains electrified.

Problem Statement

You are given Q triples of integers (a_1, b_1, d_1), (a_2, b_2, d_2), \ldots, (a_Q, b_Q, d_Q).

A subset S of the set \lbrace 1, 2, \ldots, Q\rbrace is defined to be a good set if there exists an integer sequence (X_1, X_2, \ldots, X_N) of length N that satisfies:

X_{a_i} - X_{b_i} = d_i for all i \in S.

Starting with S as an empty set, perform the following operation for i = 1, 2, \ldots, Q in this order:

If S \cup \lbrace i \rbrace is a good set, then replace S with S \cup \lbrace i \rbrace.

Print all elements of the final set S in ascending order.

Constraints

• All input values are integers.
• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq a_i, b_i \leq N
• -10^9 \leq d_i \leq 10^9

Sample Input 1

3 5
1 2 2
3 2 -3
2 1 -1
3 3 0
1 3 5

Sample Output 1

1 2 4 5

Starting with S as an empty set, perform the operation described in the problem statement for i = 1, 2, 3, 4, 5 in this order, as follows.

• For i = 1, the set S \cup \lbrace i \rbrace = \lbrace 1 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, 4) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1\rbrace.
• For i = 2, the set S \cup \lbrace i \rbrace = \lbrace 1, 2 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, -2) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1, 2\rbrace.
• For i = 3, the set S \cup \lbrace i \rbrace = \lbrace 1, 2, 3 \rbrace is not a good set.
• For i = 4, the set S \cup \lbrace i \rbrace = \lbrace 1, 2, 4 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, -2) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1, 2, 4\rbrace.
• For i = 5, the set S \cup \lbrace i \rbrace = \lbrace 1, 2, 4, 5 \rbrace is a good set, because (X_1, X_2, X_3) = (3, 1, -2) satisfies the condition in the problem statement, for example, so replace S with \lbrace 1, 2, 4, 5\rbrace.

Therefore, the final set S is \lbrace 1, 2, 4, 5\rbrace.

Sample Input 2

200000 1
1 1 1

Sample Output 2

The final set S is empty.

Sample Input 3

5 20
4 2 125421359
2 5 -191096267
3 4 -42422908
3 5 -180492387
3 3 174861038
2 3 -82998451
3 4 -134761089
3 1 -57159320
5 2 191096267
2 4 -120557647
4 2 125421359
2 3 142216401
4 5 -96172984
3 5 -108097816
1 5 -50938496
1 2 140157771
5 4 65674908
4 3 35196193
4 4 0
3 4 188711840

Sample Output 3

1 2 3 6 8 9 11 14 15 16 17 19