vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
# Task
Given some sticks by an array `V` of positive integers, where V[i] represents the length of the sticks, find the number of ways we can choose three of them to form a triangle.

# Example

 For `V = [2, 3, 7, 4]`, the result should be `1`.

 There is only `(2, 3, 4)` can form a triangle.
 
 For `V = [5, 6, 7, 8]`, the result should be `4`.
 
 `(5, 6, 7), (5, 6, 8), (5, 7, 8), (6, 7, 8)` 

# Input/Output


 - `[input]` integer array `V`

 stick lengths
 
 `3 <= V.length <= 100`
 
 `0 < V[i] <=100`


 - `[output]` an integer

 number of ways we can choose 3 sticks to form a triangle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have just bought a new house, and it has a huge, beautiful lawn. A lawn that needs cutting. Several times. Every week. The whole summer. 

After pushing the lawnmower around the lawn during the hottest Saturday afternoon in history, you decided that there must be a better way. And then you saw the ads for the new robotic lawnmovers. But which one should you buy? They all have different cutting speeds, cutting times and recharge times, not to mention different prices!

According to the advertisement, a robotic lawnmover will spend all its time either cutting the lawn or recharging its battery. Starting from a full battery, it will cut the lawn at a given rate of $c$ square meters per minute for a cutting time of $t$ minutes, after which it has run out of battery. Once out of battery, it will immediately start recharging. After recharging for $r$ minutes the battery is full again and it immediately starts cutting.

You decide that in order for your lawn to look sufficiently prim and proper, the lawnmower that you buy must be powerful enough to cut your whole lawn at least once a week on average. Formally, if we start the mower fully charged at the beginning of the week and run it for exactly $T$ weeks, it needs to cut the whole lawn at least $T$ times, for all positive integers $T$. But apart from this, you have no specific requirements, so among the ones that satisfy this requirement, you will simply go for the cheapest option. For the purposes of cutting your lawn, you may make the simplifying assumption that a week is always exactly $10080$ minutes long.

-----Input-----
The first line of input contains two integers $\ell $ and $m$ ($1 \le \ell \le 10^6$, $1 \le m \le 100$), the size of your lawn in square meters, and the number of lawnmowers to consider, respectively.

Then follow $m$ lines, each containing a string $n$ and $4$ integers $p$, $c$, $t$, and $r$, separated by commas, describing a lawnmower as follows:
 - $n$ is the name of the lawnmower, a string of at most $60$ printable characters (ASCII $32$ to $126$) excluding ‘,’, neither starting nor ending with a space,
 - $1 \leq p \leq 100000$ is the price of the lawnmover,
 - $1 \leq c \leq 100$ is the cutting rate in square meters per minute,
 - $1 \leq t \leq 10080$ is the cutting time in minutes, and
 - $1 \leq r \leq 10080$ is the recharge time in minutes.

-----Output-----
Output the name of the cheapest lawnmower capable of cutting your whole yard at least once a week on average. If several lawnmovers share the same lowest price, output all of their names, in the same order they were given in the input. If there is no such mower, output “no such mower”.

-----Examples-----
Sample Input:
7000 4
Grass Slayer 2000,9999,10,120,120
Slow-Mowe,999,1,120,240
Eco-cut X2,5499,2,25,35
Mowepower,5499,3,25,35
Sample Output:
Eco-cut X2
Mowepower

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer sequence A of length N and an integer K.
You will perform the following operation on this sequence Q times:
 - Choose a contiguous subsequence of length K, then remove the smallest element among the K elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).
Let X and Y be the values of the largest and smallest element removed in the Q operations. You would like X-Y to be as small as possible.
Find the smallest possible value of X-Y when the Q operations are performed optimally.

-----Constraints-----
 - 1 \leq N \leq 2000
 - 1 \leq K \leq N
 - 1 \leq Q \leq N-K+1
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K Q
A_1 A_2 ... A_N

-----Output-----
Print the smallest possible value of X-Y.

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

-----Sample Output-----
1

In the first operation, whichever contiguous subsequence of length 3 we choose, the minimum element in it is 1.
Thus, the first operation removes A_3=1 and now we have A=(4,3,5,2).
In the second operation, it is optimal to choose (A_2,A_3,A_4)=(3,5,2) as the contiguous subsequence of length 3 and remove A_4=2.
In this case, the largest element removed is 2, and the smallest is 1, so their difference is 2-1=1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mister B has a house in the middle of a giant plain field, which attracted aliens life. For convenience, aliens specified the Cartesian coordinate system on the field in such a way that Mister B's house has coordinates (0, 0). After that they sent three beacons to the field, but something went wrong. One beacon was completely destroyed, while the other two landed in positions with coordinates (m, 0) and (0, n), respectively, but shut down.

Mister B was interested in this devices, so he decided to take them home. He came to the first beacon, placed at (m, 0), lifted it up and carried the beacon home choosing the shortest path. After that he came to the other beacon, placed at (0, n), and also carried it home choosing the shortest path. When first beacon was lifted up, the navigation system of the beacons was activated.

Partially destroyed navigation system started to work in following way.

At time moments when both survived beacons are at points with integer coordinates the system tries to find a location for the third beacon. It succeeds if and only if there is a point with integer coordinates such that the area of the triangle formed by the two survived beacons and this point is equal to s. In this case the system sends a packet of information with beacon positions to aliens, otherwise it doesn't.

Compute how many packets of information system sent while Mister B was moving the beacons.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases. The next 3·t lines describe t test cases. 

Every test case is described in three lines as follows. Note that each parameter is given as a product of three factors.

The first line of a test case contains three space-separated integers: n1, n2, n3 (1 ≤ ni ≤ 106) such that n = n1·n2·n3.

The second line contains three space-separated integers: m1, m2, m3 (1 ≤ mi ≤ 106) such that m = m1·m2·m3.

The third line contains three space-separated integers: s1, s2, s3 (1 ≤ si ≤ 106) such that s = s1·s2·s3.

Note that for hacks only tests with t = 1 allowed.

Output

Print t integers one per line — the answers for each test.

Example

Input

3
2 1 1
2 1 1
1 1 3
1 5 1
2 2 1
1 1 2
10 6 18
2 103 2
13 1 13


Output

4
7
171

Note

First test case contains the following beacon positions: (2, 0) and (0, 2), s = 3. The following packets could be sent: ((2, 0), (0, 2), ( - 1, 0)), ((1, 0), (0, 2), (4, 0)), ((0, 0), (0, 2), (3, 1)), ((0, 0), (0, 1), ( - 6, 0)), where (b1, b2, p) has next description: b1 — first beacon position, b2 — second beacon position, p — some generated point.

Second test case contains the following beacon initial positions: (4, 0) and (0, 5), s = 2. The following packets could be sent: ((4, 0), (0, 5), (0, 4)), ((3, 0), (0, 5), (2, 3)), ((2, 0), (0, 5), (2, 2)), ((1, 0), (0, 5), (1, 4)), ((0, 0), (0, 4), (0, - 1)), ((0, 0), (0, 2), (2, 0)), ((0, 0), (0, 1), (4, 0)).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given 2 integers u and v, find the shortest array such that [bitwise-xor](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of its elements is u, and the sum of its elements is v.

Input

The only line contains 2 integers u and v (0 ≤ u,v ≤ 10^{18}).

Output

If there's no array that satisfies the condition, print "-1". Otherwise:

The first line should contain one integer, n, representing the length of the desired array. The next line should contain n positive integers, the array itself. If there are multiple possible answers, print any.

Examples

Input


2 4


Output


2
3 1

Input


1 3


Output


3
1 1 1

Input


8 5


Output


-1

Input


0 0


Output


0

Note

In the first sample, 3⊕ 1 = 2 and 3 + 1 = 4. There is no valid array of smaller length.

Notice that in the fourth sample the array is empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Going to a contest such as NWERC is not all fun and games, there are also some worldly matters to tend to. One of these is to book hotel rooms in time, before all the rooms in town are booked. 

In this problem, you should write a program to search for available rooms in a given hotel. The hotel has $r$ rooms, numbered from $1$ to $r$, and you will be given a list describing which of these rooms are already booked.

-----Input-----
The input consists of:
 - one line with two integers $r$ and $n$ ($1\leq r \leq 100$, $0 \leq n \le r$), the number of rooms in the hotel and the number of rooms that are already booked, respectively;
 - $n$ lines, each with an integer between $1$ and $r$ (inclusive), a room number that is already booked;

All $n$ room numbers of the already booked rooms are distinct.

-----Output-----
If there are available rooms, output the room number of any such room. Otherwise, output “too late”.

-----Examples-----
Sample Input:
100 5
42
3
2
99
1
Sample Output:
23

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef's last task in his internship requires him to construct 2 permutations, each having length N, such that the [bitwise AND] of each pair of elements at every index is the same.

Formally, if the permutations are A and B, then, the value A_{i} \& B_{i} must be constant over all 1≤ i ≤ N.

Help Chef by providing him 2 such permutations. If it is not possible to construct such permutations, print -1 instead.

A permutation is a sequence of integers from 1 to N of length N containing each number exactly once.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, a single integer N denoting the size of the required permutations.

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

- If there are valid permutations that satisfy the required condition, then:
- In the first line, output N space-separated integers denoting the permutation A.
- In the second line, output N space-separated integers denoting the permutation B.
- If there is no valid pair of permutations, print -1 in a single line. 

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2\cdot 10^{5}$.

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

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

----- explanation 1 ------ 
Test case $1$: There is only one element in each array and the resultant bitwise AND is $1$. Thus, $A = [1]$ and $B = [1]$.

Test case $2$: Let $A = [1,2]$ and $B = [2,1]$. The resultant bitwise AND of each pair at any index is equal to $0$. So, this is a valid pair of permutations.

Test case $3$: There are $6$ permutations of length $3$. It can be seen that any pair of the $6$ permutations does not satisfy the stated condition.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A word from the English dictionary is taken and arranged as a matrix. e.g. "MATHEMATICS"

MATHE  
ATHEM  
THEMA  
HEMAT  
EMATI  
MATIC  
ATICS  

There are many ways to trace this matrix in a way that helps you construct this word. You start tracing the matrix from the top-left position and at each iteration, you either move RIGHT or DOWN, and ultimately reach the bottom-right of the matrix. It is assured that any such tracing generates the same word. How many such tracings can be possible for a given
word of length m+n-1 written as a matrix of size m * n?

Input Format 

The first line of input contains an integer T. T test cases follow. 

Each test case contains 2 space separated integers m & n (in a new line) indicating that the matrix has m rows and each row has n characters.  

Constraints 

1 <= T <= 10^{3} 

1 ≤ m,n ≤ 10^{6}

Output Format 

Print the number of ways (S) the word can be traced as explained in the problem statement.
If the number is larger than 10^{9}+7, 

print  S mod (10^9 + 7) for each testcase (in a new line). 

Sample Input

1
2 3

Sample Output

3

Explanation 

Let's consider a word AWAY written as the matrix

AWA
WAY

Here, the word AWAY can be traced in 3 different ways, traversing either RIGHT or DOWN.

AWA
  Y

AW
 AY

A
WAY

Hence the answer is 3.

Timelimit
Time limit for this challenge is given here

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There's no day that Kevin doesn't want to explode something. 

Today Kevin and Elvis decided to make a dynamite. They have N packages of explosives (N is an even number). The i-th package contains two boxes: one has ai grams of explosives the other  bi grams. Elvis and Kevin alternatively take any package and add one of the boxes to a giant dynamite. Another box is discarded. Elvis starts this process. Kevin believes an explosion is beautiful if the giant dynamite contains exactly x grams of explosives. But he hasn't decided on the value of x yet. This process ends when all boxes are taken.

Help him and determine for each of Q values xi whether Kevin can make a dynamite with exactly xi  grams of explosives regardless of the Elvis' moves.  

Input format:

The first line contains 2 space-separated integers N and Q. It's guaranteed that N is an even number.
Each of the following N lines contain two space-separated integers ai and bi.
Each of the following Q lines contain one integer xi.

Output format:

For each number xi output "YES" (without quotes) if Kevin can make a dynamite which contains exactly xi grams of explosives regardless of the Elvis' moves and "NO" otherwise.

Constraints:
 1 ≤ N, Q ≤ 10^5 
 0 ≤ ai , bi ≤ 10^9 
 0 ≤ x ≤ 10^15 
N ≤ 20 in test data worth 24% of all points

SAMPLE INPUT
2 4
4 7
5 2
4
9
12
0

SAMPLE OUTPUT
NO
YES
NO
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrewid the Android is a galaxy-famous detective. He is now chasing a criminal hiding on the planet Oxa-5, the planet almost fully covered with water.

The only dry land there is an archipelago of n narrow islands located in a row. For more comfort let's represent them as non-intersecting segments on a straight line: island i has coordinates [l_{i}, r_{i}], besides, r_{i} < l_{i} + 1 for 1 ≤ i ≤ n - 1.

To reach the goal, Andrewid needs to place a bridge between each pair of adjacent islands. A bridge of length a can be placed between the i-th and the (i + 1)-th islads, if there are such coordinates of x and y, that l_{i} ≤ x ≤ r_{i}, l_{i} + 1 ≤ y ≤ r_{i} + 1 and y - x = a. 

The detective was supplied with m bridges, each bridge can be used at most once. Help him determine whether the bridges he got are enough to connect each pair of adjacent islands.


-----Input-----

The first line contains integers n (2 ≤ n ≤ 2·10^5) and m (1 ≤ m ≤ 2·10^5) — the number of islands and bridges.

Next n lines each contain two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 10^18) — the coordinates of the island endpoints.

The last line contains m integer numbers a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ 10^18) — the lengths of the bridges that Andrewid got.


-----Output-----

If it is impossible to place a bridge between each pair of adjacent islands in the required manner, print on a single line "No" (without the quotes), otherwise print in the first line "Yes" (without the quotes), and in the second line print n - 1 numbers b_1, b_2, ..., b_{n} - 1, which mean that between islands i and i + 1 there must be used a bridge number b_{i}. 

If there are multiple correct answers, print any of them. Note that in this problem it is necessary to print "Yes" and "No" in correct case.


-----Examples-----
Input
4 4
1 4
7 8
9 10
12 14
4 5 3 8

Output
Yes
2 3 1 

Input
2 2
11 14
17 18
2 9

Output
No

Input
2 1
1 1
1000000000000000000 1000000000000000000
999999999999999999

Output
Yes
1 



-----Note-----

In the first sample test you can, for example, place the second bridge between points 3 and 8, place the third bridge between points 7 and 10 and place the first bridge between points 10 and 14.

In the second sample test the first bridge is too short and the second bridge is too long, so the solution doesn't exist.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oh, New Year. The time to gather all your friends and reflect on the heartwarming events of the past year...

$n$ friends live in a city which can be represented as a number line. The $i$-th friend lives in a house with an integer coordinate $x_i$. The $i$-th friend can come celebrate the New Year to the house with coordinate $x_i-1$, $x_i+1$ or stay at $x_i$. Each friend is allowed to move no more than once.

For all friends $1 \le x_i \le n$ holds, however, they can come to houses with coordinates $0$ and $n+1$ (if their houses are at $1$ or $n$, respectively).

For example, let the initial positions be $x = [1, 2, 4, 4]$. The final ones then can be $[1, 3, 3, 4]$, $[0, 2, 3, 3]$, $[2, 2, 5, 5]$, $[2, 1, 3, 5]$ and so on. The number of occupied houses is the number of distinct positions among the final ones.

So all friends choose the moves they want to perform. After that the number of occupied houses is calculated. What is the minimum and the maximum number of occupied houses can there be?


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of friends.

The second line contains $n$ integers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le n$) — the coordinates of the houses of the friends.


-----Output-----

Print two integers — the minimum and the maximum possible number of occupied houses after all moves are performed.


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

Output
2 4

Input
9
1 1 8 8 8 4 4 4 4

Output
3 8

Input
7
4 3 7 1 4 3 3

Output
3 6



-----Note-----

In the first example friends can go to $[2, 2, 3, 3]$. So friend $1$ goes to $x_1+1$, friend $2$ stays at his house $x_2$, friend $3$ goes to $x_3-1$ and friend $4$ goes to $x_4-1$. $[1, 1, 3, 3]$, $[2, 2, 3, 3]$ or $[2, 2, 4, 4]$ are also all valid options to obtain $2$ occupied houses.

For the maximum number of occupied houses friends can go to $[1, 2, 3, 4]$ or to $[0, 2, 4, 5]$, for example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everybody knows what an arithmetic progression is. Let us remind you just in case that an arithmetic progression is such sequence of numbers a_1, a_2, ..., a_{n} of length n, that the following condition fulfills: a_2 - a_1 = a_3 - a_2 = a_4 - a_3 = ... = a_{i} + 1 - a_{i} = ... = a_{n} - a_{n} - 1.

For example, sequences [1, 5], [10], [5, 4, 3] are arithmetic progressions and sequences [1, 3, 2], [1, 2, 4] are not.

Alexander has n cards containing integers. Arthur wants to give Alexander exactly one more card with a number so that he could use the resulting n + 1 cards to make an arithmetic progression (Alexander has to use all of his cards).

Arthur has already bought a card but he hasn't written a number on it. Help him, print all integers that you can write on a card so that the described condition fulfilled.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of cards. The next line contains the sequence of integers — the numbers on Alexander's cards. The numbers are positive integers, each of them doesn't exceed 10^8.


-----Output-----

If Arthur can write infinitely many distinct integers on the card, print on a single line -1.

Otherwise, print on the first line the number of integers that suit you. In the second line, print the numbers in the increasing order. Note that the numbers in the answer can exceed 10^8 or even be negative (see test samples).


-----Examples-----
Input
3
4 1 7

Output
2
-2 10

Input
1
10

Output
-1

Input
4
1 3 5 9

Output
1
7

Input
4
4 3 4 5

Output
0

Input
2
2 4

Output
3
0 3 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tenten runs a weapon shop for ninjas. Today she is willing to sell $n$ shurikens which cost $1$, $2$, ..., $n$ ryo (local currency). During a day, Tenten will place the shurikens onto the showcase, which is empty at the beginning of the day. Her job is fairly simple: sometimes Tenten places another shuriken (from the available shurikens) on the showcase, and sometimes a ninja comes in and buys a shuriken from the showcase. Since ninjas are thrifty, they always buy the cheapest shuriken from the showcase.

Tenten keeps a record for all events, and she ends up with a list of the following types of records:

  + means that she placed another shuriken on the showcase;  - x means that the shuriken of price $x$ was bought. 

Today was a lucky day, and all shurikens were bought. Now Tenten wonders if her list is consistent, and what could be a possible order of placing the shurikens on the showcase. Help her to find this out!


-----Input-----

The first line contains the only integer $n$ ($1\leq n\leq 10^5$) standing for the number of shurikens. 

The following $2n$ lines describe the events in the format described above. It's guaranteed that there are exactly $n$ events of the first type, and each price from $1$ to $n$ occurs exactly once in the events of the second type.


-----Output-----

If the list is consistent, print "YES". Otherwise (that is, if the list is contradictory and there is no valid order of shurikens placement), print "NO".

In the first case the second line must contain $n$ space-separated integers denoting the prices of shurikens in order they were placed. If there are multiple answers, print any.


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

Output
YES
4 2 3 1 

Input
1
- 1
+

Output
NO

Input
3
+
+
+
- 2
- 1
- 3

Output
NO



-----Note-----

In the first example Tenten first placed shurikens with prices $4$ and $2$. After this a customer came in and bought the cheapest shuriken which costed $2$. Next, Tenten added a shuriken with price $3$ on the showcase to the already placed $4$-ryo. Then a new customer bought this $3$-ryo shuriken. After this she added a $1$-ryo shuriken. Finally, the last two customers bought shurikens $1$ and $4$, respectively. Note that the order $[2, 4, 3, 1]$ is also valid.

In the second example the first customer bought a shuriken before anything was placed, which is clearly impossible.

In the third example Tenten put all her shurikens onto the showcase, after which a customer came in and bought a shuriken with price $2$. This is impossible since the shuriken was not the cheapest, we know that the $1$-ryo shuriken was also there.

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