Crayon

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

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

Sample Input

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

Sample Output

2
2

Source

Classical

Manager

Information
Solved Number80
Submit Number283
Problem Tags
data structures
trees
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel