P5768 [CQOI2016] Routing Table

Routing table lookup is an important step when a router forwards IP packets. Usually, each routing table entry consists of a destination address, a mask, a Next Hop address, and other auxiliary information. For example: | Destination Address | Mask Length | Next Hop | | :----------: | :----------: | :----------: | | 0.0.0.0 | /1 | 192.168.1.1 | | 128.0.0.0 | /1 | 192.168.1.1 | | 8.8.8.0 | /24 | 192.168.1.1 | | 8.8.8.8 | /32 | 192.168.1.253 | When a router receives an IP packet, it compares the destination IP address in the packet with the entries in the routing table one by one, chooses an entry that matches and is **most specific**, and forwards the packet to the Next Hop specified by that entry. The matching process is: convert the destination address in the packet and the destination address in an entry into binary strings, then check the mask length of the entry. If the mask length is $x$, compare the first $x$ bits of the two binary strings. If they are the same, it is considered a match. **Most specific** means: if multiple entries match, choose the one with the largest mask length. It can also be understood as the entry that matches the most bits. The operation of converting an IP address into a binary string is: convert the $4$ integers in the address (each must be in the range $0$ to $255$) into $8$-bit binary numbers, and then concatenate them in order to obtain a $32$-bit binary string. For example, after converting $192.168.1.253$ into a binary string, we get $11000000$ $10101000$ $00000001$ $11111101$. We use the packet destination address $8.8.8.8$ as an example to illustrate the matching process in the routing table above. | 8.8.8.8 | 00001000 00001000 00001000 00001000 | | :----------: | :----------: | | 0.0.0.0/1 | $\color{red}{0}$0000000 00000000 00000000 00000000 | | 128.0.0.0/1 | $\color{red}{1}$0000000 00000000 00000000 00000000 | | 8.8.8.0/24 | $\color{red}{00001000}$ $\color{red}{00001000 }$ $\color{red}{00001000}$ 00000000 | | 8.8.8.8/32 | $\color{red}{00001000}$ $\color{red}{00001000 }$ $\color{red}{00001000}$ $\color{red}{00001000}$ | In the table above, all addresses are converted to binary strings, and the bits to be compared (determined by the mask length) are marked in red. By 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$ can all match. The router chooses the entry with the longest mask length (/32), i.e. $8.8.8.8/32$, and forwards the packet to its corresponding Next Hop address $192.168.1.253$. In real core routers, routing tables are usually large (the global Internet routing table is now close to $60$万 entries), and they keep expanding as new devices join. To analyze how routing table changes affect forwarding, a network engineer wants to know, over a period of time, how many times the selected routing table entry for a certain IP address changes (a change means that a different entry is chosen due to factors such as most specific match; the Next Hop address is not considered).

The first line contains an integer $M$, indicating that there are $M$ operations in total. The next $M$ lines each describe one operation. There are two types of operations: `A /` Here $D$ is an IP address, and $L$ is an integer ($1 \le L \le 32$). Add an entry to the routing table, with destination address $D$ and mask length $L$. The Next Hop address is omitted because it is not used. `Q ` Here $D$ is an IP address, and $a,b$ are positive integers ($a \le b$). Query, during the period from the $a$-th to the $b$-th added entry (including $a$ and $b$), how many times the selected routing table entry for destination address $D$ changes. It is guaranteed that at the time of the query, the table contains at least $b$ entries.