L. Trivial
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To save the country from a dangerous virus, Domestos has reached out to you for help - create a better recording system for the country's medical system.

The current medical system uses a multiset (hence, it allows duplication) of strings to record the different patients.

Since there are no records in the multiset, Domestos has implemented two basic operations to create and get information on the different strings in the multiset. Those are:

  • $$$1$$$ $$$index$$$ $$$character$$$: Appends the $$$character$$$ to the end of the string situated on the $$$index$$$-th position. If $$$index$$$ is with one bigger than the cardinal of the multiset, a new string containing only the $$$character$$$ is appended to the multiset. Note that this operation does not affect the order of the other strings within the multiset. For a better understanding, please refer to the example.
  • $$$2$$$ $$$index$$$: For the string situated on the $$$index$$$-th position, say how many strings from the multiset are in the same equivalence class with it. For two strings to be in the same equivalence class, they need to have the same distinct palindromic substrings (a substring is a consecutive subsequence). A string is palindromic when reading it backwards is the same as forwards.

    For example, given the following multiset: $$$\{"aaaabxa", "aaabxaa", "abxaaaa", "dcxaaaa"\}$$$, applying the operation on the second index would generate the answer 1, whereas applying it on the third one would generate the answer 2.

Since Domestos is having limited capacity, the number of $$$1^{st}$$$ operations is $$$N \leq 4*10^5$$$ and moreover the total number of operations is capped to $$$M \leq 8*10^5$$$.

Domestos believes that this problem is trivial for you to solve and that might climb you on the top of the standings!

Input

The first line of the input will contain the number $$$M$$$, representing the total number of operations.

The following $$$M$$$ lines will contain each operation.

Output

You should output $$$M$$$-$$$N$$$ lines containing the output of each $$$2^{nd}$$$ operation.

Example
Input
12
1 1 a
1 1 b
1 1 a
2 1
1 2 a
2 2
1 3 a
2 3
1 2 b
2 2
1 2 a
2 2
Output
1
1
2
1
2
Note

After the first three operations the string "aba" is created and the $$$2^{nd}$$$ operation performed on it outputs 1 since there is just one string.

Then, an additional string is created, resulting into having two strings in the multiset: $$$\{"aba", "a"\}$$$. As those two string are not in the same equivalence class, the output of the $$$2^{nd}$$$ operation will be 1.

As the third string is created, the multiset will contain: $$$\{"aba", "a", "a"\}$$$. The third $$$2^{nd}$$$ operation will output 2 since the last two string are in the same equivalence class.

The last two $$$1^{st}$$$ operations basically equalise the second to the first string and hence the output of the last $$$2^{nd}$$$ operation will be also 2.