Routing table lookup is a critical step for routers when forwarding IP packets. Typically, an entry in a routing table consists of a destination address, a mask, a next-hop address, and other auxiliary information. For example:

When a router receives an IP packet, it compares the destination IP address in the packet with each entry in the routing table, selects the matching and most specific entry, and forwards the packet to the next hop specified in that entry.

The matching process involves converting the destination address in the packet and the destination address in the routing entry into binary strings. If the mask length is $x$, the first $x$ bits of the two binary strings are compared. If they are identical, the entry is considered a match.

The most specific entry is defined as the matching entry with the longest mask length when multiple entries match. This can also be understood as the entry with the most matching binary bits.

The operation of converting an IP address into a binary string involves converting the $4$ integers in the address (each in the range $0$ to $255$) into $8$-bit binary numbers, and then concatenating them in order to obtain a $32$-bit binary string. For example, 192.168.1.253 becomes 11000000 10101000 00000001 11111101 in binary.

Taking the packet destination address 8.8.8.8 as an example, we illustrate the matching process in the routing table above:

The table above shows the addresses converted into binary strings, with the bits to be compared (determined by the mask length) marked in red. Comparing the red parts with the destination address in the packet, we can see that 0.0.0.0/1, 8.8.8.0/24, and 8.8.8.8/32 all match. The router selects the entry with the longest mask length (/32), which is 8.8.8.8/32, and forwards the packet to its corresponding next-hop address 192.168.1.253.

In actual core routers, routing tables are usually large (the global internet routing table currently has nearly $600,000$ records) and continue to expand as new devices are connected. To analyze the impact of routing table changes on packet forwarding, network engineers want to know how many times the selected routing entry for a specific IP address changes over a period of time (a change is defined as selecting a different entry due to factors like the most specific match; the next-hop address is not considered).

Input

The first line contains an integer $M$, representing the total number of operations. The next $M$ lines each describe an operation. There are two types of operations:

A <D>/<L> Where $D$ is an IP address and $L$ is an integer $(1 \leq L \leq 32)$. Add an entry to the routing table with destination address $D$ and mask length $L$. The next-hop address is omitted as it is not used.

Q <D> <a> <b> Where $D$ is an IP address, and $a, b$ are positive integers $(a \leq b)$. Query how many times the selected routing entry for destination address $D$ changed during the period from the $a$-th to the $b$-th addition operation (inclusive). It is guaranteed that there are at least $b$ entries in the table at the time of the query.

Output

Contains several lines, each containing a single integer, corresponding to each query operation in order.

Examples

Input 1

47
A 128.0.0.0/1
A 128.0.0.0/4
A 100.200.20.0/23
A 241.170.96.0/20
A 74.128.0.0/17
A 193.24.0.0/14
A 128.0.0.0/19
A 128.0.0.0/13
A 128.0.0.0/5
A 128.0.0.0/11
A 128.0.0.0/12
A 192.0.0.0/7
Q 192.0.0.13 1 8
A 128.0.0.0/8
Q 128.0.0.15 1 8
A 74.0.0.0/8
A 96.0.0.0/4
A 193.24.0.0/23
A 100.192.0.0/11
A 128.0.0.0/18
A 128.0.0.0/20
Q 128.0.0.4 1 13
A 192.0.0.0/8
A 192.0.0.0/22
Q 128.0.0.7 1 14
A 128.0.0.0/23
A 74.128.0.0/14
A 128.0.0.0/14
A 128.0.0.0/25
A 74.128.0.0/12
Q 128.0.0.9 2 17
A 96.0.0.0/11
A 64.0.0.0/2
A 74.0.0.0/26
A 100.192.0.0/18
A 128.0.0.0/27
A 193.24.0.0/18
Q 128.0.0.3 4 21
Q 74.128.0.12 3 24
A 128.0.0.0/9
A 193.24.0.0/22
Q 128.0.0.7 4 24
A 192.0.0.0/10
Q 128.0.0.3 2 23
A 100.192.0.0/10
Q 241.170.96.2 1 26
Q 100.192.0.4 4 24

Output 1

1
3
3
3
2
2
1
3
4
2
2

Subtasks

One way to interpret a query is: ignore all other query operations and only consider the addition operations. First, clear the routing table, then perform the $1$st to $(a-1)$-th addition operations. Then, count the number of times the matching entry changes during the $a$-th to $b$-th addition operations.

For $30\%$ of the data, $M \leq 10^3$;

For $100\%$ of the data, $M \leq 10^6$.

Given an entry with mask length $L$, it is guaranteed that after converting the destination address to a binary string, the last $32 - L$ bits are all $0$. Additionally, it is guaranteed that no two entries with the same destination address and mask length will be added.