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.