题目描述

路由表中每一项对应了一个形如 1011101????????????????????????? 的规则，会匹配指定的前缀为给定形式的 $\texttt{ip}$。

当有多个规则匹配时，前缀最长的生效。同一时刻不会有多个匹配的规则的前缀一样长。每一个时刻，会有一条规则被加入，或者之前被加入的某条规则会过期。

给一系列 $\texttt{ip}$，问每一个 $\texttt{ip}$ 在一个给定的时间区间内匹配到的生效规则变了几次？

例如，有一系列事件：

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

那么，$\texttt{ip}$ 地址 11011101001001010101011101000010 在这五个时刻之后匹配到的生效规则分别是：

$110$ (第一条)，
$110$ (第一条)，
$11$ (第二条)，
空，
$110$ (第三条)。

其中，在第二个事件后到第五个事件后的这段过程中，一共变了 $3$ 次。

输入格式

第一行两个正整数 $n,q$，表示事件数有询问数。
接下来 $n$ 行，每行描述一个事件，格式为：

$\texttt{Add}$ $s$ 表示新建一个规则，匹配前缀为 $s$ 的所有 $\texttt{ip}$。
$\texttt{Del}$ $s$ 表示把当前前缀 $s$ 对应的规则删掉(过期)。保证之前有这样的一条规则还没被删。

接下来 $q$ 行，每行一个 $\texttt{ip}$ 与两个正整数 $a,b$，表示查询在第 $a$ 个事件后到第 $b$ 个事件的这段时间里，这个 $\texttt{ip}$ 匹配到的生效规则变化的次数。 $\texttt{ip}$ 用01字符串来表示。

输出格式

对于每次查询，输出一行一个整数表示答案。

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

3

提示

【数据范围】

$1\le n,q \le 10^5$