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:
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
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.
11 8 tamarind red mint coconut ginger peanut pudina tomato periperisauce hummus redchilli 2 1 4 2 3 10 2 1 7 2 4 11 1 8 papaya 2 4 11 1 4 onion 2 1 7
For the first 3 events, answers are as follows: