vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Candy Boxes

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There is an old tradition of keeping 4 boxes of candies in the house in Cyberland. The numbers of candies are special if their arithmetic mean, their median and their range are all equal. By definition, for a set {*x*1,<=*x*2,<=*x*3,<=*x*4} (*x*1<=≤<=*x*2<=≤<=*x*3<=≤<=*x*4) arithmetic mean is , median is  and range is *x*4<=-<=*x*1. The arithmetic mean and median are not necessary integer. It is well-known that if those three numbers are same, boxes will create a "debugging field" and codes in the field will have no bugs.

For example, 1,<=1,<=3,<=3 is the example of 4 numbers meeting the condition because their mean, median and range are all equal to 2.

Jeff has 4 special boxes of candies. However, something bad has happened! Some of the boxes could have been lost and now there are only *n* (0<=≤<=*n*<=≤<=4) boxes remaining. The *i*-th remaining box contains *a**i* candies.

Now Jeff wants to know: is there a possible way to find the number of candies of the 4<=-<=*n* missing boxes, meeting the condition above (the mean, median and range are equal)?

Input Specification:
The first line of input contains an only integer *n* (0<=≤<=*n*<=≤<=4).

The next *n* lines contain integers *a**i*, denoting the number of candies in the *i*-th box (1<=≤<=*a**i*<=≤<=500).

Output Specification:
In the first output line, print "YES" if a solution exists, or print "NO" if there is no solution.

If a solution exists, you should output 4<=-<=*n* more lines, each line containing an integer *b*, denoting the number of candies in a missing box.

All your numbers *b* must satisfy inequality 1<=≤<=*b*<=≤<=106. It is guaranteed that if there exists a positive integer solution, you can always find such *b*'s meeting the condition. If there are multiple answers, you are allowed to print any of them.

Given numbers *a**i* may follow in any order in the input, not necessary in non-decreasing.

*a**i* may have stood at any positions in the original set, not necessary on lowest *n* first positions.

Demo Input:
['2\n1\n1\n', '3\n1\n1\n1\n', '4\n1\n2\n2\n3\n']

Demo Output:
['YES\n3\n3\n', 'NO\n', 'YES\n']

Note:
For the first sample, the numbers of candies in 4 boxes can be 1, 1, 3, 3. The arithmetic mean, the median and the range of them are all 2.

For the second sample, it's impossible to find the missing number of candies.

In the third example no box has been lost and numbers satisfy the condition.

You may output *b* in any order.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have to create a function which receives 3 arguments: 2 numbers, and the result of an unknown operation performed on them (also a number).

Based on those 3 values you have to return a string, that describes which operation was used to get the given result.

The possible return strings are:
  `"addition"`,
  `"subtraction"`,
  `"multiplication"`,
  `"division"`.

## Example:
```
calcType(1, 2, 3) -->   1 ? 2 = 3   --> "addition"
```

## Notes
* In case of division you should expect that the result of the operation is obtained by using `/` operator on the input values - no manual data type conversion or rounding should be performed.
* Cases with just one possible answers are generated.
* Only valid arguments will be passed to the function.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ever the learned traveller, Alan Partridge has pretty strong views on London:

```
"Go to London. I guarantee you'll either be mugged or not appreciated.
Catch the train to London, stopping at Rejection, Disappointment, Backstabbing Central and Shattered Dreams Parkway."
```
Your job is to check that the provided list of stations contains all of the stops Alan mentions. There will be other stations in the array.  Example:

```
['Rejection', 'Disappointment', 'Backstabbing Central', 'Shattered Dreams Parkway']
```

If the stations all appear, return 'Smell my cheese you mother!', if not,  return 'No, seriously, run. You will miss it.'.

Other katas in this series:
Alan Partridge I - Partridge Watch
Alan Partridge II - Apple Turnover

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are quite a lot of ways to have fun with inflatable balloons. For example, you can fill them with water and see what happens.

Grigory and Andrew have the same opinion. So, once upon a time, they went to the shop and bought n packets with inflatable balloons, where i-th of them has exactly a_i balloons inside.

They want to divide the balloons among themselves. In addition, there are several conditions to hold:

  * Do not rip the packets (both Grigory and Andrew should get unbroken packets); 
  * Distribute all packets (every packet should be given to someone); 
  * Give both Grigory and Andrew at least one packet; 
  * To provide more fun, the total number of balloons in Grigory's packets should not be equal to the total number of balloons in Andrew's packets. 



Help them to divide the balloons or determine that it's impossible under these conditions.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 10) — the number of packets with balloons.

The second line contains n integers: a_1, a_2, …, a_n (1 ≤ a_i ≤ 1000) — the number of balloons inside the corresponding packet.

Output

If it's impossible to divide the balloons satisfying the conditions above, print -1.

Otherwise, print an integer k — the number of packets to give to Grigory followed by k distinct integers from 1 to n — the indices of those. The order of packets doesn't matter.

If there are multiple ways to divide balloons, output any of them.

Examples

Input

3
1 2 1


Output

2
1 2


Input

2
5 5


Output

-1


Input

1
10


Output

-1

Note

In the first test Grigory gets 3 balloons in total while Andrey gets 1.

In the second test there's only one way to divide the packets which leads to equal numbers of balloons.

In the third test one of the boys won't get a packet at all.

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

A great deal of energy is lost as metabolic heat when the organisms from one trophic level are consumed by the next level. 

Suppose in Chefland the energy reduces by a factor of K, i.e, if initially, the energy is X, then the transfer of energy to the next tropic level is \lfloor \frac{X} {K} \rfloor. This limits the length of foodchain which is defined to be the highest level receiving non-zero energy.

E is the energy at the lowest tropic level. Given E and K for an ecosystem, find the maximum length of foodchain.

Note: \lfloor x \rfloor denoted the floor function, and it returns the greatest integer that is less than or equal to x (i.e  rounds down to the nearest integer). For example, \lfloor 1.4 \rfloor = 1, \lfloor 5 \rfloor = 5, \lfloor -1.5 \rfloor = -2, \lfloor -3 \rfloor = -3 , \lfloor 0 \rfloor = 0.

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains a single line of input, two integers E, K.

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

For each testcase, output in a single line answer to the problem.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ E ≤ 10^{9}$
$2 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
3
5 3
6 7
10 2

----- Sample Output 1 ------ 
2
1
4
----- explanation 1 ------ 
TestCase $1$: The energy at first level is $5$ units. For the second level energy becomes $\lfloor \frac{5} {3} \rfloor = 1$ units. So the length of foodchain is $2$ since from the next level onwards $0$ units of energy will be received.

TestCase $3$: The energy at different levels is:
- Level $1$- $10$ units
- Level $2$- $\lfloor \frac{10} {2} \rfloor = 5$ units
- Level $3$- $\lfloor \frac{5} {2} \rfloor = 2$ units
- Level $4$- $\lfloor \frac{2} {2} \rfloor = 1$ units
- Level $5$- $\lfloor \frac{1} {2} \rfloor = 0$ units

So the answer is $4$, since it is the last level to receive non-zero energy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dezider is making a game board for the game of Convexity. He drilled a bunch of holes in a piece of wood. As the name of the game suggests the holes were on the boundary of a convex polygon. After turning over the piece of wood, Dezider froze—he had damaged the famous Picasso lithograph—The Bull No. 8. Now the question is: how to fix the damage? Drawing a bunch of straight lines to cover the holes seems like a good repair method but, of course, Dezider would like to draw as few lines as possible. He needs your help. Write a program that, given the positions of the holes, finds the smallest number of straight lines that can cover the holes.

-----Input-----
The only input line starts with $n$, the number of holes. Then $2n$ numbers, the coordinates of the holes, follow. You can assume that $3 \leq n \leq 1000$ and the coordinates are integers between $-1000000$ and $1000000$. The holes lie on the boundary of a convex polygon.

-----Output-----
The output contains one line with the smallest number $\ell $, such that $\ell $ straight lines can cover the holes.

-----Examples-----
Sample Input:
4 0 0 1 1 1 0 0 1
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an easier version of the problem. In this version, n ≤ 2000.

There are n distinct points in three-dimensional space numbered from 1 to n. The i-th point has coordinates (x_i, y_i, z_i). The number of points n is even.

You'd like to remove all n points using a sequence of n/2 snaps. In one snap, you can remove any two points a and b that have not been removed yet and form a perfectly balanced pair. A pair of points a and b is perfectly balanced if no other point c (that has not been removed yet) lies within the axis-aligned minimum bounding box of points a and b.

Formally, point c lies within the axis-aligned minimum bounding box of points a and b if and only if min(x_a, x_b) ≤ x_c ≤ max(x_a, x_b), min(y_a, y_b) ≤ y_c ≤ max(y_a, y_b), and min(z_a, z_b) ≤ z_c ≤ max(z_a, z_b). Note that the bounding box might be degenerate. 

Find a way to remove all points in n/2 snaps.

Input

The first line contains a single integer n (2 ≤ n ≤ 2000; n is even), denoting the number of points.

Each of the next n lines contains three integers x_i, y_i, z_i (-10^8 ≤ x_i, y_i, z_i ≤ 10^8), denoting the coordinates of the i-th point.

No two points coincide.

Output

Output n/2 pairs of integers a_i, b_i (1 ≤ a_i, b_i ≤ n), denoting the indices of points removed on snap i. Every integer between 1 and n, inclusive, must appear in your output exactly once.

We can show that it is always possible to remove all points. If there are many solutions, output any of them.

Examples

Input


6
3 1 0
0 3 0
2 2 0
1 0 0
1 3 0
0 1 0


Output


3 6
5 1
2 4


Input


8
0 1 1
1 0 1
1 1 0
1 1 1
2 2 2
3 2 2
2 3 2
2 2 3


Output


4 5
1 6
2 7
3 8

Note

In the first example, here is what points and their corresponding bounding boxes look like (drawn in two dimensions for simplicity, as all points lie on z = 0 plane). Note that order of removing matters: for example, points 5 and 1 don't form a perfectly balanced pair initially, but they do after point 3 is removed. 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Top-model Izabella participates in the competition. She wants to impress judges and show her mathematical skills.

Her problem is following: for given string, consisting of only 0 and 1, tell if it's possible to remove some digits in such a way, that remaining number is a representation of some positive integer, divisible by 64, in the binary numerical system.


-----Input-----

In the only line given a non-empty binary string s with length up to 100.


-----Output-----

Print «yes» (without quotes) if it's possible to remove digits required way and «no» otherwise.


-----Examples-----
Input
100010001

Output
yes
Input
100

Output
no


-----Note-----

In the first test case, you can get string 1 000 000 after removing two ones which is a representation of number 64 in the binary numerical system.

You can read more about binary numeral system representation here: https://en.wikipedia.org/wiki/Binary_system

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Statement
There are two integers A and B. You are required to compute the bitwise AND amongst all natural numbers lying between A and B, both inclusive.

Input Format

First line of the input contains T, the number of testcases to follow.
Each testcase in a newline contains A and B separated by a single space.

Constraints

1≤T≤200

0≤A≤B<2^32

Output Format

Output one line per test case with the required bitwise AND.

SAMPLE INPUT
3 
12 15 
2 3 
8 13

SAMPLE OUTPUT
12 
2 
8

Explanation

1st Test Case : 12 & 13 & 14 & 15 = 12

2nd Test Case : 2 & 3 = 2

3rd Test Case : 8 & 9 & 10 & 11 & 12 & 13 = 8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As we all know, F.C. Barcelona is the best soccer team of our era! Their entangling and mesmerizing game style usually translates into very high ball possession, consecutive counter-attack plays and goals. Lots of goals, thanks to the natural talent of their attacker and best player in history, Lionel Andres Messi.
However, at the most prestigious tournament of individual teams, the UEFA Champions League, there are no guarantees and believe it or not, Barcelona is in trouble.... They are tied versus Chelsea, which is a very defending team that usually relies on counter-strike to catch opposing teams off guard and we are in the last minute of the match. So Messi decided to settle things down for good and now he is conducting the ball on his teams' midfield and he will start a lethal counter-attack :D
After dribbling the 2 strikers from Chelsea, he now finds himself near the center of the field and he won't be able to dribble the entire team on his own, so he will need to pass the ball to one of his teammates, run forward and receive the ball once again to score the final goal.
Exactly K players are with him on his counter-attack and the coach, Tito Villanova knows that this counter-attack will end in a goal only if after exactly N passes are performed between the players, Messi ends up with the ball.
(Note that the ball only needs to end with Messi after exactly N passes are performed between all the K+1 players, i.e. Messi can receive the ball several times during the N passes. See the 2nd test case explanation for further clarification. ) 
However, he realized that there are many scenarios possible for this, so he asked you, his assistant coach, to tell him in how many ways can Messi score the important victory goal. So help him!!

-----Input-----
Input will contain a number T denoting the number of test cases.
Then T test cases follow, each one consisting of two space-sparated integers N and K.

-----Output-----
For each test case, output a single integer, the number of ways the winning play might happen modulo 1000000007 (109+7).

-----Constraints-----

- 1 ≤ T ≤ 100
- 2 ≤ N ≤ 1000
- 1 ≤ K ≤ 10

-----Example-----
Input:
2
2 4
4 2

Output:
4
6

-----Explanation-----
In the first test case, say four players with Messi are Xavi, Busquets, Iniesta and Jordi Alba. Then the ways of the winning play to happen when exactly  2 passes are to be performed are:
1) Messi - Xavi - Messi
2) Messi - Busquets - Messi
3) Messi - Iniesta - Messi
4) Messi - Alba - Messi

In the second test case, also say that two players with Messi are Xavi and Iniesta. There are 6 ways for the winning play to happen when exactly 4 passes are performed. All the examples of such winning play are:
1) Messi - Xavi - Messi - Iniesta - Messi
2) Messi - Xavi - Iniesta - Xavi - Messi
3) Messi - Xavi - Messi - Xavi - Messi
4) Messi - Iniesta - Messi - Iniesta - Messi
5) Messi - Iniesta - Messi - Xavi - Messi
6) Messi - Iniesta - Xavi - Iniesta - Messi

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a stone-chiseler in Ancient Greece, charged with copying the text from famous monuments onto new stones. The existing inscriptions use boustrophedon writing, in which the lines of text alternate direction, and if a line ends in the middle of a word, the word simply continues on the next line. For example, an inscription may look like this:

IN.HONOR.OF.THE.INTERNAT
TEPMOC.GNIMMARGORP.LANOI
ITION

(In the original boustrophedon style, no spaces or punctuation were used between words, but here we have introduced periods between words.)

Today, however, you have been asked to copy these over into the new-fangled style where each line runs left to right, and words will not be split across lines — if there is not room for a whole word on a particular line, it will be started on the next line. So, the inscription above might instead look like this:

IN.HONOR.OF.THE
INTERNATIONAL
PROGRAMMING.COMPETITION

Of course, before you get started, you will need to know what size of stone will be required for your inscription. The width of the stone will be given, and the length for you to determine.

-----Input-----
The first line of the input will consist of three numbers, $n$, the number of lines in the original inscription, $d$, the width of the original inscription, and $w$, the width of your new stone in characters. Then, $n$ lines follow containing the original inscription written in boustrophedon style. You may assume that the first $n-1$ such lines consist only of capital letters and periods, with the $n$-th line also possibly containing spaces. You may assume that no two periods appear consecutively, that $1\leq n \leq 100000$, $1\leq d\leq 100$, $1\leq w\leq 100$, and that no word is more than $w$ letters long.

-----Output-----
The output should consist of a single integer, representing the number of lines required to write the inscription when writing left to right and not splitting words across lines.

-----Examples-----
Sample Input 1:
3 24 24
IN.HONOR.OF.THE.INTERNAT
TEPMOC.GNIMMARGORP.LANOI
ITION
Sample Output 1:
3

Sample Input 2:
3 24 20
IN.HONOR.OF.THE.INTERNAT
TEPMOC.GNIMMARGORP.LANOI
ITION
Sample Output 2:
4

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Vasya painted a Cartesian coordinate system on a piece of paper and marked some set of points (*x*1,<=*y*1),<=(*x*2,<=*y*2),<=...,<=(*x**n*,<=*y**n*). Let's define neighbors for some fixed point from the given set (*x*,<=*y*): 
 -  point (*x*',<=*y*') is (*x*,<=*y*)'s right neighbor, if *x*'<=&gt;<=*x* and *y*'<==<=*y* -  point (*x*',<=*y*') is (*x*,<=*y*)'s left neighbor, if *x*'<=&lt;<=*x* and *y*'<==<=*y* -  point (*x*',<=*y*') is (*x*,<=*y*)'s lower neighbor, if *x*'<==<=*x* and *y*'<=&lt;<=*y* -  point (*x*',<=*y*') is (*x*,<=*y*)'s upper neighbor, if *x*'<==<=*x* and *y*'<=&gt;<=*y* 
We'll consider point (*x*,<=*y*) from the given set supercentral, if it has at least one upper, at least one lower, at least one left and at least one right neighbor among this set's points.

Vasya marked quite many points on the paper. Analyzing the picture manually is rather a challenge, so Vasya asked you to help him. Your task is to find the number of supercentral points in the given set.

Input Specification:
The first input line contains the only integer *n* (1<=≤<=*n*<=≤<=200) — the number of points in the given set. Next *n* lines contain the coordinates of the points written as "*x* *y*" (without the quotes) (|*x*|,<=|*y*|<=≤<=1000), all coordinates are integers. The numbers in the line are separated by exactly one space. It is guaranteed that all points are different.

Output Specification:
Print the only number — the number of supercentral points of the given set.

Demo Input:
['8\n1 1\n4 2\n3 1\n1 2\n0 2\n0 1\n1 0\n1 3\n', '5\n0 0\n0 1\n1 0\n0 -1\n-1 0\n']

Demo Output:
['2\n', '1\n']

Note:
In the first sample the supercentral points are only points (1, 1) and (1, 2).

In the second sample there is one supercental point — point (0, 0).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Timofey likes integers a lot. Unfortunately, he is very young and can't work with very big integers, so he does all the operations modulo his favorite prime m. Also, Timofey likes to look for arithmetical progressions everywhere.

One of his birthday presents was a sequence of distinct integers a1, a2, ..., an. Timofey wants to know whether he can rearrange the elements of the sequence so that is will be an arithmetical progression modulo m, or not.

Arithmetical progression modulo m of length n with first element x and difference d is sequence of integers x, x + d, x + 2d, ..., x + (n - 1)·d, each taken modulo m.

Input

The first line contains two integers m and n (2 ≤ m ≤ 109 + 7, 1 ≤ n ≤ 105, m is prime) — Timofey's favorite prime module and the length of the sequence.

The second line contains n distinct integers a1, a2, ..., an (0 ≤ ai < m) — the elements of the sequence.

Output

Print -1 if it is not possible to rearrange the elements of the sequence so that is will be an arithmetical progression modulo m.

Otherwise, print two integers — the first element of the obtained progression x (0 ≤ x < m) and its difference d (0 ≤ d < m).

If there are multiple answers, print any of them.

Examples

Input

17 5
0 2 4 13 15


Output

13 2


Input

17 5
0 2 4 13 14


Output

-1


Input

5 3
1 2 3


Output

3 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For Diwali, Chef arranges all $K$ laddus in a row in his sweet shop. Whenever a customer comes to buy laddus, chef follows a rule that each customer must buy all laddus on odd position. After the selection of the laddu, a new row is formed, and again out of these only laddus on odd position are selected. This continues until the chef left with the last laddu. Find out the position of that last laddu in the original row.

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

-----Output:-----
For each testcase, print the position of that laddu who is left, in the original row.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq K \leq 10^5$

-----Sample Input:-----
3
1
5
8

-----Sample Output:-----
1
4
8

-----EXPLANATION:-----
For 1) Only one laddu which is last so print 1.
For 2) Customer 1: [1, 3, 5]
New row = [2, 4]

Customer 2: [2]

Last laddu = 4

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