# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Good and Evil

By Peregrine_Falcon · Limits 1s, 512 MB

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

InputOutput
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.

### Statistics

65% Solution Ratio

user.545264Earliest, 5M ago

Nasif_44thFastest, 0.1s

prajjwal07Lightest, 14 MB

Md_AbdullahShortest, 1571B