A chef has recently opened a new restaurant to serve his special dishes. He has a list of ingredients from which he makes them. Each ingredient is denoted by a unique lowercase letter. Thus, a dish is represented as a string of ingredients possibly with repititions. There are \(N\) people in his restaurant currently each of whom have ordered some dished.

You are given a collection of dishes with duplicates possibly. The chef can serve one of his favorite dishes from them if he is able to reorder all their ingredients (i.e. a permutation of the concatenation of all the strings) such that they form a palindrome. You have to facilitate the day-to-day working of the restaurant. There are two types of events happening in the restaurant:

A person updates his order to get a new kind of dish.
People in the range \([L, R]\) wants to know the number of non-empty subsets of \(A[L \ldots R]\) from which the Chef can make one of his favorite dish.

You are given the initial orders of the people. Therefore, you have to process \(Q\) events of the mentioned types.

Input format

First Line: Two integers \(N, Q\) denoting the number of people currently in the restaurant and the numbers events happening over time
Second Line: \(N\) space seperated strings consisting only of lowercase letters, \(A_1, A_2, A_3,\ldots, A_N\) where \(A_i\) denotes the chutney initially ordered by the \(i^{th}\) person
Next \(Q\) Lines: Event of any of the above two type in the following format:
1. \(1 \text{ } i \text{ } X \): The \(i^{th}\) person has updated his order to a new chutney \(X\): \(A[i] = X\)
2. \(2 \text{ } L \text{ } R\): Count the number of subsets satisfying the constraint described above.

Output format

Print the required answer for each event of the \(2^{nd}\) type.

Constraints

\(1 \le N \le 2\cdot10^5 \)

\(1 \le i \le N, 1 \le L \le R \le N\)

\(1 \le Q \le 5 \cdot 10^4\)

\(1 \le \sum |A_i|, \sum |X| \le 10^6\)

There is at least one event of \(2^{nd}\) type.