Problem Statement

You have an empty bag. You are given Q queries, which must be processed in order.

There are three types of queries.

• 1 x : Put one ball with the integer x written on it into the bag.
• 2 x : Remove one ball with the integer x written on it from the bag and discard it. It is guaranteed that the bag has a ball with the integer x written on it when this query is given.
• 3 : Print the number of different integers written on the balls in the bag.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• 1 \leq x \leq 10^{6}
• When a query of the second type is given, the bag has a ball with the integer x written on it.
• There is at least one query of the third type.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
2
3

Initially, the bag is empty.

For the first query 1 3, a ball with the integer 3 written on it enters the bag.

For the second query 1 1, a ball with the integer 1 written on it enters the bag.

For the third query 1 4, a ball with the integer 4 written on it enters the bag.

For the fourth query 3, the bag has balls with the integers 1, 3, 4, so print 3.

For the fifth query 2 1, a ball with the integer 1 written on it is removed from the bag.

For the sixth query 3, the bag has balls with the integers 3, 4, so print 2.

For the seventh query 1 5, a ball with the integer 5 written on it enters the bag.

For the eighth query 3, the bag has balls with the integers 3, 4, 5, so print 3.

Sample Input 2

8
1 2
1 2
3
2 2
1 4
1 4
2 2
3

Sample Output 2

1
1

Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

• It is a string of length L+1 consisting of o and -.
• Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

• There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

• 1\leq N\leq 2\times10^5
• S is a string of length N consisting of o and -.

Sample Input 1

10
o-oooo---o

Sample Output 1

4

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.

Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.

Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

Sample Output 3

7

Problem Statement

You are given a string S consisting of A, B, C.

Let S^{(0)}:=S. For i=1,2,3,\ldots, let S^{(i)} be the result of simultaneously replacing the characters of S^{(i-1)} as follows: A → BC, B → CA, C → AB.

Answer Q queries. The i-th query is as follows.

• Print the k_i-th character from the beginning of S^{(t_i)}.

Constraints

• S is a string of length between 1 and 10^5 (inclusive) consisting of A, B, C.
• 1 \leq Q \leq 10^5
• 0 \leq t_i \leq 10^{18}
• 1 \leq k_i \leq \min(10^{18}, the length of S^{(t_i)})
• Q, t_i, k_i are integers.

Sample Input 1

ABC
4
0 1
1 1
1 3
1 6

Sample Output 1

A
B
C
B

We have S^{(0)}=ABC, S^{(1)}=BCCAAB.

Thus, the answers to the queries are A, B, C, B in the given order.

Sample Input 2

CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 407121144297426665

Sample Output 2

A
A
C
A
A

Problem Statement

In the nation of Atcoder, there are N cities numbered 1 to N, and M trains numbered 1 to M. Train i departs from city A_i at time S_i and arrives at city B_i at time T_i.

Given a positive integer X_1, find a way to set non-negative integers X_2,\ldots,X_M that satisfies the following condition with the minimum possible value of X_2+\ldots+X_M.

• Condition: For all pairs (i,j) satisfying 1 \leq i,j \leq M, if B_i=A_j and T_i \leq S_j, then T_i+X_i \leq S_j+X_j.
  • In other words, for any pair of trains that are originally possible to transfer between, it is still possible to transfer even after delaying the departure and arrival times of each train i by X_i.

It can be proved that such a way to set X_2,\ldots,X_M with the minimum possible value of X_2+\ldots+X_M is unique.

Constraints

• 2 \leq N \leq 2\times 10^5
• 2 \leq M \leq 2\times 10^5
• 1 \leq A_i,B_i \leq N
• A_i \neq B_i
• 0 \leq S_i < T_i \leq 10^9
• 1 \leq X_1 \leq 10^9
• All input values are integers.

Sample Input 1

3 6 15
1 2 10 20
1 2 20 30
2 3 25 40
2 3 35 50
3 1 15 30
3 1 45 60

Sample Output 1

0 10 0 0 5

The arrival of train 1 from city 1 to 2 is delayed by 15 and becomes time 35.
To allow transfer from train 1 to 3 in city 2, the departure of train 3 is delayed by 10, making it depart at time 35 and arrive at time 50.
Further, to allow transfer from train 3 to 6 in city 3, the departure of train 6 is delayed by 5, making it depart at time 50.
Other trains can operate without delay while still allowing transfers between originally transferable trains, so (X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5) satisfies the condition.
Moreover, there is no solution with a smaller sum that satisfies the condition, so this is the answer.

Sample Input 2

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

Sample Output 2

100 100 100 100 100 100 100 100

Sample Input 3

4 4 10
1 2 0 1
1 2 0 10
2 3 100 200
2 4 100 200

Sample Output 3

0 0 0

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