Description

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:

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.

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).

Input Format

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 <D>/<L>

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 <D> <a> <b>

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.

Output Format

Contains several lines. Each line has only one integer, corresponding to each query operation in order.

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

1
3
3
3
2
2
1
3
4
2
2

Hint

One way to understand a query is: ignore all other query operations and consider only the add operations. First clear the routing table, then perform the $1$-st to the $(a-1)$-th add operations. After that, count the number of times the match selection changes during the $a$-th to the $b$-th add operations.

For $30\%$ of the testdata, $M \le 10^3$.

For $100\%$ of the testdata, $M \le 10^6$.

For an entry with mask length $L$, the testdata guarantees that after converting the destination address into a binary string, the last $32-L$ bits are all $0$. In addition, it is guaranteed that no two added entries have both the same destination address and the same mask length.

Translated by ChatGPT 5