vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
New Year is coming! Vasya has prepared a New Year's verse and wants to recite it in front of Santa Claus.

Vasya's verse contains $n$ parts. It takes $a_i$ seconds to recite the $i$-th part. Vasya can't change the order of parts in the verse: firstly he recites the part which takes $a_1$ seconds, secondly — the part which takes $a_2$ seconds, and so on. After reciting the verse, Vasya will get the number of presents equal to the number of parts he fully recited.

Vasya can skip at most one part of the verse while reciting it (if he skips more than one part, then Santa will definitely notice it).

Santa will listen to Vasya's verse for no more than $s$ seconds. For example, if $s = 10$, $a = [100, 9, 1, 1]$, and Vasya skips the first part of verse, then he gets two presents.

Note that it is possible to recite the whole verse (if there is enough time). 

Determine which part Vasya needs to skip to obtain the maximum possible number of gifts. If Vasya shouldn't skip anything, print 0. If there are multiple answers, print any of them.

You have to process $t$ test cases.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains two integers $n$ and $s$ ($1 \le n \le 10^5, 1 \le s \le 10^9$) — the number of parts in the verse and the maximum number of seconds Santa will listen to Vasya, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the time it takes to recite each part of the verse.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print one integer — the number of the part that Vasya needs to skip to obtain the maximum number of gifts. If Vasya shouldn't skip any parts, print 0.


-----Example-----
Input
3
7 11
2 9 1 3 18 1 4
4 35
11 9 10 7
1 8
5

Output
2
1
0



-----Note-----

In the first test case if Vasya skips the second part then he gets three gifts.

In the second test case no matter what part of the verse Vasya skips.

In the third test case Vasya can recite the whole verse.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers cost[] of length N, where cost[i] is the cost of the i^{th} step on a staircase. Once the cost is paid, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
Example 1:
Input:
N = 3
cost[] = {10, 15, 20}
Output:
15
Explanation:
Cheapest option is to start at cost[1],
pay that cost, and go to the top.
 
Example 2:
Input:
N = 10
arr[] = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}
Output:
6
Explanation:
Cheapest option is to start on cost[0], 
and only step on 1s, skipping cost[3].
Your Task:
The task is to complete the function minCostClimbingStairs() which takes an array cost[] as input and returns the minimum cost to reach the top.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
2 ≤ N ≤ 10^{3}
0 ≤ cost[i] ≤ 999

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has an array a consisting of positive integer numbers. Vasya wants to divide this array into two non-empty consecutive parts (the prefix and the suffix) so that the sum of all elements in the first part equals to the sum of elements in the second part. It is not always possible, so Vasya will move some element before dividing the array (Vasya will erase some element and insert it into an arbitrary position).

Inserting an element in the same position he was erased from is also considered moving.

Can Vasya divide the array after choosing the right element to move and its new position?


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 100000) — the size of the array.

The second line contains n integers a_1, a_2... a_{n} (1 ≤ a_{i} ≤ 10^9) — the elements of the array.


-----Output-----

Print YES if Vasya can divide the array after moving one element. Otherwise print NO.


-----Examples-----
Input
3
1 3 2

Output
YES

Input
5
1 2 3 4 5

Output
NO

Input
5
2 2 3 4 5

Output
YES



-----Note-----

In the first example Vasya can move the second element to the end of the array.

In the second example no move can make the division possible.

In the third example Vasya can move the fourth element by one position to the left.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Siruseri amusement park has a new attraction. It consists of a rectangular array of discs. Each disc is divided into four equal sectors and the four sectors are coloured with the colours Red, Blue, Green and Yellow (in some order). The ordering may be different in different discs. Here is a possible arrangment of the discs:

You start at the top left disc. Your task is to walk down to the bottom right disc. In each step, you can rotate the current disc by $90$ degrees in the clockwise direction or move to a neighbouring disc. However, you can move to a neighbouring disc only if adjacent sectors of these two discs have the same colour. For example, in the figure above, you can move from the disc at position ($1$, $1$) to either of its neighbours. However, from the disc at position ($1$, $2$) you can only move to the disc at position ($1$, $1$). If you wish to move from ($1$, $2$) to ($1$, $3$) then you would have to rotate this disc three times so that the colour (red) on the adjacent sectors are the same.
For each rotate move, a penalty point is added to the score. The aim is to reach the bottom right with as few penalty points as possible. For example, in the arrangement described in the above figure, the best possible score is $2$, corresponding to the following path: Move from ($1$, $1$) to ($2$, $1$). Move from ($2$, $1$) to ($2$, $2$). Rotate. Rotate. Move from ($2$, $2$) to ($2$, $3$). Move from ($2$, $3$) to ($1$, $3$). Move from ($1$, $3$) to ($1$, $4$). Finally, move from ($1$, $4$) to ($2$, $4$).
Your task is to determine the minimum number of penalty points required to go from the top left disc to the bottom right disc for the given arrangement of discs.

-----Input:-----
The first line contains two integers $M$ and $N$. $M$ is the number of rows and $N$ is the number of columns in the given arrangment. This is followed by $M \times N$ lines of input. Lines $2$ to $N+1$, describe the colours on the discs on the first row, Lines $N+2$ to $2 \cdot N+1$ describe the colours on discs in the second row and so on. Each of these lines contain a permutation of the set {R, G, B, Y} giving the colours in the top, right, bottom and left sectors in that order.

-----Output:-----
A single integer on a single line indicating the minimum number of penalty points required to go from the top left disc to the bottom right disc for the given arrangement of discs.

-----Constraints:-----
- In $80 \%$ of the input, $1 \leq M,N \leq 60$.
- In all the inputs $1 \leq M,N \leq 1000$.

-----Sample Input-----
2 4
G Y B R
B G R Y
G Y B R
G R B Y
B Y G R
G B R Y
B R G Y
B R G Y

-----Sample Output-----
2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a mysterious language (codenamed "Secret") available in "Custom Test" tab. Find out what this language is and write a program which outputs its name. Note that the program must be written in this language.

Input Specification:
This program has only one test, and it's empty (it doesn't give your program anything to read).

Output Specification:
Output the name of the mysterious language.

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
PolandBall is standing in a row with Many Other Balls. More precisely, there are exactly n Balls. Balls are proud of their home land — and they want to prove that it's strong.

The Balls decided to start with selecting exactly m groups of Balls, each consisting either of single Ball or two neighboring Balls. Each Ball can join no more than one group.

The Balls really want to impress their Enemies. They kindly asked you to calculate number of such divisions for all m where 1 ≤ m ≤ k. Output all these values modulo 998244353, the Enemies will be impressed anyway.

Input

There are exactly two numbers n and k (1 ≤ n ≤ 109, 1 ≤ k < 215), denoting the number of Balls and the maximim number of groups, respectively.

Output

You should output a sequence of k values. The i-th of them should represent the sought number of divisions into exactly i groups, according to PolandBall's rules.

Examples

Input

3 3


Output

5 5 1 

Input

1 1


Output

1 

Input

5 10


Output

9 25 25 9 1 0 0 0 0 0 

Note

In the first sample case we can divide Balls into groups as follows: 

{1}, {2}, {3}, {12}, {23}.

{12}{3}, {1}{23}, {1}{2}, {1}{3}, {2}{3}.

{1}{2}{3}.

Therefore, output is: 5 5 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a matrix(2D array) M of size N*N consisting of 0s and 1s only. The task is to find the column with maximum number of 0s.
Example:
Input:
N = 3
M[][] = {{1, 1, 0},
         {1, 1, 0},
         {1, 1, 0}}
Output:2
Explanation:
2nd column (0-based indexing) 
is having 3 zeros which is 
maximum among all columns.
 
Your Task:
Your task is to complete the function columnWithMaxZero() which should return the column number with the maximum number of zeros. If more than one column exists, print the one which comes first.
Constraints:
1 <= N <= 10^{2}
0 <= A[i][j] <= 1

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

Ka ka ka cypher is a cypher used by small children in some country. When a girl wants to pass something to the other girls and there are some boys nearby, she can use Ka cypher. So only the other girls are able to understand her. 
She speaks using KA, ie.: 
`ka thi ka s ka bo ka y ka i ka s ka u ka gly` what simply means `this boy is ugly`. 


# Task 

Write a function `KaCokadekaMe` (`ka_co_ka_de_ka_me` in Python) that accepts a string word and returns encoded message using ka cypher. 
Our rules:
- The encoded word should start from `ka`.
- The `ka` goes after vowel (a,e,i,o,u)
- When there is multiple vowels together, the `ka` goes only after the last `vowel`
- When the word is finished by a vowel, do not add the `ka` after

# Input/Output

The `word` string consists of only lowercase and uppercase characters. There is only 1 word to convert - no white spaces.

# Example

```
KaCokadekaMe("a");  //=> "kaa"
KaCokadekaMe("ka");  //=> "kaka"
KaCokadekaMe("aa"); //=> "kaaa"  
KaCokadekaMe("Abbaa"); //=> kaAkabbaa
KaCokadekaMe("maintenance"); //=> kamaikantekanakance
KaCokadekaMe("Woodie"); //=> kaWookadie
KacokadekaMe("Incomprehensibilities"); //=> kaIkancokamprekahekansikabikalikatiekas
```

# Remark

Ka cypher's country residents, please don't hate me for simplifying the way how we divide the words into "syllables" in the Kata. I don't want to make it too hard for other nations ;-P

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yash likes playing with numbers. He has a challenge for you. Yash gives
you a number that he made by multiplying two numbers. He claims that the
possible sum of the two numbers he multiplied is as minimum as possible. He
challenges you to find that minimum sum.

Formally, for a given value of N, you are required to find the minimum sum of two distinct numbers x and y such that x, y > 0 and xy = N.  

-----Input:-----
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

Each testcase contains single integer N.

-----Output:-----
For each testcase, output minimum x + y such that x*y = N and x,y >0.

-----Constraints :-----
$1 \leq T \leq 100$
$1 < N \leq 10^{12}$

-----Sample Input:-----
1

852140

-----Sample Output:-----
1929

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of n positive integers a_1, a_2, ..., a_n. You can perform the following operation any number of times: select several distinct indices i_1, i_2, ..., i_k (1 ≤ i_j ≤ n) and move the number standing at the position i_1 to the position i_2, the number at the position i_2 to the position i_3, ..., the number at the position i_k to the position i_1. In other words, the operation cyclically shifts elements: i_1 → i_2 → … i_k → i_1.

For example, if you have n=4, an array a_1=10, a_2=20, a_3=30, a_4=40, and you choose three indices i_1=2, i_2=1, i_3=4, then the resulting array would become a_1=20, a_2=40, a_3=30, a_4=10.

Your goal is to make the array sorted in non-decreasing order with the minimum number of operations. The additional constraint is that the sum of cycle lengths over all operations should be less than or equal to a number s. If it's impossible to sort the array while satisfying that constraint, your solution should report that as well.

Input

The first line of the input contains two integers n and s (1 ≤ n ≤ 200 000, 0 ≤ s ≤ 200 000)—the number of elements in the array and the upper bound on the sum of cycle lengths.

The next line contains n integers a_1, a_2, ..., a_n—elements of the array (1 ≤ a_i ≤ 10^9).

Output

If it's impossible to sort the array using cycles of total length not exceeding s, print a single number "-1" (quotes for clarity).

Otherwise, print a single number q— the minimum number of operations required to sort the array.

On the next 2 ⋅ q lines print descriptions of operations in the order they are applied to the array. The description of i-th operation begins with a single line containing one integer k (1 ≤ k ≤ n)—the length of the cycle (that is, the number of selected indices). The next line should contain k distinct integers i_1, i_2, ..., i_k (1 ≤ i_j ≤ n)—the indices of the cycle.

The sum of lengths of these cycles should be less than or equal to s, and the array should be sorted after applying these q operations.

If there are several possible answers with the optimal q, print any of them.

Examples

Input

5 5
3 2 3 1 1


Output

1
5
1 4 2 3 5 


Input

4 3
2 1 4 3


Output

-1

Input

2 0
2 2


Output

0

Note

In the first example, it's also possible to sort the array with two operations of total length 5: first apply the cycle 1 → 4 → 1 (of length 2), then apply the cycle 2 → 3 → 5 → 2 (of length 3). However, it would be wrong answer as you're asked to use the minimal possible number of operations, which is 1 in that case.

In the second example, it's possible to the sort the array with two cycles of total length 4 (1 → 2 → 1 and 3 → 4 → 3). However, it's impossible to achieve the same using shorter cycles, which is required by s=3.

In the third example, the array is already sorted, so no operations are needed. Total length of empty set of cycles is considered to be zero.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given N integers, the task is to insert those elements in the queue. Also, given M integers, the task is to find the frequency of each number in the Queue.
Note:
insert() will be called N times by main().
findFrequency() will be called M times by main();
Where k is each element passing through respective function calls.
Example 1:
Input:
N = 8
1 2 3 4 5 2 3 1
M = 5
1 3 2 9 10
Output:
2
2
2
-1
-1
Explanation:
After inserting 1, 2, 3, 4, 5, 2, 3 and 1 into the queue, frequency of 1 is 2, 3 is 2 and 2 is 2. Since 9 and 10 are not there in the queue we output -1 for them.
Example 2:
Input:
N = 6
1 2 1 1 1 4
M = 4
1 5 4 3
Output:
4
-1
1
-1
Explanation:
After inserting 1, 2, 1, 1, 1 and 4 into the queue, frequency of 1 is 4 and that of 4 is 1. Since 5 and 3 are not there in the queue we output -1 for them.
Your Task:
Your task is to complete the functions insert() and findFrequency() which inserts the element into the queue and find the count of occurences of element in the queue respectively.
Expected Time Complexity: O(N*M)
Expected Space Complexity: O(N)
Constraints:
1 <= N <= 10^{3}
1 <= M <= 10^{3}
1 <= Elements of Queue <= 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan is a novice painter. He has n dyes of different colors. He also knows exactly m pairs of colors which harmonize with each other.

Ivan also enjoy playing chess. He has 5000 rooks. He wants to take k rooks, paint each of them in one of n colors and then place this k rooks on a chessboard of size 10^{9} × 10^{9}.

Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set. Assume that rooks can jump over other rooks, in other words a rook can go to any cell which shares vertical and to any cell which shares horizontal.

Ivan wants his arrangement of rooks to have following properties:

  * For any color there is a rook of this color on a board;
  * For any color the set of rooks of this color is connected;
  * For any two different colors a b union of set of rooks of color a and set of rooks of color b is connected if and only if this two colors harmonize with each other.



Please help Ivan find such an arrangement.

Input

The first line of input contains 2 integers n, m (1 ≤ n ≤ 100, 0 ≤ m ≤ min(1000,    (n(n-1))/(2))) — number of colors and number of pairs of colors which harmonize with each other.

In next m lines pairs of colors which harmonize with each other are listed. Colors are numbered from 1 to n. It is guaranteed that no pair occurs twice in this list.

Output

Print n blocks, i-th of them describes rooks of i-th color.

In the first line of block print one number a_{i} (1 ≤ a_{i} ≤ 5000) — number of rooks of color i. In each of next a_{i} lines print two integers x and y (1 ≤ x,    y ≤ 10^{9}) — coordinates of the next rook.

All rooks must be on different cells.

Total number of rooks must not exceed 5000.

It is guaranteed that the solution exists.

Examples

Input

3 2
1 2
2 3


Output

2
3 4
1 4
4
1 2
2 2
2 4
5 4
1
5 1


Input

3 3
1 2
2 3
3 1


Output

1
1 1
1
1 2
1
1 3


Input

3 1
1 3


Output

1
1 1
1
2 2
1
3 1

Note

Rooks arrangements for all three examples (red is color 1, green is color 2 and blue is color 3).

<image>

<image>

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The stardate is 1983, and Princess Heidi is getting better at detecting the Death Stars. This time, two Rebel spies have yet again given Heidi two maps with the possible locations of the Death Star. Since she got rid of all double agents last time, she knows that both maps are correct, and indeed show the map of the solar system that contains the Death Star. However, this time the Empire has hidden the Death Star very well, and Heidi needs to find a place that appears on both maps in order to detect the Death Star.

The first map is an N × M grid, each cell of which shows some type of cosmic object that is present in the corresponding quadrant of space. The second map is an M × N grid. Heidi needs to align those two maps in such a way that they overlap over some M × M section in which all cosmic objects are identical. Help Heidi by identifying where such an M × M section lies within both maps.


-----Input-----

The first line of the input contains two space-separated integers N and M (1 ≤ N ≤ 2000, 1 ≤ M ≤ 200, M ≤ N). The next N lines each contain M lower-case Latin characters (a-z), denoting the first map. Different characters correspond to different cosmic object types. The next M lines each contain N characters, describing the second map in the same format. 


-----Output-----

The only line of the output should contain two space-separated integers i and j, denoting that the section of size M × M in the first map that starts at the i-th row is equal to the section of the second map that starts at the j-th column. Rows and columns are numbered starting from 1.

If there are several possible ways to align the maps, Heidi will be satisfied with any of those. It is guaranteed that a solution exists.


-----Example-----
Input
10 5
somer
andom
noise
mayth
eforc
ebewi
thyou
hctwo
again
noise
somermayth
andomeforc
noiseebewi
againthyou
noisehctwo

Output
4 6



-----Note-----

The 5-by-5 grid for the first test case looks like this: 

mayth

eforc

ebewi

thyou

hctwo

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese and Russian as well. 

Mike and his friend Tom are playing a very interesting game right now. Here is the description of the game:

		Initially, there is a positive integer N written on the desk, which is strictly greater than 1;
		Mike makes the first move, then players make moves alternatively;
		On each move the current player can either decrease the number on the desk by 1, or divide it by one of it's divisors except itself and 1; It's forbidden to decrease the number if it's equal to 1;
		If the current player can't make a move, then he loses. In other words, if there is "1" written on the desk right before his move, then he loses.
	
You are given a number N. You need to determine the winner of the game, if N is the number written of the desk initially. You may assume, that both players play optimally.

------ Input ------ 

There are multiple test cases in the input. The first line of the input contains one integer T, denoting the number of test cases in the input.

The next T lines contain one integer each, denoting the initial number of the game.
All the test cases are independent and must be considered separately!
 
------ Output ------ 

Your output should contain exactly T lines, each contains the name of the winner(Mike or Tom) of the corresponding game. You should output the verdicts of the games in the order they appear in the input.
 
------ Constraints ------ 

1 ≤ T ≤ 10 000;
2 ≤ N ≤ 10^{8}, for each test case appeared in the input.

------ Example ------ 

Input:
4 
5 
3 
2 
4

Output:
Tom
Tom
Mike
Mike

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has decided to give a string to his mother.

The value of a string T is the length of the longest common subsequence of T and T', where T' is the string obtained by reversing T. That is, the value is the longest length of the following two strings that are equal: a subsequence of T (possibly non-contiguous), and a subsequence of T' (possibly non-contiguous).

Takahashi has a string S. He wants to give her mother a string of the highest possible value, so he would like to change at most K characters in S to any other characters in order to obtain a string of the highest possible value. Find the highest possible value achievable.

Constraints

* 1 \leq |S| \leq 300
* 0 \leq K \leq |S|
* S consists of lowercase English letters.
* K is an integer.

Input

Input is given from Standard Input in the following format:


S
K


Output

Print the highest possible value achievable.

Examples

Input

abcabcabc
1


Output

7


Input

atcodergrandcontest
3


Output

15

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