You are friends with a genius inventor, and she needs your help with her latest invention. She has built a real life Tetris machine, which also doubles as an obstacle course / climbing wall. However, for safety reasons, she needs to know exactly how many blocks there are in any given column, at any stage in the game.

This ain't your grandma's game of Tetris. Instead of four-block clusters falling from the sky, there are rectangular slabs of blocks falling from the sky. These slabs have a start column index, an end column index, and a thickness value (indicating the number of rows). Also, the slabs will split into individual blocks to fill the space. Also, the slabs don't rotate or move from side to side; they just fall straight down. Additionally, the slabs always start falling from a height greater than anything currently in the game. So it's not really Tetris.

Here an example of this process for a rectangular slab of blocks from indexes 1 to 4 (zero indexed) with thickness 2.

.oooo...
.oooo...
x..xxx..
xx.xxx..
xxxxxx.x

...oo...
.oooo...
xooxxx..
xx.xxx..
xxxxxx.x

...oo...
.o.oo...
xooxxx..
xxoxxx..
xxxxxx.x

Your friend has given you a series of instructions and queries. Each instruction will be entered into her Tetris machine, including a starting position, end position, and thickness. Each query contains a column index, and you must answer that query by counting how many blocks are in that column. Note that every column starts off with zero blocks in it.

Soon, you get tired of running around and counting things. There's got to be an easier way to answer your friend's queries...

Input Specification

The first line has an integer \(n\), the number of instructions and queries.

The next \(n\) lines contain either instructions or queries.

Instructions are given by the letter D for drop, and then a space, and then three space-separated integers. These integers are \(s\), the first position in the, \(e\), the last position in the slab, and then \(r\), the number of rows in the slab.

Queries are given by the letter C for count, and then a space, and then a single integer. This integer is \(i\), the index of a column in the Tetris board.

Output Specification

For each query, output a line containing a single integer, the number of blocks currently in the given column. Do nothing for instructions.

Bounds

Note that this problem includes sub-problems of increasing difficulty worth different numbers of points.

20 points

\(0 < n \leq 100\)

\(0 \leq s, e, i < 100\)

\(0 < r \leq 100\)

80 points

\(0 < n \leq 5 \times 10^5\)

\(0 \leq s, e, i < 5 \times 10^5\)

\(0 < r \leq 100\)

Note that the 100 point input has a lot of input data, so you might need to use fast I/O methods.

For all sub-problems:

\(s \leq e\)

Sample Input

5
C 0
D 1 2 2
D 2 4 1
C 2
C 3

Sample Output

0
3
1