路由表中每一项对应了一个形如 1011101????????????????????????? 的规则，会匹配指定的前缀为给定形式的 ip。 当有多个规则匹配时，前缀最长的生效。同一时刻不会有多个匹配的规则的前缀一样长。每一个时刻，会有一条规则被加入，或者之前被加入的某条规则会过期。给一系列 ip，问每一个 ip 在一个给定的时间区间内匹配到的生效规则变了几次？
例如，有一系列事件：
- Add 110
- Add 11
- Del 110
- Del 11
- Add 110
那么,IP 地址 11011101001001010101011101000010 在这五个时刻之后匹配到的生效规则分别是：
110（第一条），110（第一条），11（第二条），- 空，
110（第三条）。
其中，在第二个事件后到第五个事件后的这段过程中，一共变了3次。
输入格式
第一行两个整数 $N$ 和 $Q$，表示时刻的个数与查询的个数。
接下来 $N$ 行，每行描述一个事件。事件的格式是
Add s表示新建一个规则，匹配前缀为s的所有 ip.Del s表示把当前前缀s对应的规则删掉（过期）。保证之前有这样的一条规则还没被删。
接下来 $Q$ 行，每行一个 ip 与两个整数 $a,b$，表示查询 ip 在第 $a$ 个事件（从 1 开始数）后到第 $b$ 个事件后的这段时间里，这个 ip 匹配到的生效规则变化的次数。 ip 用01字符串来表示。
输出格式
对每个查询，输出所求的变化次数.
样例数据
样例 1 输入
5 1 Add 110 Add 11 Del 110 Del 11 Add 110 11011101001001010101011101000010 2 5
样例 1 输出
3
子任务
对于 $100\%$ 的数据，$1 \le N, Q \le 10^5$，串长不超过32
| Test Case | $N,Q \leq$ |
|---|---|
| 1 | $10$ |
| 2 | $100$ |
| 3 | $1\,000$ |
| 4 | $2\,000$ |
| 5 | $10\,000$ |
| 6 | $20\,000$ |
| 7 | $30\,000$ |
| 8 | $50\,000$ |
| 9 | $80\,000$ |
| 10 | $10^5$ |