Inside each of us, there is the seed of both good and evil. It's a constant struggle as to which one will win. And one cannot exist without the other. ~Eric Burdon

Unlike human beings, segments have a fixed part of good and evil. Let’s take a segment from $L$ to $R$ for example. Let $M$$=$$\lfloor{((L+R)/2)}\rfloor$ rounded down to nearest integer point. The part $L$ to $M$ is good and the rest of the segment is evil.

Initially, you have an empty collection of integer segments. You have to perform $Q$ operations of three types in the collection:

Type 1: Add a segment from $L$ to $R$ to the collection. Type 2: Remove an existing segment from $L$ to $R$ from the collection. It is guaranteed that the input segment exists in the collection. If there are multiple copies of the same segment, only one will be removed. Type 3: Given integer point $X$, find the number of good and evil parts of segments is intersected by point X.

Input

The first line of input consists of an integer $Q$$(3 \leq Q \leq 2×10^5)$ number of operations to be performed. Each of the next $Q$ lines consists of one of three types of operations. Type 1: $1$$L$$R$$(1 \leq L < R \leq 10^{16})$. Type 2: $2$$L$$R$$(1 \leq L < R \leq 10^{16})$. Type 3: $3$$X$$(1 \leq X \leq 10^{16})$.

For 40 Points: $1≤ Q,L,R ≤10^3$ For 100 Points: Original constraints.

Output

For each of the Type 3 queries, output two integers $G$ and $E$ separated by space in each line. $G$ is the number of the good segments and $E$ is the number of evil segments that point $X$ is part of.

Sample

Input

Output

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

1 1
2 0
0 1
0 0

The first operation is to add a segment from 1 to 9. Here from 1 to 5 is good and 6 to 9 is evil. The second operation adding another segment from 3 to 9. Here, 3 to 6 is good and 7 to 9 is evil. The third operation is a query for point 6. Point 6 is intersecting with the first segment’s evil part and the second segment’s good part.