问题描述

现有两个字符串多重集合 $X$ 和 $Y$，初始时均为空集合。

你需要依次处理 $Q$ 个查询。第 $i$ 个查询由一个整数 $T_i$ 和一个字符串 $S_i$ 组成：

• 若 $T_i = 1$，则将 $S_i$ 加入多重集合 $X$；
• 若 $T_i = 2$，则将 $S_i$ 加入多重集合 $Y$。

在每个查询处理完成后，请输出当前多重集合 $Y$ 中满足不以 $X$ 中任何字符串作为前缀的字符串个数。

输入格式

第一行输入一个正整数 $Q$，表示查询的数量。

接下来输入 $Q$ 行，第 $i$ 行包含一个整数 $T_i$ 和一个字符串 $S_i$，中间用一个空格隔开。

输出格式

输出共 $Q$ 行，第 $i$ 行输出一个整数，表示在处理完第 $i$ 个查询后满足条件的字符串数量。

样例输入 1

4
1 at
2 watcoder
2 atcoder
1 wa

样例输出 1

0
1
1
0

样例输入 2

10
1 w
1 avko
2 atcoder
1 bzginn
2 beginner
1 atco
2 contest
1 ntxcdg
1 atc
1 contest

样例输出 2

0
0
1
1
2
1
2
2
2
1

说明

样例 1 解释：

• $i = 1$：$X = \{\text{"at"}\}, Y = \varnothing$，$Y$ 中元素个数为 $0$，答案为 $0$；
• $i = 2$：$X = \{\text{"at"}\}, Y = \{\text{"watcoder"}\}$，watcoder 不以 at 为前缀，答案为 $1$；
• $i = 3$：$X = \{\text{"at"}\}, Y = \{\text{"watcoder"}, \text{"atcoder"}\}$，atcoder 以 at 为前缀，仅 watcoder 满足条件，答案为 $1$；
• $i = 4$：$X = \{\text{"at"}, \text{"wa"}\}$，watcoder 以 wa 为前缀，两者均不满足条件，答案为 $0$。

评测数据规模

对于所有评测数据：

• $1 \leq Q \leq 2 \times 10^5$
• $T_i \in \{1, 2\} \quad (1 \leq i \leq Q)$
• 字符串 $S_i$ 仅由小写英文字母组成，且 $1 \leq |S_i| \leq 5 \times 10^5$
• 所有查询中字符串长度之和满足 $\sum_{i=1}^Q |S_i| \leq 5 \times 10^5$
• 所有输入均为整数或合法字符串