AT_abc403_e [ABC403E] Forbidden Prefix

There are two multisets of strings, $ X $ and $ Y $ , both initially empty. You are given $ Q $ queries to process in order. In the $ i $ -th query, you receive an integer $ T_i $ and a string $ S_i $ . If $ T_i=1 $ , insert $ S_i $ into $ X $ ; if $ T_i=2 $ , insert $ S_i $ into $ Y $ . After processing each query, print this value: - the number of strings in $ Y $ that have no element of $ X $ as a prefix.

The input is given from Standard Input in the following format: > $ Q $ $ T_1\ S_1 $ $ T_2\ S_2 $ $ \vdots $ $ T_Q\ S_Q $

Print $ Q $ lines. The $ i $ -th line $ (1 \leq i \leq Q) $ should contain the count after processing the $ i $ -th query.

### Sample Explanation 1 The counts after processing the queries for $ i=1,2,3,4 $ are as follows. - $ i=1 $ : $ Y $ is empty, so the count is $ 0 $ . - $ i=2 $ : `watcoder` has no element of $ X $ as a prefix, so the count is $ 1 $ . - $ i=3 $ : `watcoder` has no element of $ X $ as a prefix, while `atcoder` has `at` as a prefix, so the count is $ 1 $ . - $ i=4 $ : `watcoder` has `wa` as a prefix, and `atcoder` has `at` as a prefix, so the count is $ 0 $ . ### Constraints - $ Q $ is an integer between $ 1 $ and $ 2 \times 10^5 $ , inclusive. - $ T_i \in \{1,2\} $ - Each $ S_i $ is a string of length between $ 1 $ and $ 5\times 10^5 $ , inclusive, consisting of lowercase English letters. - $ \displaystyle \sum_{i=1}^Q |S_i| \leq 5 \times 10^5 $