vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ayu loves distinct letter sequences ,a distinct letter sequence is defined by a sequence of small case english alphabets such that no character appears more then once.
But however there are two phrases that she doesn't like these phrases are "kar" and "shi" and she is given a sequence of distinct characters and she wonders how many such sequences she can form using all the characters such that these phrases don't occur.
Help her finding the number of such sequences.
New Year Gift - It is guaranteed that for sequences of length greater then 6 letters k,a,r,s,h,i will be present(we thought of being generous, thank us later :)).

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each line consists of a string $S$ (3<=s.length<=18) of distinct characters.

-----Output:-----
Print the number of sequences that can be formed by permuting all the characters such that phrases "kar" and "shi" don't occur.

-----Constraints-----
- $1 \leq T \leq 10$
- $3 \leq S.length \leq 18$

-----Sample Input:-----
2
karp
abcd

-----Sample Output:-----
22
24

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We will call a string that can be obtained by concatenating two equal strings an even string. For example, `xyzxyz` and `aaaaaa` are even, while `ababab` and `xyzxy` are not.

For a non-empty string S, we will define f(S) as the shortest even string that can be obtained by appending one or more characters to the end of S. For example, f(`abaaba`)=`abaababaab`. It can be shown that f(S) is uniquely determined for a non-empty string S.

You are given an even string S consisting of lowercase English letters. For each letter in the lowercase English alphabet, find the number of its occurrences from the l-th character through the r-th character of f^{10^{100}} (S).

Here, f^{10^{100}} (S) is the string f(f(f( ... f(S) ... ))) obtained by applying f to S 10^{100} times.

Constraints

* 2 \leq |S| \leq 2\times 10^5
* 1 \leq l \leq r \leq 10^{18}
* S is an even string consisting of lowercase English letters.
* l and r are integers.

Input

Input is given from Standard Input in the following format:


S
l r


Output

Print 26 integers in a line with spaces in between. The i-th integer should be the number of the occurrences of the i-th letter in the lowercase English alphabet from the l-th character through the r-th character of f^{10^{100}} (S).

Examples

Input

abaaba
6 10


Output

3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


Input

xx
1 1000000000000000000


Output

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1000000000000000000 0 0


Input

vgxgpuamkvgxgvgxgpuamkvgxg
1 1000000000000000000


Output

87167725689669676 0 0 0 0 0 282080685775825810 0 0 0 87167725689669676 0 87167725689669676 0 0 87167725689669676 0 0 0 0 87167725689669676 141040342887912905 0 141040342887912905 0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Joisino is planning to record N TV programs with recorders.

The TV can receive C channels numbered 1 through C.

The i-th program that she wants to record will be broadcast from time s_i to time t_i (including time s_i but not t_i) on Channel c_i.

Here, there will never be more than one program that are broadcast on the same channel at the same time.

When the recorder is recording a channel from time S to time T (including time S but not T), it cannot record other channels from time S-0.5 to time T (including time S-0.5 but not T).

Find the minimum number of recorders required to record the channels so that all the N programs are completely recorded.

Constraints

* 1≤N≤10^5
* 1≤C≤30
* 1≤s_i<t_i≤10^5
* 1≤c_i≤C
* If c_i=c_j and i≠j, either t_i≤s_j or s_i≥t_j.
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N C
s_1 t_1 c_1
:
s_N t_N c_N


Output

When the minimum required number of recorders is x, print the value of x.

Examples

Input

3 2
1 7 2
7 8 1
8 12 1


Output

2


Input

3 4
1 3 2
3 4 4
1 4 3


Output

3


Input

9 4
56 60 4
33 37 2
89 90 3
32 43 1
67 68 3
49 51 3
31 32 3
70 71 1
11 12 3


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have to create a method "compoundArray" which should take as input two int arrays of different length and return one int array with numbers of both arrays shuffled one by one. 
```Example: 
Input - {1,2,3,4,5,6} and {9,8,7,6} 
Output - {1,9,2,8,3,7,4,6,5,6}
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Lecture

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have a new professor of graph theory and he speaks very quickly. You come up with the following plan to keep up with his lecture and make notes.

You know two languages, and the professor is giving the lecture in the first one. The words in both languages consist of lowercase English characters, each language consists of several words. For each language, all words are distinct, i.e. they are spelled differently. Moreover, the words of these languages have a one-to-one correspondence, that is, for each word in each language, there exists exactly one word in the other language having has the same meaning.

You can write down every word the professor says in either the first language or the second language. Of course, during the lecture you write down each word in the language in which the word is shorter. In case of equal lengths of the corresponding words you prefer the word of the first language.

You are given the text of the lecture the professor is going to read. Find out how the lecture will be recorded in your notes.

Input Specification:
The first line contains two integers, *n* and *m* (1<=≤<=*n*<=≤<=3000, 1<=≤<=*m*<=≤<=3000) — the number of words in the professor's lecture and the number of words in each of these languages.

The following *m* lines contain the words. The *i*-th line contains two strings *a**i*, *b**i* meaning that the word *a**i* belongs to the first language, the word *b**i* belongs to the second language, and these two words have the same meaning. It is guaranteed that no word occurs in both languages, and each word occurs in its language exactly once.

The next line contains *n* space-separated strings *c*1,<=*c*2,<=...,<=*c**n* — the text of the lecture. It is guaranteed that each of the strings *c**i* belongs to the set of strings {*a*1,<=*a*2,<=... *a**m*}.

All the strings in the input are non-empty, each consisting of no more than 10 lowercase English letters.

Output Specification:
Output exactly *n* words: how you will record the lecture in your notebook. Output the words of the lecture in the same order as in the input.

Demo Input:
['4 3\ncodeforces codesecrof\ncontest round\nletter message\ncodeforces contest letter contest\n', '5 3\njoll wuqrd\neuzf un\nhbnyiyc rsoqqveh\nhbnyiyc joll joll euzf joll\n']

Demo Output:
['codeforces round letter round\n', 'hbnyiyc joll joll un joll\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a usual chat user on the most famous streaming platform. Of course, there are some moments when you just want to chill and spam something.

More precisely, you want to spam the emote triangle of size $k$. It consists of $2k-1$ messages. The first message consists of one emote, the second one — of two emotes, ..., the $k$-th one — of $k$ emotes, the $k+1$-th one — of $k-1$ emotes, ..., and the last one — of one emote.

For example, the emote triangle for $k=3$ consists of $5$ messages:

Of course, most of the channels have auto moderation. Auto moderator of the current chat will ban you right after you spam at least $x$ emotes in succession (you can assume you are the only user in the chat). Now you are interested — how many messages will you write before getting banned? Or maybe you will not get banned at all (i.e. will write all $2k-1$ messages and complete your emote triangle successfully)? Note that if you get banned as a result of writing a message, this message is also counted.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The next $t$ lines describe test cases.

The only line of the test case contains integers $k$ and $x$ ($1 \le k \le 10^9; 1 \le x \le 10^{18}$).


-----Output-----

For each test case, print the number of messages you will write before getting banned for the corresponding values $k$ and $x$.


-----Examples-----

Input
7
4 6
4 7
1 2
3 7
2 5
100 1
1000000000 923456789987654321
Output
3
4
1
4
3
1
1608737403


-----Note-----

Let's analyze the test cases of the example.

In the first test case, you write three messages containing $1$, $2$ and $3$ emotes respectively, and since $1 + 2 + 3 \ge 6$, you get banned after that.

In the second test case, you write four messages containing $1$, $2$, $3$ and $4$ emotes respectively, and since $1 + 2 + 3 + 4 \ge 7$, you get banned after that.

In the third test case, you write one message containing exactly $1$ emote. It doesn't get you banned, since $1 < 2$, but you have already finished posting your emote triangle. So you wrote one message successfully.

In the fourth test case, you write four messages containing $1$, $2$, $3$ and $2$ emotes respectively, and since $1 + 2 + 3 + 2 \ge 7$, you get banned after that.

In the fifth test case, you write three messages containing $1$, $2$ and $1$ emote respectively. It doesn't get you banned, since $1 + 2 + 1 < 5$, but you have already finished posting your emote triangle. So you wrote three messages successfully.

In the sixth test case, since $x = 1$, you get banned as soon as you send your first message.

The seventh test case is too large to analyze, so we'll skip it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Rectangle and Square

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Petya very much likes rectangles and especially squares. Recently he has received 8 points on the plane as a gift from his mother. The points are pairwise distinct. Petya decided to split them into two sets each containing 4 points so that the points from the first set lay at the vertexes of some square and the points from the second set lay at the vertexes of a rectangle. Each point of initial 8 should belong to exactly one set. It is acceptable for a rectangle from the second set was also a square. If there are several partitions, Petya will be satisfied by any of them. Help him find such partition. Note that the rectangle and the square from the partition should have non-zero areas. The sides of the figures do not have to be parallel to the coordinate axes, though it might be the case.

Input Specification:
You are given 8 pairs of integers, a pair per line — the coordinates of the points Petya has. The absolute value of all coordinates does not exceed 104. It is guaranteed that no two points coincide.

Output Specification:
Print in the first output line "YES" (without the quotes), if the desired partition exists. In the second line output 4 space-separated numbers — point indexes from the input, which lie at the vertexes of the square. The points are numbered starting from 1. The numbers can be printed in any order. In the third line print the indexes of points lying at the vertexes of a rectangle in the similar format. All printed numbers should be pairwise distinct.

If the required partition does not exist, the first line should contain the word "NO" (without the quotes), after which no output is needed.

Demo Input:
['0 0\n10 11\n10 0\n0 11\n1 1\n2 2\n2 1\n1 2\n', '0 0\n1 1\n2 2\n3 3\n4 4\n5 5\n6 6\n7 7\n', '0 0\n4 4\n4 0\n0 4\n1 2\n2 3\n3 2\n2 1\n']

Demo Output:
['YES\n5 6 7 8\n1 2 3 4\n', 'NO\n', 'YES\n1 2 3 4\n5 6 7 8\n']

Note:
Pay attention to the third example: the figures do not necessarily have to be parallel to the coordinate axes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer sequence $1, 2, \dots, n$. You have to divide it into two sets $A$ and $B$ in such a way that each element belongs to exactly one set and $|sum(A) - sum(B)|$ is minimum possible.

The value $|x|$ is the absolute value of $x$ and $sum(S)$ is the sum of elements of the set $S$.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^9$).


-----Output-----

Print one integer — the minimum possible value of $|sum(A) - sum(B)|$ if you divide the initial sequence $1, 2, \dots, n$ into two sets $A$ and $B$.


-----Examples-----
Input
3

Output
0

Input
5

Output
1

Input
6

Output
1



-----Note-----

Some (not all) possible answers to examples:

In the first example you can divide the initial sequence into sets $A = \{1, 2\}$ and $B = \{3\}$ so the answer is $0$.

In the second example you can divide the initial sequence into sets $A = \{1, 3, 4\}$ and $B = \{2, 5\}$ so the answer is $1$.

In the third example you can divide the initial sequence into sets $A = \{1, 4, 5\}$ and $B = \{2, 3, 6\}$ so the answer is $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Counterexample 

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Your friend has recently learned about coprime numbers. A pair of numbers {*a*,<=*b*} is called coprime if the maximum number that divides both *a* and *b* is equal to one. 

Your friend often comes up with different statements. He has recently supposed that if the pair (*a*,<=*b*) is coprime and the pair (*b*,<=*c*) is coprime, then the pair (*a*,<=*c*) is coprime. 

You want to find a counterexample for your friend's statement. Therefore, your task is to find three distinct numbers (*a*,<=*b*,<=*c*), for which the statement is false, and the numbers meet the condition *l*<=≤<=*a*<=&lt;<=*b*<=&lt;<=*c*<=≤<=*r*. 

More specifically, you need to find three numbers (*a*,<=*b*,<=*c*), such that *l*<=≤<=*a*<=&lt;<=*b*<=&lt;<=*c*<=≤<=*r*, pairs (*a*,<=*b*) and (*b*,<=*c*) are coprime, and pair (*a*,<=*c*) is not coprime.

Input Specification:
The single line contains two positive space-separated integers *l*, *r* (1<=≤<=*l*<=≤<=*r*<=≤<=1018; *r*<=-<=*l*<=≤<=50).

Output Specification:
Print three positive space-separated integers *a*, *b*, *c* — three distinct numbers (*a*,<=*b*,<=*c*) that form the counterexample. If there are several solutions, you are allowed to print any of them. The numbers must be printed in ascending order. 

If the counterexample does not exist, print the single number -1.

Demo Input:
['2 4\n', '10 11\n', '900000000000000009 900000000000000029\n']

Demo Output:
['2 3 4\n', '-1\n', '900000000000000009 900000000000000010 900000000000000021\n']

Note:
In the first sample pair (2, 4) is not coprime and pairs (2, 3) and (3, 4) are. 

In the second sample you cannot form a group of three distinct integers, so the answer is -1. 

In the third sample it is easy to see that numbers 900000000000000009 and 900000000000000021 are divisible by three.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Spoonerize... with numbers... numberize?... numboonerize?... noonerize? ...anyway!  If you don't yet know what a spoonerism is and haven't yet tried my spoonerism kata, please do [check it out](http://www.codewars.com/kata/spoonerize-me) first.

You will create a function which takes an array of two positive integers, spoonerizes them, and returns the positive difference between them as a single number or ```0``` if the numbers are equal:
```
[123, 456] = 423 - 156 = 267
```
Your code must test that all array items are numbers and return ```"invalid array"``` if it finds that either item is not a number.  The provided array will always contain 2 elements.

When the inputs are valid, they will always be integers, no floats will be passed.  However, you must take into account that the numbers will be of varying magnitude, between and within test cases.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is organizing a party.
At the party, each guest will receive one or more snack pieces.
Takahashi predicts that the number of guests at this party will be A or B.
Find the minimum number of pieces that can be evenly distributed to the guests in both of the cases predicted.
We assume that a piece cannot be divided and distributed to multiple guests.

-----Constraints-----
 - 1 \leq A, B \leq 10^5
 - A \neq B
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Print the minimum number of pieces that can be evenly distributed to the guests in both of the cases with A guests and B guests.

-----Sample Input-----
2 3

-----Sample Output-----
6

When we have six snack pieces, each guest can take three pieces if we have two guests, and each guest can take two if we have three guests.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S. The task is to count the number of substrings which contains equal number of lowercase and uppercase letters. 
Example 1:
Input:
S = "gEEk"
Output: 3
Explanation: There are 3 substrings of
the given string which satisfy the
condition. They are "gE", "gEEk" and "Ek".
Example 2:
Input:
S = "WomensDAY"
Output: 4
Explanation: There are 4 substrings of 
the given string which satisfy the
condition. They are "Wo", "ensDAY", 
"nsDA" and "sD"
Your Task:
The task is to complete the function countSubstring() which takes the string S as input parameter and returns the number of substrings which contains equal number of uppercase and lowercase letters.
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an n × m grid. Each grid cell is filled with a unique integer from 1 to nm so that each integer appears exactly once.

In one operation, you can choose an arbitrary cycle of the grid and move all integers along that cycle one space over. Here, a cycle is any sequence that satisfies the following conditions:

  * There are at least four squares. 
  * Each square appears at most once. 
  * Every pair of adjacent squares, and also the first and last squares, share an edge. 



For example, if we had the following grid:

<image>

We can choose an arbitrary cycle like this one:

<image>

To get the following grid:

<image>

In this particular case, the chosen cycle can be represented as the sequence [1, 2, 3, 6, 5, 8, 7, 4], the numbers are in the direction that we want to rotate them in.

Find any sequence of operations to sort the grid so that the array created by concatenating the rows from the highest to the lowest is sorted (look at the first picture above).

Note you do not need to minimize number of operations or sum of cycle lengths. The only constraint is that the sum of all cycles lengths must not be greater than 10^5. We can show that an answer always exists under the given constraints. Output any valid sequence of moves that will sort the grid.

Input

The first line contains two integers n and m (3 ≤ n,m ≤ 20) — the dimensions of the grid.

Each of the next n lines contains m integers x_{i,1}, x_{i,2}, …, x_{i, m} (1 ≤ x_{i,j} ≤ nm), denoting the values of the block in row i and column j. 

It is guaranteed that all x_{i,j} are distinct.

Output

First, print a single integer k, the number of operations (k ≥ 0).

On each of the next k lines, print a cycle as follows:

$$$s\ y_1\ y_2\ …\ y_s$$$

Here, s is the number of blocks to move (s ≥ 4). Here we have block y_1 moving to where block y_2 is, block y_2 moving to where block y_3 is, and so on with block y_s moving to where block y_1 is.

The sum of s over all operations must be at most 10^5.

Examples

Input

3 3
4 1 2
7 6 3
8 5 9


Output

1
8 1 4 7 8 5 6 3 2

Input

3 5
1 2 3 5 10
11 6 4 14 9
12 7 8 13 15


Output

3
4 4 14 13 8
4 5 10 9 4
4 12 7 6 11

Note

The first sample is the case in the statement. Here, we can use the cycle in reverse order to sort the grid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem, a $n \times m$ rectangular matrix $a$ is called increasing if, for each row of $i$, when go from left to right, the values strictly increase (that is, $a_{i,1}<a_{i,2}<\dots<a_{i,m}$) and for each column $j$, when go from top to bottom, the values strictly increase (that is, $a_{1,j}<a_{2,j}<\dots<a_{n,j}$).

In a given matrix of non-negative integers, it is necessary to replace each value of $0$ with some positive integer so that the resulting matrix is increasing and the sum of its elements is maximum, or find that it is impossible.

It is guaranteed that in a given value matrix all values of $0$ are contained only in internal cells (that is, not in the first or last row and not in the first or last column).


-----Input-----

The first line contains integers $n$ and $m$ ($3 \le n, m \le 500$) — the number of rows and columns in the given matrix $a$.

The following lines contain $m$ each of non-negative integers — the values in the corresponding row of the given matrix: $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($0 \le a_{i,j} \le 8000$).

It is guaranteed that for all $a_{i,j}=0$, $1 < i < n$ and $1 < j < m$ are true.


-----Output-----

If it is possible to replace all zeros with positive numbers so that the matrix is increasing, print the maximum possible sum of matrix elements. Otherwise, print -1.


-----Examples-----
Input
4 5
1 3 5 6 7
3 0 7 0 9
5 0 0 0 10
8 9 10 11 12

Output
144

Input
3 3
1 2 3
2 0 4
4 5 6

Output
30

Input
3 3
1 2 3
3 0 4
4 5 6

Output
-1

Input
3 3
1 2 3
2 3 4
3 4 2

Output
-1



-----Note-----

In the first example, the resulting matrix is as follows: 

1 3 5 6 7

3 6 7 8 9

5 7 8 9 10

8 9 10 11 12



In the second example, the value $3$ must be put in the middle cell.

In the third example, the desired resultant matrix does not exist.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.