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:

1. A person updates his order to get a new kind of dish.
2. 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.