Starting from 0, perform multiple additions/subtractions of $d \times 10^k$, where $d$ is a digit from 0 to 9. You are required to support queries for the number of occurrences of a specific digit in the current result.

Input

The first line contains an integer $n$, the number of operations.

The following $n$ lines each contain one of the following three types of operations:

• A d k, which means to add $d \times 10^k$ to the current result;
• S d k, which means to subtract $d \times 10^k$ from the current result;
• Q d, which means to query how many times the digit $d$ appears in the current result.

Output

For each query, output one line containing an integer representing the number of occurrences of that digit in the result at the time of the query.

Examples

Input 1

11
A 1 2
Q 0
Q 1
Q 2
S 4 1
Q 0
Q 1
Q 6
S 6 1
Q 0
Q 1

Output 1

2
1
0
1
0
1
1
0

Note

The first operation A adds 100, and the two S operations subtract 40 and 60, respectively.

Constraints

For 100% of the data, $1 \le n \le 50\,000$, $1 \le k \le 10^9$, $0 \le d \le 9$, and the result is always non-negative during the operations.

For 20% of the data, $n \le 1000$, $k \le 15$.

For 30% of the data, $n \le 5000$, $k \le 5000$.