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