Problem Statement

We have a multiset of integers S, which is initially empty.

Given Q queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an x into S.

• 2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).

• 3 : Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq Q
• When a query of type 3 is given, S is not empty.
• All values in input are integers.

Sample Input 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

Sample Output 1

1
5
4

The multiset S transitions as follows.

• 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
• 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
• 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
• 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
• 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
• 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
• 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
• 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type 3, nothing should be printed.

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

• Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i \leq N
• All values in input are integers.

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
• Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
• Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9

Problem Statement

A function f(x) defined for non-negative integers x satisfies the following conditions.

• f(0) = 1.
• f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor) for any positive integer k.

Here, \lfloor A \rfloor denotes the value of A rounded down to an integer.

Find f(N).

Constraints

• N is an integer satisfying 0 \le N \le 10^{18}.

Sample Input 1

2

Sample Output 1

3

We have f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3.

Sample Input 2

0

Sample Output 2

1

Sample Input 3

100

Sample Output 3

55

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertices U_i and V_i.

There are 2^N ways to paint each vertex red or blue. Find the number, modulo 998244353, of such ways that satisfy all of the following conditions:

• There are exactly K vertices painted red.
• There is an even number of edges connecting vertices painted in different colors.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
• (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

4 4 2
1 2
1 3
2 3
3 4

Sample Output 1

2

The following two ways satisfy the conditions.

• Paint Vertices 1 and 2 red and Vertices 3 and 4 blue.
• Paint Vertices 3 and 4 red and Vertices 1 and 2 blue.

In either of the ways above, the 2-nd and 3-rd edges connect vertices painted in different colors.

Sample Input 2

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

Sample Output 2

64

Problem Statement

There is a graph G with N vertices and 0 edges on a 2-dimensional plane. The vertices are numbered from 1 to N, and vertex i is located at coordinates (x_i,y_i).

For vertices u and v of G, the distance d(u,v) between u and v is defined as the Manhattan distance d(u,v)=|x_u-x_v|+|y_u-y_v|.

Also, for two connected components A and B of G, let V(A) and V(B) be the vertex sets of A and B, respectively. The distance d(A,B) between A and B is defined as d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace.

Process Q queries as described below. Each query is one of the following three types:

• 1 a b : Let n be the number of vertices in G. Add vertex n+1 to G with coordinates (x_{n+1},y_{n+1})=(a,b).
• 2 : Let n be the number of vertices in G and m be the number of connected components.
  • If m=1, output -1.
  • If m\geq 2, merge all connected components with the minimum distance and output the value of that minimum distance. Formally, let the connected components of G be A_1,A_2,\ldots,A_m and let \displaystyle k=\min_{1\leq i\lt j\leq m} d(A_i,A_j). For all pairs of vertices (u,v)\ (1\leq u\lt v\leq n) that are not in the same connected component and satisfy d(u,v)=k, add an edge between vertices u and v. Then, output k.
• 3 u v : If vertices u and v are in the same connected component, output Yes; otherwise, output No.

Constraints

• 2\leq N\leq 1500
• 1\leq Q\leq 1500
• 0\leq x_i,y_i\leq 10^9
• For queries of type 1, 0\leq a,b\leq 10^9.
• For queries of type 3, let n be the number of vertices in G just before processing that query, then 1\leq u\lt v\leq n.
• All input values are integers.

Sample Input 1

4 11
3 4
3 3
7 3
2 2
3 1 2
2
3 1 2
1 6 4
2
3 2 5
2
3 2 5
2
1 2 2
2

Sample Output 1

No
1
Yes
2
No
3
Yes
-1
0

Initially, vertices 1,2,3,4 are located at coordinates (3,4),(3,3),(7,3),(2,2), respectively.

• For the 1st query, vertices 1 and 2 are not connected, so output No.
• For the 2nd query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace. The minimum distance between different connected components is 1, and an edge is added between vertices 1 and 2. Output 1.
• For the 3rd query, vertices 1 and 2 are connected, so output Yes.
• For the 4th query, add vertex 5 at coordinates (6,4).
• For the 5th query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace. The minimum distance between different connected components is 2, and edges are added between vertices 2 and 4 and between vertices 3 and 5. Output 2.
• For the 6th query, vertices 2 and 5 are not connected, so output No.
• For the 7th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace. The minimum distance between different connected components is 3, and an edge is added between vertices 1 and 5. Output 3.
• For the 8th query, vertices 2 and 5 are connected, so output Yes.
• For the 9th query, there is 1 connected component, so output -1.
• For the 10th query, add vertex 6 at coordinates (2,2).
• For the 11th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace. The minimum distance between different connected components is 0, and an edge is added between vertices 4 and 6. Output 0.