CRAYON - Crayon

no tags 

Background

Mary love painting so much, but as we know she can't draw very well. There is no one appreciate her works, so she come up with a puzzle with herself...

Description

There are only one case in each input file, the first line is a integer N (N <= 1,000,00) denoted the total operations executed by Mary. Then following N lines, each line is one of the folling operations.

  • D L R: draw a segment [L, R], 1 <= L <= R <= 1,000,000,000
  • C I: clear the ith added segment. It’s guaranteed that the every added segment will be cleared only once.
  • Q L R: query the number of segment sharing at least a common point with interval [L, R]. 1 <= L <= R <= 1,000,000,000.

Input

n

(then following n operations ... )

Output

(for each query, print the result on a single line ... )

Example

Input:
6
D 1 3
D 2 4
Q 2 3
D 2 4
C 2
Q 2 3

Output:
2
2

hide comments
the_analyst753: 2018-11-09 17:21:55

i think there is problem with the constraints it should be 10^6

:D: 2013-02-10 00:30:39

Clear index is 1-based. Clear operations do not affect the indexes.

xiaodao: 2013-01-24 19:46:34

Sorry for Inconvenience ... but Mary is a character in a small RPG game called Ib ...

[Rampage] Blue.Mary: 2013-01-23 08:18:31

[Reminder] This is NOT my problem.


Added by:xiaodao
Date:2013-01-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem