IP地址

题目描述

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

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

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

例如，有一系列事件：

\texttt{Add}Add 110110
\texttt{Add}Add 1111
\texttt{Del}Del 110110
\texttt{Del}Del 1111
\texttt{Add}Add 110110

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

110110 (第一条)，
110110 (第一条)，
1111 (第二条)，
空，
110110 (第三条)。

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

输入输出格式

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

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

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

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

输入输出样例

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

3

说明

【数据范围】

1\le n,q \le 10^51≤n,q≤105