Each entry in the routing table corresponds to a rule in the form of 1011101?????????????????????????, which matches IP addresses with the specified prefix. When multiple rules match, the one with the longest prefix takes effect. At any given time, no two matching rules will have the same prefix length. At each moment, either a new rule is added, or a previously added rule expires. Given a series of IP addresses, for each IP, determine how many times the effective matching rule changes within a given time interval.

For example, consider a series of events: - Add 110 - Add 11 - Del 110 - Del 11 - Add 110

Then, for the IP address 11011101001001010101011101000010, the effective matching rules after these five moments are:

• 110 (first rule),
• 110 (first rule),
• 11 (second rule),
• None,
• 110 (third rule).

In the process from after the second event to after the fifth event, the effective rule changes 3 times.

Input

The first line contains two integers $N$ and $Q$, representing the number of moments and the number of queries, respectively.

The next $N$ lines each describe an event. The format of the events is:

• Add s means to create a new rule that matches all IP addresses with prefix s.
• Del s means to delete (expire) the current rule corresponding to prefix s. It is guaranteed that such a rule exists and has not been deleted yet.

The next $Q$ lines each contain an IP address and two integers $a$ and $b$, representing a query for the number of times the effective rule for this IP changes in the interval from after the $a$-th event (1-indexed) to after the $b$-th event. IP addresses are represented as binary strings.

Output

For each query, output the calculated number of changes.

Examples

Input 1

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

Output 1

3

Subtasks

For $100\%$ of the data, $1 \le N, Q \le 10^5$, and the string length does not exceed 32.