vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Kriti and Me were getting bored, so we finally came up with an idea of a cool game.
The game is described as follows.
1. Initially, we have a stack of n disks.
2. A player in his/her turn can remove a certain number of disks from the stack.
3. The player who can't remove the disks in his/her turn loses.
4. In the beginning, we will be provided with 2 sets, S and K, (of size Ssize and Ksize), 1 for me and other for Kriti.
The number of disks any player can remove from the stack in his/her turn must be an element of his/her set.

Provided that the 2 players play alternatively and optimally, help me guess if I can win the game or not.

Input Format:

Input begins with 2 positive integers Ksize and Ssize denoting the size of Kriti's and My set respectively.
The next line contains Ksize positive integers, denoting the elements of Kriti's set.
Similarly, the following line contains Ssize positive integers denoting, the elements of my set.

Next line contains a positive integer Q, the number of queries.
Each of the next Q lines contain an positive integer n and a character c denoting who will play first.
'S' means I will start the game. 'K' means Kriti will play first.

Output Format:
For each n, print "YES" if I can win the game else print "NO" in a new line.(All alphabets in capital, quotes only for clarification).

Scoring Criteria:

20 Points: 1 ≤ K, S ≤ 3,  1 ≤ S[i], K[i] ≤ 5     and 1 ≤ Q ≤5 and n ≤ 10
50 Points: 1 ≤ K, S ≤ 50,  1 ≤ S[i], K[i] ≤ 100   and 1 ≤ Q ≤100 and n ≤ 1000 
130 Points: 1 ≤ K, S ≤ 100, 1 ≤ S[i], K[i] ≤ 1000  and 1 ≤ Q ≤ 10000 and n ≤ 100000

SAMPLE INPUT
3 3
2 4 5
1 5 7
4
2 S
3 S
3 K
5 K

SAMPLE OUTPUT
YES
NO
YES
NO

Explanation

In first test case, I can remove 1 disk, and Kriti is left with no choice.
In second test case, I have no choice except to remove 1 disk. Kriti will remove 2 disk afterwards and win.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The marmots have prepared a very easy problem for this year's HC^2 – this one. It involves numbers n, k and a sequence of n positive integers a_1, a_2, ..., a_{n}. They also came up with a beautiful and riveting story for the problem statement. It explains what the input means, what the program should output, and it also reads like a good criminal.

However I, Heidi, will have none of that. As my joke for today, I am removing the story from the statement and replacing it with these two unhelpful paragraphs. Now solve the problem, fools!


-----Input-----

The first line of the input contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 2200). The second line contains n space-separated integers a_1, ..., a_{n} (1 ≤ a_{i} ≤ 10^4).


-----Output-----

Output one number.


-----Examples-----
Input
8 5
1 1 1 1 1 1 1 1

Output
5
Input
10 3
16 8 2 4 512 256 32 128 64 1

Output
7
Input
5 1
20 10 50 30 46

Output
10
Input
6 6
6 6 6 6 6 6

Output
36
Input
1 1
100

Output
100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Raju is very fond of strings.Once he was playing a  game with his friend.His friend gave him a string to decipher.As Raju is not very good at programming, he ask for your help.

So he provide you a string and your task is  to decipher it.

Note : The pattern is hidden in the Sample Test Cases.

INPUT
A single integer T denoting number of cases.
T lines follow a string S,consisting of only lowercase latin characters ( 'a' - 'z').

OUTPUT
Print the output in a new line  for every test cases.

Constraints

1 ≤ T ≤ 10000
1 ≤ |s| ≤ 100

*Problem Setter : *Shikhar Singh

SAMPLE INPUT
10
tdaejjptlzec
qvcopt
aacpax
cqwmpzr
gdlbnj
qzxjgjj
azzyyx
cnbb
wxqfsta
wgwmdt

SAMPLE OUTPUT
technovation
qwerty
abesec
cryptex
genero
qazmkop
aabbcc
code
wysiwyg
whyphy

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have array of $n$ numbers $a_{1}, a_{2}, \ldots, a_{n}$. 

Rearrange these numbers to satisfy $|a_{1} - a_{2}| \le |a_{2} - a_{3}| \le \ldots \le |a_{n-1} - a_{n}|$, where $|x|$ denotes absolute value of $x$. It's always possible to find such rearrangement.

Note that all numbers in $a$ are not necessarily different. In other words, some numbers of $a$ may be same.

You have to answer independent $t$ test cases.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases.

The first line of each test case contains single integer $n$ ($3 \le n \le 10^{5}$) — the length of array $a$. It is guaranteed that the sum of values of $n$ over all test cases in the input does not exceed $10^{5}$.

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($-10^{9} \le a_{i} \le 10^{9}$).


-----Output-----

For each test case, print the rearranged version of array $a$ which satisfies given condition. If there are multiple valid rearrangements, print any of them.


-----Example-----
Input
2
6
5 -2 4 8 6 5
4
8 1 4 2

Output
5 5 4 6 8 -2
1 2 4 8



-----Note-----

In the first test case, after given rearrangement, $|a_{1} - a_{2}| = 0 \le |a_{2} - a_{3}| = 1 \le |a_{3} - a_{4}| = 2 \le |a_{4} - a_{5}| = 2 \le |a_{5} - a_{6}| = 10$. There are other possible answers like "5 4 5 6 -2 8".

In the second test case, after given rearrangement, $|a_{1} - a_{2}| = 1 \le |a_{2} - a_{3}| = 2 \le |a_{3} - a_{4}| = 4$. There are other possible answers like "2 4 8 1".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two friends David and Rojer were preparing for their weekly class-test.
The are preparing for the math test, but because of continuously adding big integers and solving equations they got exhausted. They decided to take break and play a game. They play a game which will help them in both(for having fun and will also help to prepare for math test).
There are N words and they have to find RESULT with the help of these words (just like they have N integers and they have to find integer RESULT=sum of N integers) . Since they are playing this game for the first time! They are not too good in this. Help them in finding weather their RESULT is correct or not.   
NOTE:- Total number of unique characters in N words are not greater than 10. All input words and RESULT are in UPPER-CASE only!
Refer Here for how to add numbers : https://en.wikipedia.org/wiki/Verbal_arithmetic

-----Input:-----
- First line consist of an integer N (total number of words).
- Next N line contains words with which they have to find RESULT.
- Last line consist of the RESULT they found.

-----Output:-----
If RESULT is correct print true else print false.

-----Sample Input:-----
3

THIS

IS

TOO

FUNNY  

-----Sample Output:-----
true

-----Constraints-----
- $2 \leq N \leq 10$
- $1 \leq Length of The word \leq 10$
- $1 \leq Length of The Result \leq 11$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dreamoon wants to climb up a stair of n steps. He can climb 1 or 2 steps at each move. Dreamoon wants the number of moves to be a multiple of an integer m. 

What is the minimal number of moves making him climb to the top of the stairs that satisfies his condition?


-----Input-----

The single line contains two space separated integers n, m (0 < n ≤ 10000, 1 < m ≤ 10).


-----Output-----

Print a single integer — the minimal number of moves being a multiple of m. If there is no way he can climb satisfying condition print  - 1 instead.


-----Examples-----
Input
10 2

Output
6

Input
3 5

Output
-1



-----Note-----

For the first sample, Dreamoon could climb in 6 moves with following sequence of steps: {2, 2, 2, 2, 1, 1}.

For the second sample, there are only three valid sequence of steps {2, 1}, {1, 2}, {1, 1, 1} with 2, 2, and 3 steps respectively. All these numbers are not multiples of 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Fedor and New Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
After you had helped George and Alex to move in the dorm, they went to help their friend Fedor play a new computer game «Call of Soldiers 3».

The game has (*m*<=+<=1) players and *n* types of soldiers in total. Players «Call of Soldiers 3» are numbered form 1 to (*m*<=+<=1). Types of soldiers are numbered from 0 to *n*<=-<=1. Each player has an army. Army of the *i*-th player can be described by non-negative integer *x**i*. Consider binary representation of *x**i*: if the *j*-th bit of number *x**i* equal to one, then the army of the *i*-th player has soldiers of the *j*-th type. 

Fedor is the (*m*<=+<=1)-th player of the game. He assume that two players can become friends if their armies differ in at most *k* types of soldiers (in other words, binary representations of the corresponding numbers differ in at most *k* bits). Help Fedor and count how many players can become his friends.

Input Specification:
The first line contains three integers *n*, *m*, *k* (1<=≤<=*k*<=≤<=*n*<=≤<=20; 1<=≤<=*m*<=≤<=1000).

The *i*-th of the next (*m*<=+<=1) lines contains a single integer *x**i* (1<=≤<=*x**i*<=≤<=2*n*<=-<=1), that describes the *i*-th player's army. We remind you that Fedor is the (*m*<=+<=1)-th player.

Output Specification:
Print a single integer — the number of Fedor's potential friends.

Demo Input:
['7 3 1\n8\n5\n111\n17\n', '3 3 3\n1\n2\n3\n4\n']

Demo Output:
['0\n', '3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today RK has to transport his N items of different weights(in calories) to a near city but before that he wants to make sure that the weights of all items are balanced. In order to check this he puts all items on the weight scale and found that weights are not balanced actually. So to deal with it RK designed his own procedure.
RK chooses two different weights say A and B such that weight(A) > weight(B) and reduce the weight of A by weight(B) calories. He repeats this procedure as many times as he needed. The ultimate goal of RK is to balance all weights by minimizing the sum of all weights using his own procedure. RK has asked for your help as their are large number of items. So make a quick move and help RK .

INPUT :

The first line contains the number of test cases T(1 ≤ T ≤ 10). First line of each test case contains a positive integer N(2 ≤ N ≤ 10^6)-Number of items .Second line contains N space separated positive integers in the interval [1,10^9] representing weight of each item in calories.

OUTPUT :

For each test case output the minimum sum of all balanced weights.

SAMPLE INPUT
2
3
3 6 9
2
2 2

SAMPLE OUTPUT
9
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's introduce a number system which is based on a roman digits. There are digits I, V, X, L which correspond to the numbers $1$, $5$, $10$ and $50$ respectively. The use of other roman digits is not allowed.

Numbers in this system are written as a sequence of one or more digits. We define the value of the sequence simply as the sum of digits in it.

For example, the number XXXV evaluates to $35$ and the number IXI — to $12$.

Pay attention to the difference to the traditional roman system — in our system any sequence of digits is valid, moreover the order of digits doesn't matter, for example IX means $11$, not $9$.

One can notice that this system is ambiguous, and some numbers can be written in many different ways. Your goal is to determine how many distinct integers can be represented by exactly $n$ roman digits I, V, X, L.


-----Input-----

The only line of the input file contains a single integer $n$ ($1 \le n \le 10^9$) — the number of roman digits to use.


-----Output-----

Output a single integer — the number of distinct integers which can be represented using $n$ roman digits exactly.


-----Examples-----
Input
1

Output
4

Input
2

Output
10

Input
10

Output
244



-----Note-----

In the first sample there are exactly $4$ integers which can be represented — I, V, X and L.

In the second sample it is possible to represent integers $2$ (II), $6$ (VI), $10$ (VV), $11$ (XI), $15$ (XV), $20$ (XX), $51$ (IL), $55$ (VL), $60$ (XL) and $100$ (LL).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given string s of length n consisting of 0-s and 1-s. You build an infinite string t as a concatenation of an infinite number of strings s, or t = ssss ... For example, if s = 10010, then t = 100101001010010...

Calculate the number of prefixes of t with balance equal to x. The balance of some string q is equal to cnt_{0, q} - cnt_{1, q}, where cnt_{0, q} is the number of occurrences of 0 in q, and cnt_{1, q} is the number of occurrences of 1 in q. The number of such prefixes can be infinite; if it is so, you must say that.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".

Input

The first line contains the single integer T (1 ≤ T ≤ 100) — the number of test cases.

Next 2T lines contain descriptions of test cases — two lines per test case. The first line contains two integers n and x (1 ≤ n ≤ 10^5, -10^9 ≤ x ≤ 10^9) — the length of string s and the desired balance, respectively.

The second line contains the binary string s (|s| = n, s_i ∈ \{0, 1\}).

It's guaranteed that the total sum of n doesn't exceed 10^5.

Output

Print T integers — one per test case. For each test case print the number of prefixes or -1 if there is an infinite number of such prefixes.

Example

Input


4
6 10
010010
5 3
10101
1 0
0
2 0
01


Output


3
0
1
-1

Note

In the first test case, there are 3 good prefixes of t: with length 28, 30 and 32.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.
 
Example 1:
Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:
Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:
Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

 
Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vipul has N empty boxes, numbered from 1 to N, with infinite capacity. He performs M operations. Each operation is described by 3 integers, a, b, and k. Here, a and b are indices of the boxes, and k is the number of marbles to be added inside each box whose index lies between a and b (both inclusive). Can you tell the average number of marbles after M operations?

Input Format

The first line contains two integers, N and M, separated by a single space. 
M lines follow; each of them contains three integers, a, b, and k, separated by spaces.

Output Format

A single line containing the average number of marbles across N boxes, rounded down to the nearest integer.

Constraints 

3≤N≤10^7 
1≤M≤10^5 
1≤a≤b≤N 
0≤k≤10^6

Note: Rounded down means finding the greatest integer which is less than or equal to the given number. E.g. 13.65 and 13.23 are rounded down to 13, while 12.98 is rounded down to 12.

SAMPLE INPUT
5 3
1 2 100
2 5 100
3 4 100

SAMPLE OUTPUT
160

Explanation

Initially each of the jars contains 0 candies

0 0 0 0

First operation:

100 100 0 0 0  

Second operation:

100 200 100 100 100  

Third operation:

100 200 200 200 100  

Total = 800, 
Average = 800/5 = 160

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are interested in collecting the sets of six prime numbers, that having a starting prime p, the following values are also primes forming the sextuplet ```[p, p + 4, p + 6, p + 10, p + 12, p + 16]```

The first sextuplet that we find is ```[7, 11, 13, 17, 19, 23]```

The second one is ```[97, 101, 103, 107, 109, 113]```

Given a number ```sum_limit```, you should give the first sextuplet which sum (of its six primes) surpasses the sum_limit value.

```python
find_primes_sextuplet(70) == [7, 11, 13, 17, 19, 23]

find_primes_sextuplet(600) == [97, 101, 103, 107, 109, 113]
```
Features of the tests:
```
Number Of Tests = 18
10000 < sum_limit < 29700000
```
If you have solved this kata perhaps you will find easy to solve this one:
https://www.codewars.com/kata/primes-with-two-even-and-double-even-jumps/
Enjoy it!!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n stones arranged on an axis. Initially the i-th stone is located at the coordinate s_i. There may be more than one stone in a single place.

You can perform zero or more operations of the following type: 

  * take two stones with indices i and j so that s_i ≤ s_j, choose an integer d (0 ≤ 2 ⋅ d ≤ s_j - s_i), and replace the coordinate s_i with (s_i + d) and replace coordinate s_j with (s_j - d). In other words, draw stones closer to each other. 



You want to move the stones so that they are located at positions t_1, t_2, …, t_n. The order of the stones is not important — you just want for the multiset of the stones resulting positions to be the same as the multiset of t_1, t_2, …, t_n.

Detect whether it is possible to move the stones this way, and if yes, construct a way to do so. You don't need to minimize the number of moves.

Input

The first line contains a single integer n (1 ≤ n ≤ 3 ⋅ 10^5) – the number of stones.

The second line contains integers s_1, s_2, …, s_n (1 ≤ s_i ≤ 10^9) — the initial positions of the stones.

The second line contains integers t_1, t_2, …, t_n (1 ≤ t_i ≤ 10^9) — the target positions of the stones.

Output

If it is impossible to move the stones this way, print "NO".

Otherwise, on the first line print "YES", on the second line print the number of operations m (0 ≤ m ≤ 5 ⋅ n) required. You don't have to minimize the number of operations.

Then print m lines, each containing integers i, j, d (1 ≤ i, j ≤ n, s_i ≤ s_j, 0 ≤ 2 ⋅ d ≤ s_j - s_i), defining the operations.

One can show that if an answer exists, there is an answer requiring no more than 5 ⋅ n operations.

Examples

Input


5
2 2 7 4 9
5 4 5 5 5


Output


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

Input


3
1 5 10
3 5 7


Output


NO

Note

Consider the first example. 

  * After the first move the locations of stones is [2, 2, 6, 5, 9]. 
  * After the second move the locations of stones is [2, 3, 5, 5, 9]. 
  * After the third move the locations of stones is [2, 5, 5, 5, 7]. 
  * After the last move the locations of stones is [4, 5, 5, 5, 5]. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer n and an integer k such that 0 ≤ k ≤ n, find any permutation A of 1, 2 \dots n such that the number of indices for which A_{i}=i is exactly k. If there exists no such permutation, print -1. If there exist multiple such permutations, print any one of them.

------ Input Format ------ 

- First line of the input contains T, the number of test cases. Then the test cases follow.
- Each test case contains a single line of input, two integers n, k.

------ Output Format ------ 

For each test case, print a permutation in a single line, if a permutation with the given constraints exists. Print -1 otherwise.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ n ≤ 10^{5}$
$0 ≤ k ≤ n$
- Sum of $n$ over all test cases doesn't exceed $2 \cdot 10^{6}$

----- Sample Input 1 ------ 
3
2 1
3 1
4 2

----- Sample Output 1 ------ 
-1
1 3 2
3 2 1 4

----- explanation 1 ------ 
Test case $1$: There are total $2$ permutations of $[1, 2]$  which are $[1, 2]$ and $[2, 1]$. There are $2$ indices in $[1, 2]$ and $0$ indices in $[2, 1]$ for which $A_{i}=i$ holds true. Thus, there doesn't exist any permutation of $[1, 2]$ with exactly $1$ index $i$ for which $A_{i}=i$ holds true.

Test case $2$: Consider the permutation $A = [1, 3, 2]$. We have $A_{1} = 1$, $A_{2} = 3$ and $A_{3} = 2$. So, this permutation has exactly $1$ index such that $A_{i}=i$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently scientists discovered new field to research. They explore how to organize TV schedule to maximize happiness of viewers. They proved that a change of happiness after viewing a TV-show depends only on this show and the previous show.

Formally, each TV-show is characterized by three values: 
ti, ai and bi , where ti is the type of the i-th TV-show, ai and bi are how happiness changes after viewing the i-th show. If the previous TV-show exists
(i.e. the current show is not the first) and the previous show type equals to the type of the current show then happiness is increased by ai. Otherwise after viewing the i-th TV-show happiness is increased by bi.

There are n TV-shows in total numbered from 1 to n. The problem is to choose some TV-shows and order them in a sequence in a way to maximize happiness after viewing all of them one after another. Actually some TV-shows do not increase happiness, if quality of a TV-show is very low it can have negative a
and/or b values. It is possible to choose empty set of TV-shows, in that case happiness will no be changed. Each show can be used at most once.

Input
The first line contains integer n (1 ≤ n ≤ 600)  the number of TV-shows. Each of the following n lines describes one show. The i-th line contains three integers: ti, ai , bi (1 ≤ ti ≤ n; |ai|, |bi| ≤ 105)  the typ eand the values of the i-th show.

Output
The output should contain two lines. Output two integer numbers c and k in the first line, where c maximal happiness change after viewing subset of shows in an appropriate order, k (0 ≤ k ≤ n)  the number of shows in the optimal subset. Output the sequence of TV-shows in the order that maximizes
happiness in the second line. Formally, output k indices f1, f2, . . . , fk (1 ≤ fj ≤ n), where f1 is the first show to be shown, f2 is the second show to be shown, and so on. If there are many optimal solutions, any is acceptable

SAMPLE INPUT
4
1 10 5
1 5 10
2 -1 -1
3 5 1

SAMPLE OUTPUT
21 3
4 2 1

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