K. Idiosyncratic Item Boxes
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

UTCS Roadshow has created a brand new custom track for their Mario Kart Tournament! Banana Split is a very technical track - except for the straightaway with $$$10^9$$$ item box spawn points in a row (a driver could theoretically hit a billion consecutive item boxes without veering off course). The item box spawn points can be viewed as a row from a trackside view, and the points can be numbered from $$$1$$$ to $$$10^9$$$, inclusive, from left to right.

At the beginning of a race, none of the item box spawn points have any active item boxes. During the race, however, the internals of the Mario Kart operating system must respond to $$$Q$$$ queries about the changing state of the giant row of spawn points. There are two types of queries $$$C$$$ and $$$S$$$, that correspond to IDs $$$1$$$ and $$$2$$$, respectively.

  • Type $$$C$$$: Output the number of item boxes a kart hits between spawn points $$$x$$$ and $$$y$$$, inclusive, assuming that sufficient time has passed for all previously hit boxes to respawn.
  • Type $$$S$$$: Force all the item boxes between spawn points $$$x$$$ and $$$y$$$, inclusive, to start spawning in repeatedly for karts to encounter. If an item box spawn point is already active, it will continue to spawn item boxes.

Can you help answer all queries of type $$$C$$$ to make Banana Split run smoothly?

Input

The first line of input contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), representing the number of queries to be responded to. The next $$$Q$$$ lines of input each contain three space-separated integers $$$t$$$ ($$$t = 1, 2$$$), $$$x$$$, and $$$y$$$ ($$$1 \leq x \leq y \leq 10^9$$$) representing the query type, $$$x$$$, and $$$y$$$, respectively, as described above.

Output

For each query of type $$$C$$$, output the answer as a single non-negative integer on its own line.

Example
Input
10
2 7 12
2 10 11
1 10 12
2 8 13
1 10 11
2 11 15
1 10 10
2 8 11
2 7 9
2 3 4
Output
3
2
1