vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Tug of war is a sport that directly puts two teams against each other in a test of strength.

During school days, both Chef Shifu and Chef Po were champions of tug of war.
On behalf of restaurant's anniversary, Chef Shifu and Chef Po have decided to conduct 
a tug of war game for their customers.


Master Chef Oogway has decided the following rules for the game.


    Let N be the number of players participating in the game. All of these 
    players would stand in a circle in clock wise direction.
    

    There are an infinite number of long ropes available.
    When a rope is held by exactly two players, it is termed as bonding.
    

    At least one bonding is necessary to conduct a game.
    

    A player can play against multiple people simultaneously i.e he can have more than one bonding at
    the same time. 
    

    Both members of a pair of players that have a bonding must have the same number of total
    bondings. That is, if the player A  makes bonding with the player B,
    then the number of total bondings of the player A must be the same as
    that of the player B.
    

    Bondings should be created in such a fashion that ropes must not intersect each other. 
    

    The number of bondings of every player must be no more than K.
    


Now Master Chef Oogway asked Chef Shifu and Chef Po to find out the number of possible games.
Your task is to help them find this number. As this number might become huge,
you've to find it modulo (10^14+7). Two games are different iff there is some
bonding that is present in only of them. 



Input
First line contains T, the number of test cases.
Each of T lines contain 2 positive integers N and K separated by a space.


Output
For each test case, output the number of ways to conduct the game modulo 100000000000007 (10^14+7) in one line.


Example

Input:
3
3 2
4 0
2 1

Output:
4
0
1

Explanation:

For the 1st case, there are 3 players. Let's call them p1, p2, p3.
Different games possible are:
Game 1: p1-p2 (numbers of bondings of p1, p2 are 1 ≤ K = 2)
Game 2: p1-p3 (numbers of bondings of p1, p3 are 1 ≤ K = 2)
Game 3: p2-p3 (numbers of bondings of p2, p3 are 1 ≤ K = 2)
Game 4: p1-p2, p1-p3, p2-p3 (numbers of bondings of p1, p2, p3 are 2 ≤ K
= 2)


For the 2nd test case, we cannot form the game, because K = 0 and hence no
player is allowed to make any bonding. As any game must have atleast one
bonding, no game is possible here. 


For the 3rd case, only possible game is:
Game 1: p1-p2 (number of bondings in p1, p2 are 1)



Constraints
1 ≤ T ≤ 10000
0 ≤ N ≤ 10000
0 ≤ K ≤ N

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During the winter holidays, the demand for Christmas balls is exceptionally high. Since it's already 2018, the advances in alchemy allow easy and efficient ball creation by utilizing magic crystals.

Grisha needs to obtain some yellow, green and blue balls. It's known that to produce a yellow ball one needs two yellow crystals, green — one yellow and one blue, and for a blue ball, three blue crystals are enough.

Right now there are A yellow and B blue crystals in Grisha's disposal. Find out how many additional crystals he should acquire in order to produce the required number of balls.


-----Input-----

The first line features two integers A and B (0 ≤ A, B ≤ 10^9), denoting the number of yellow and blue crystals respectively at Grisha's disposal.

The next line contains three integers x, y and z (0 ≤ x, y, z ≤ 10^9) — the respective amounts of yellow, green and blue balls to be obtained.


-----Output-----

Print a single integer — the minimum number of crystals that Grisha should acquire in addition.


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

Output
2

Input
3 9
1 1 3

Output
1

Input
12345678 87654321
43043751 1000000000 53798715

Output
2147483648



-----Note-----

In the first sample case, Grisha needs five yellow and four blue crystals to create two yellow balls, one green ball, and one blue ball. To do that, Grisha needs to obtain two additional crystals: one yellow and one blue.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Complete the function that takes two numbers as input, ```num``` and ```nth``` and return the `nth` digit of `num` (counting from right to left).

## Note
- If ```num``` is negative, ignore its sign and treat it as a positive value
- If ```nth``` is not positive, return `-1`
- Keep in mind that `42 = 00042`. This means that ```findDigit(42, 5)``` would return `0`

## Examples

```
findDigit(5673, 4)     returns 5
findDigit(129, 2)      returns 2
findDigit(-2825, 3)    returns 8
findDigit(-456, 4)     returns 0
findDigit(0, 20)       returns 0
findDigit(65, 0)       returns -1
findDigit(24, -8)      returns -1
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We’ve all seen katas that ask for conversion from snake-case to camel-case, from camel-case to snake-case, or from camel-case to kebab-case — the possibilities are endless.

But if we don’t know the case our inputs are in, these are not very helpful.

### Task:

So the task here is to implement a function (called `id` in Ruby/Crystal/JavaScript/CoffeeScript and `case_id` in Python/C) that takes a string, `c_str`, and returns a string with the case the input is in. The possible case types are “kebab”, “camel”, and ”snake”. If none of the cases match with the input, or if there are no 'spaces' in the input (for example in snake case, spaces would be '_'s), return “none”. Inputs will only have letters (no numbers or special characters).

### Some definitions

Kebab case: `lowercase-words-separated-by-hyphens`

Camel case: `lowercaseFirstWordFollowedByCapitalizedWords`

Snake case: `lowercase_words_separated_by_underscores`

### Examples:

```python
case_id(“hello-world”) #=> “kebab”
case_id(“hello-to-the-world”) #=> “kebab”
case_id(“helloWorld”) #=> “camel”
case_id(“helloToTheWorld”) #=> “camel”
case_id(“hello_world”) #=> “snake”
case_id(“hello_to_the_world”) #=> “snake”
case_id(“hello__world”) #=> “none”
case_id(“hello_World”) #=> “none”
case_id(“helloworld”) #=> “none”
case_id(“hello-World”) #=> “none”
```

Also check out my other creations — [Split Without Loss](https://www.codewars.com/kata/split-without-loss), [Adding Fractions](https://www.codewars.com/kata/adding-fractions),
[Random Integers](https://www.codewars.com/kata/random-integers), [Implement String#transpose](https://www.codewars.com/kata/implement-string-number-transpose), [Implement Array#transpose!](https://www.codewars.com/kata/implement-array-number-transpose), [Arrays and Procs #1](https://www.codewars.com/kata/arrays-and-procs-number-1), and [Arrays and Procs #2](https://www.codewars.com/kata/arrays-and-procs-number-2)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let us denote by f(x, m) the remainder of the Euclidean division of x by m.
Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M).
Find \displaystyle{\sum_{i=1}^N A_i}.

-----Constraints-----
 - 1 \leq N \leq 10^{10}
 - 0 \leq X < M \leq 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N X M

-----Output-----
Print \displaystyle{\sum_{i=1}^N A_i}.

-----Sample Input-----
6 2 1001

-----Sample Output-----
1369

The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Permutation p is a sequence of integers p=[p_1, p_2, ..., p_n], consisting of n distinct (unique) positive integers between 1 and n, inclusive. For example, the following sequences are permutations: [3, 4, 1, 2], [1], [1, 2]. The following sequences are not permutations: [0], [1, 2, 1], [2, 3], [0, 1, 2].

The important key is in the locked box that you need to open. To open the box you need to enter secret code. Secret code is a permutation p of length n. 

You don't know this permutation, you only know the array q of prefix maximums of this permutation. Formally:

  * q_1=p_1, 
  * q_2=max(p_1, p_2), 
  * q_3=max(p_1, p_2,p_3), 
  * ... 
  * q_n=max(p_1, p_2,...,p_n). 



You want to construct any possible suitable permutation (i.e. any such permutation, that calculated q for this permutation is equal to the given array).

Input

The first line contains integer number t (1 ≤ t ≤ 10^4) — the number of test cases in the input. Then t test cases follow.

The first line of a test case contains one integer n (1 ≤ n ≤ 10^{5}) — the number of elements in the secret code permutation p.

The second line of a test case contains n integers q_1, q_2, ..., q_n (1 ≤ q_i ≤ n) — elements of the array q for secret permutation. It is guaranteed that q_i ≤ q_{i+1} for all i (1 ≤ i < n).

The sum of all values n over all the test cases in the input doesn't exceed 10^5.

Output

For each test case, print:

  * If it's impossible to find such a permutation p, print "-1" (without quotes). 
  * Otherwise, print n distinct integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n). If there are multiple possible answers, you can print any of them. 

Example

Input


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


Output


1 3 4 5 2 
-1
2 1 
1 

Note

In the first test case of the example answer [1,3,4,5,2] is the only possible answer:

  * q_{1} = p_{1} = 1; 
  * q_{2} = max(p_{1}, p_{2}) = 3; 
  * q_{3} = max(p_{1}, p_{2}, p_{3}) = 4; 
  * q_{4} = max(p_{1}, p_{2}, p_{3}, p_{4}) = 5; 
  * q_{5} = max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5. 



It can be proved that there are no answers for the second test case of the example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a string $S$ let the unique set of characters that occur in it one or more times be $C$. Consider a permutation of the elements of $C$ as $(c_1, c_2, c_3 ... )$. Let $f(c)$ be the number of times $c$ occurs in $S$.
If any such permutation of the elements of $C$ satisfies $f(c_i) = f(c_{i-1}) + f(c_{i-2})$ for all $i \ge 3$, the string is said to be a dynamic string.
Mr Bancroft is given the task to check if the string is dynamic, but he is busy playing with sandpaper. Would you help him in such a state?
Note that if the number of distinct characters in the string is less than 3, i.e. if $|C| < 3$, then the string is always dynamic.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, a string $S$.

-----Output:-----
For each testcase, output in a single line "Dynamic" if the given string is dynamic, otherwise print "Not". (Note that the judge is case sensitive)

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq |S| \leq 10^5$
- $S$ contains only lower case alphabets: $a$, $b$, …, $z$

-----Sample Input:-----
3
aaaabccc
aabbcc
ppppmmnnoooopp

-----Sample Output:-----
Dynamic
Not
Dynamic

-----Explanation:-----
- Testase 1: For the given string, $C = \{a, b, c\}$ and $f(a)=4, f(b)=1, f(c)=3$. $f(a) = f(c) + f(b)$ so the permutation $(b, c, a)$ satisfies the requirement.
- Testcase 2: Here too $C = \{a, b, c\}$ but no permutation satisfies the requirement of a dynamic string.
- Testcase 3: Here $C = \{m, n, o, p\}$ and $(m, n, o, p)$ is a permutation that makes it a dynamic string.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Nephren Runs a Cinema

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Lakhesh loves to make movies, so Nephren helps her run a cinema. We may call it No. 68 Cinema.



However, one day, the No. 68 Cinema runs out of changes (they don't have 50-yuan notes currently), but Nephren still wants to start their business. (Assume that yuan is a kind of currency in Regulu Ere.)

There are three types of customers: some of them bring exactly a 50-yuan note; some of them bring a 100-yuan note and Nephren needs to give a 50-yuan note back to him/her; some of them bring VIP cards so that they don't need to pay for the ticket.

Now *n* customers are waiting outside in queue. Nephren wants to know how many possible queues are there that they are able to run smoothly (i.e. every customer can receive his/her change), and that the number of 50-yuan notes they have after selling tickets to all these customers is between *l* and *r*, inclusive. Two queues are considered different if there exists a customer whose type is different in two queues. As the number can be large, please output the answer modulo *p*.

Input Specification:
One line containing four integers *n* (1<=≤<=*n*<=≤<=105), *p* (1<=≤<=*p*<=≤<=2·109), *l* and *r* (0<=≤<=*l*<=≤<=*r*<=≤<=*n*).

Output Specification:
One line indicating the answer modulo *p*.

Demo Input:
['4 97 2 3\n', '4 100 0 4\n']

Demo Output:
['13\n', '35\n']

Note:
We use A, B and C to indicate customers with 50-yuan notes, customers with 100-yuan notes and customers with VIP cards respectively.

For the first sample, the different possible queues that there are 2 50-yuan notes left are AAAB, AABA, ABAA, AACC, ACAC, ACCA, CAAC, CACA and CCAA, and the different possible queues that there are 3 50-yuan notes left are AAAC, AACA, ACAA and CAAA. So there are 13 different queues satisfying the first sample. Similarly, there are 35 different queues satisfying the second sample.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Berland annual chess tournament is coming!

Organizers have gathered 2·n chess players who should be divided into two teams with n people each. The first team is sponsored by BerOil and the second team is sponsored by BerMobile. Obviously, organizers should guarantee the win for the team of BerOil.

Thus, organizers should divide all 2·n players into two teams with n people each in such a way that the first team always wins.

Every chess player has its rating r_{i}. It is known that chess player with the greater rating always wins the player with the lower rating. If their ratings are equal then any of the players can win.

After teams assignment there will come a drawing to form n pairs of opponents: in each pair there is a player from the first team and a player from the second team. Every chess player should be in exactly one pair. Every pair plays once. The drawing is totally random.

Is it possible to divide all 2·n players into two teams with n people each so that the player from the first team in every pair wins regardless of the results of the drawing?


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100).

The second line contains 2·n integers a_1, a_2, ... a_2n (1 ≤ a_{i} ≤ 1000).


-----Output-----

If it's possible to divide all 2·n players into two teams with n people each so that the player from the first team in every pair wins regardless of the results of the drawing, then print "YES". Otherwise print "NO".


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

Output
YES

Input
1
3 3

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You receive some random elements as a space-delimited string. Check if the elements are part of an ascending sequence of integers starting with 1, with an increment of 1 (e.g. 1, 2, 3, 4).

Return:

* `0` if the elements can form such a sequence, and no number is missing ("not broken", e.g. `"1 2 4 3"`)
* `1` if there are any non-numeric elements in the input ("invalid", e.g. `"1 2 a"`)
* `n` if the elements are part of such a sequence, but some numbers are missing, and `n` is the lowest of them ("broken", e.g. `"1 2 4"` or `"1 5"`)


## Examples
```
"1 2 3 4"  ==>  return 0, because the sequence is complete

"1 2 4 3"  ==>  return 0, because the sequence is complete (order doesn't matter)

"2 1 3 a"  ==>  return 1, because it contains a non numerical character

"1 3 2 5"  ==>  return 4, because 4 is missing from the sequence

"1 5"      ==>  return 2, because the sequence is missing 2, 3, 4 and 2 is the lowest

```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
General Payne has a battalion of n soldiers. The soldiers' beauty contest is coming up, it will last for k days. Payne decided that his battalion will participate in the pageant. Now he has choose the participants.

All soldiers in the battalion have different beauty that is represented by a positive integer. The value a_{i} represents the beauty of the i-th soldier.

On each of k days Generals has to send a detachment of soldiers to the pageant. The beauty of the detachment is the sum of the beauties of the soldiers, who are part of this detachment. Payne wants to surprise the jury of the beauty pageant, so each of k days the beauty of the sent detachment should be unique. In other words, all k beauties of the sent detachments must be distinct numbers.

Help Payne choose k detachments of different beauties for the pageant. Please note that Payne cannot just forget to send soldiers on one day, that is, the detachment of soldiers he sends to the pageant should never be empty.


-----Input-----

The first line contains two integers n, k (1 ≤ n ≤ 50; 1 ≤ k ≤  $\frac{n(n + 1)}{2}$) — the number of soldiers and the number of days in the pageant, correspondingly. The second line contains space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^7) — the beauties of the battalion soldiers.

It is guaranteed that Payne's battalion doesn't have two soldiers with the same beauty.


-----Output-----

Print k lines: in the i-th line print the description of the detachment that will participate in the pageant on the i-th day. The description consists of integer c_{i} (1 ≤ c_{i} ≤ n) — the number of soldiers in the detachment on the i-th day of the pageant and c_{i} distinct integers p_{1, }i, p_{2, }i, ..., p_{c}_{i}, i — the beauties of the soldiers in the detachment on the i-th day of the pageant. The beauties of the soldiers are allowed to print in any order.

Separate numbers on the lines by spaces. It is guaranteed that there is the solution that meets the problem conditions. If there are multiple solutions, print any of them.


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

Output
1 1
1 2
2 3 2

Input
2 1
7 12

Output
1 12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya got n cubes. He decided to build a pyramid from them. Vanya wants to build the pyramid as follows: the top level of the pyramid must consist of 1 cube, the second level must consist of 1 + 2 = 3 cubes, the third level must have 1 + 2 + 3 = 6 cubes, and so on. Thus, the i-th level of the pyramid must have 1 + 2 + ... + (i - 1) + i cubes.

Vanya wants to know what is the maximum height of the pyramid that he can make using the given cubes.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^4) — the number of cubes given to Vanya.


-----Output-----

Print the maximum possible height of the pyramid in the single line.


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

Output
1

Input
25

Output
4



-----Note-----

Illustration to the second sample:  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This kata generalizes [Twice Linear](https://www.codewars.com/kata/5672682212c8ecf83e000050). You may want to attempt that kata first.

## Sequence

Consider an integer sequence `U(m)` defined as:

1. `m` is a given non-empty set of positive integers.
2. `U(m)[0] = 1`, the first number is always 1.
3. For each `x` in `U(m)`, and each `y` in `m`, `x * y + 1` must also be in `U(m)`.
4. No other numbers are in `U(m)`.
5. `U(m)` is sorted, with no duplicates.

### Sequence Examples

#### `U(2, 3) = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]`

1 produces 3 and 4, since `1 * 2 + 1 = 3`, and `1 * 3 + 1 = 4`.

3 produces 7 and 10, since `3 * 2 + 1 = 7`, and `3 * 3 + 1 = 10`.

#### `U(5, 7, 8) = [1, 6, 8, 9, 31, 41, 43, 46, 49, 57, 64, 65, 73, 156, 206, ...]`

1 produces 6, 8, and 9.

6 produces 31, 43, and 49.

## Task:

Implement `n_linear` or `nLinear`: given a set of postive integers `m`, and an index `n`, find `U(m)[n]`, the `n`th value in the `U(m)` sequence.

### Tips

* Tests use large n values. Slow algorithms may time-out.
* Tests use large values in the m set. Algorithms which multiply further than neccessary may overflow.
* Linear run time and memory usage is possible.
* How can you build the sequence iteratively, without growing extra data structures?

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hilbert's Hotel is a very unusual hotel since the number of rooms is infinite! In fact, there is exactly one room for every integer, including zero and negative integers. Even stranger, the hotel is currently at full capacity, meaning there is exactly one guest in every room. The hotel's manager, David Hilbert himself, decides he wants to shuffle the guests around because he thinks this will create a vacancy (a room without a guest).

For any integer $k$ and positive integer $n$, let $k\bmod n$ denote the remainder when $k$ is divided by $n$. More formally, $r=k\bmod n$ is the smallest non-negative integer such that $k-r$ is divisible by $n$. It always holds that $0\le k\bmod n\le n-1$. For example, $100\bmod 12=4$ and $(-1337)\bmod 3=1$.

Then the shuffling works as follows. There is an array of $n$ integers $a_0,a_1,\ldots,a_{n-1}$. Then for each integer $k$, the guest in room $k$ is moved to room number $k+a_{k\bmod n}$.

After this shuffling process, determine if there is still exactly one guest assigned to each room. That is, there are no vacancies or rooms with multiple guests.


-----Input-----

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. Next $2t$ lines contain descriptions of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of the array.

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

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


-----Output-----

For each test case, output a single line containing "YES" if there is exactly one guest assigned to each room after the shuffling process, or "NO" otherwise. You can print each letter in any case (upper or lower).


-----Example-----
Input
6
1
14
2
1 -1
4
5 5 5 1
3
3 2 1
2
0 1
5
-239 -2 -100 -3 -11

Output
YES
YES
YES
NO
NO
YES



-----Note-----

In the first test case, every guest is shifted by $14$ rooms, so the assignment is still unique.

In the second test case, even guests move to the right by $1$ room, and odd guests move to the left by $1$ room. We can show that the assignment is still unique.

In the third test case, every fourth guest moves to the right by $1$ room, and the other guests move to the right by $5$ rooms. We can show that the assignment is still unique.

In the fourth test case, guests $0$ and $1$ are both assigned to room $3$.

In the fifth test case, guests $1$ and $2$ are both assigned to room $2$.

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