You have $N$ strings $S_{1}, S_{2}, S_{3}, ... , S_{N}$ of lowercase characters.  You’ll need to support $Q$ operations of two types. You have to process the operations/queries online. After each operations, you need to print how many strings are currently palindrome. A palindrome is a string that reads the same forward or backward.

Operattion Type 1: $1\;\;A\;\;B$ : That means $S_{B}$ will be added at the end of $S_{A}$ and $S_{B}$will be deleted. It is guaranteed that $A \neq B$ and $S_{B}$ will not be given in any other opertaion as it is deleted. 

Operattion Type 2: $2\;\;A\;\;K \;\; C$ : That means you need to insert character $C$ at $K'th$ position of $S_{A}$. 

Note that the operations are encoded. That is, you need to write an online solution, please read the input format carefully.

Input Format 

First line will contain two integers $N$ and $Q$ $(1 <= N, Q <= 10^5)$, they are number of strings and number of operations.

Each of next $N$ lines will contain a string of lowercase characters. Summation of lengths of initial $N$ strings <= $10^5$.

Each of the next $Q$ lines will describe a operation.

It contains one integer $OP$ $(1 <= OP <= 2)$ — the type of operation.

The given opeartions will be encoded in the following way: let $P_{r}$ be the number of palindromes that you have printed after executing the previous operation (initially, $P_{r} = 0$). 

•  If $OP = 1$, two integers follow, $A^\prime$ and $B ^\prime$ $( 0 <= A^\prime, B^\prime < 2^{30} )$. First, do the following: $A = A^\prime ⊕ P_{r}$ and $B = B^\prime ⊕ P_{r}$ $(1 <= A, B <= N)$. Now you'll execute the operation of first type, that is  $S_{B}$ will be added at the end of $S_{A}$ and $S_{B}$will be deleted.
• If $OP = 2$, two integers and a lowercase character follow, $A^\prime$, $K ^\prime$ and $C$ $( 0 <= A^\prime, K^\prime < 2^{30})$. First, do the following: $A = A^\prime ⊕ P_{r}$ and $K = K^\prime ⊕ P_{r}$  $(1 <= A <= N, 1 <= K <= |S_{A}|+1)$ . . Now you'll execute the operation of second type, which is insert character $C$ at $K'th$ position of $S_{A}$.  If $K = |S_{A}|+1$, then you need to append the character at the end of $S_{A}$.

Output Format 

After completeing each operation, print one integer - that is currently how many strings are palindrome. 

Constraints

For 10 points: $1 <= N, Q <= 10$ and summation of lengths of initial $N$ strings <= 100.

For full point: Original constarints.