Problem Description

Each entry in the routing table corresponds to a rule of the form 1011101?????????????????????????, which matches an $\texttt{ip}$ whose prefix fits the given pattern.

When multiple rules match, the one with the longest prefix takes effect. At any time, there will not be multiple matching rules with the same prefix length. At each moment, either a rule is added, or some previously added rule expires.

Given a list of $\texttt{ip}$ addresses, for each $\texttt{ip}$, ask how many times the effective matched rule changes within a given time interval.

For example, suppose there is a sequence of events:

$\texttt{Add}$ $110$
$\texttt{Add}$ $11$
$\texttt{Del}$ $110$
$\texttt{Del}$ $11$
$\texttt{Add}$ $110$

Then, for the $\texttt{ip}$ address 11011101001001010101011101000010, the effective matched rules after these five moments are:

$110$ (the first one),
$110$ (the first one),
$11$ (the second one),
empty,
$110$ (the third one).

During the period from after the second event to after the fifth event, it changes a total of $3$ times.

Input Format

The first line contains two positive integers $n,q$, representing the number of events and the number of queries.

The next $n$ lines each describe an event in the following format:

$\texttt{Add}$ $s$ means creating a new rule that matches all $\texttt{ip}$ addresses with prefix $s$.
$\texttt{Del}$ $s$ means deleting (expiring) the current rule corresponding to prefix $s$. It is guaranteed that such a rule exists and has not been deleted before.

The next $q$ lines each contain an $\texttt{ip}$ and two positive integers $a,b$, meaning: during the time period from after the $a$-th event to the $b$-th event, how many times does the effective rule matched by this $\texttt{ip}$ change? The $\texttt{ip}$ is given as a binary string of 0 and 1.

Output Format

For each query, output one line with an integer representing the answer.

5 1
Add 110
Add 11
Del 110
Del 11
Add 110
11011101001001010101011101000010 2 5

3

Hint

Constraints

• $1\le n,q \le 10^5$.
• $|s|\le32$.
• Each $\texttt{ip}$ has length $32$.

Translated by ChatGPT 5