Problem K. King of Port ≡

Statement

A section of a container terminal in a port is represented as a coordinate system with (x, y) axes. The height of a section is limited to 15 containers. A maximum of 50,000 containers can be added to a section. Each container is described by 3 numbers (x, y, size), containers are numbered from 1.

A container of size 1 takes up one space (x, y), a container of size 2 takes up two spaces (x, y) and (x + 1, y). There is guaranteed to be no empty space under the container. Containers are gradually added to the section, and simultaneously with the addition of containers, requests are received: "how many containers must be previously removed from the section in order to remove the container with number c_j?". To remove a container, it is necessary to remove all containers that are located directly above the container being removed.

This image illustrates the first example:

Input format

The first line of the input file contains a single integer N. Next are N lines of two types:

• If the first character in the line is "I", then this is a request to add a container. The "I" character is followed by three integers x_i, y_i, size_i.
• If the first character in the line is "C", then this is a request for the number of containers that need to be extracted to extract the container with number c_j. The "C" character is followed by the integer c_j.

Output format

The output file should contain the same number of integers as the number of requests of the second type received.

Constraints

1 ≤ N ≤ 500000

0 ≤ x ≤ 10000

0 ≤ y ≤ 14

1 ≤ size ≤ 2

Container with number c_j is already guaranteed to be added to the section.

A maximum of 50,000 containers can be added to a section.

Sample tests

21
I 0 0 1
I 1 0 1
I 2 0 1
I 3 0 2
I 5 0 1
I 6 0 1
I 0 1 2
I 2 1 2
I 4 1 1
I 5 1 1
I 6 1 1
I 3 2 2
I 5 2 1
I 6 2 1
I 4 3 2
I 6 3 1
I 4 4 1
I 5 4 2
C 4
C 6
C 8

6
4
4

11
I 0 0 2
C 1
I 0 1 1
I 1 1 1
C 1
I 0 2 2
C 1
I 2 0 2
C 5
I 0 3 1
C 1

0
2
3
0
4