Routing Table Effective Rule Change Counting

Problem statement:

You are given a series of events on a routing table. Each event either adds or deletes a routing rule. Each rule is represented by a bit string (for example, 1011101) that stands for the fixed prefix of an IP address. An IP address is a binary string (for example, 11011101001001010101011101000010). A rule matches an IP address if the IP address begins with the rule's bit string. When multiple rules match an IP, the rule with the longest prefix is effective. It is guaranteed that at any moment, no two active rules have the same prefix length.

Initially, the routing table is empty. At each moment an event occurs that either adds a rule (Add) or deletes a rule (Del).

For each query, you are given two integers L and R along with an IP address. You should consider the state of the routing table immediately after events L to R (inclusive). For each of these states, determine which rule is effective for the given IP (if any) using the longest prefix match. Then count how many times the effective rule changes from one event state to the next within the interval.

Example:
Consider the sequence of events:

1. Add 110
2. Add 11
3. Del 110
4. Del 11
5. Add 110

For the IP 11011101001001010101011101000010 the effective rules after each event are as follows:

After event 1: 110
After event 2: 110
After event 3: 11
After event 4: (none)
After event 5: 110

Considering the interval from event 2 to event 5, the effective rule changes occur between events 2 and 3, 3 and 4, and 4 and 5 – a total of 3 changes.

inputFormat

Input Format:

The first line contains two integers N and Q, where N is the number of events and Q is the number of queries.

The next N lines each contain an event in one of the following formats:
• Add X
• Del X

Here, X is a non-empty binary string representing the fixed prefix of a rule. It is guaranteed that at any moment, there is at most one active rule for any given prefix length.

The next Q lines each describe a query and contain two integers L and R followed by a binary string ip. This means that you should consider the state of the routing table after events L through R (inclusive) and determine the number of times the effective rule for ip changes during that interval.

outputFormat

Output Format:

For each query, output a single integer on a new line representing the number of times the effective rule changes during the given time interval.

sample

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

3