vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Vitya is studying in the third grade. During the last math lesson all the pupils wrote on arithmetic quiz. Vitya is a clever boy, so he managed to finish all the tasks pretty fast and Oksana Fillipovna gave him a new one, that is much harder.

Let's denote a flip operation of an integer as follows: number is considered in decimal notation and then reverted. If there are any leading zeroes afterwards, they are thrown away. For example, if we flip 123 the result is the integer 321, but flipping 130 we obtain 31, and by flipping 31 we come to 13.

Oksana Fillipovna picked some number a without leading zeroes, and flipped it to get number ar. Then she summed a and ar, and told Vitya the resulting value n. His goal is to find any valid a.

As Oksana Fillipovna picked some small integers as a and ar, Vitya managed to find the answer pretty fast and became interested in finding some general algorithm to deal with this problem. Now, he wants you to write the program that for given n finds any a without leading zeroes, such that a + ar = n or determine that such a doesn't exist.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 10100 000).

Output

If there is no such positive integer a without leading zeroes that a + ar = n then print 0. Otherwise, print any valid a. If there are many possible answers, you are allowed to pick any.

Examples

Input

4


Output

2


Input

11


Output

10


Input

5


Output

0


Input

33


Output

21

Note

In the first sample 4 = 2 + 2, a = 2 is the only possibility.

In the second sample 11 = 10 + 1, a = 10 — the only valid solution. Note, that a = 01 is incorrect, because a can't have leading zeroes.

It's easy to check that there is no suitable a in the third sample.

In the fourth sample 33 = 30 + 3 = 12 + 21, so there are three possibilities for a: a = 30, a = 12, a = 21. Any of these is considered to be correct answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.


Note:
You may assume the greed factor is always positive. 
You cannot assign more than one cookie to one child.


Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.



Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities in Westeros. The i-th city is inhabited by a_{i} people. Daenerys and Stannis play the following game: in one single move, a player chooses a certain town and burns it to the ground. Thus all its residents, sadly, die. Stannis starts the game. The game ends when Westeros has exactly k cities left.

The prophecy says that if the total number of surviving residents is even, then Daenerys wins: Stannis gets beheaded, and Daenerys rises on the Iron Throne. If the total number of surviving residents is odd, Stannis wins and everything goes in the completely opposite way.

Lord Petyr Baelish wants to know which candidates to the throne he should support, and therefore he wonders, which one of them has a winning strategy. Answer to this question of Lord Baelish and maybe you will become the next Lord of Harrenholl.


-----Input-----

The first line contains two positive space-separated integers, n and k (1 ≤ k ≤ n ≤ 2·10^5) — the initial number of cities in Westeros and the number of cities at which the game ends. 

The second line contains n space-separated positive integers a_{i} (1 ≤ a_{i} ≤ 10^6), which represent the population of each city in Westeros.


-----Output-----

Print string "Daenerys" (without the quotes), if Daenerys wins and "Stannis" (without the quotes), if Stannis wins.


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

Output
Stannis

Input
3 1
2 2 1

Output
Daenerys

Input
6 3
5 20 12 7 14 101

Output
Stannis



-----Note-----

In the first sample Stannis will use his move to burn a city with two people and Daenerys will be forced to burn a city with one resident. The only survivor city will have one resident left, that is, the total sum is odd, and thus Stannis wins.

In the second sample, if Stannis burns a city with two people, Daenerys burns the city with one resident, or vice versa. In any case, the last remaining city will be inhabited by two people, that is, the total sum is even, and hence Daenerys wins.

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

There are N vacant lots on the two-dimensional plane. Numbers from 1 to N are assigned to each vacant lot. Every vacant lot is so small that it can be considered a point. The i-th vacant lot exists at (xi, yi).

Taro chose just K from these N vacant lots and decided to build a building in those vacant lots. However, I thought it would be uninteresting to build multiple buildings too close together, so Taro decided to choose a vacant lot so that the Euclidean distance between each vacant lot would always be 2 or more.

Create a program that outputs possible combinations of vacant lots that Taro chooses. If there are multiple combinations, output the smallest one in lexicographical order. However, no matter how you choose K vacant lots, if the Euclidean distance of any two vacant lots is less than 2, output -1 instead.

Constraints

The input satisfies the following conditions.

* All inputs are integers.
* 2 ≤ K ≤ N ≤ 6,000
* 1 ≤ xi, yi ≤ 1,000,000 (1 ≤ i ≤ N)
* xi mod 2 = floor (yi ÷ 2) mod 2 (1 ≤ i ≤ N)
(Here, floor (yi ÷ 2) is the value obtained by dividing yi by 2 and rounding down to the nearest whole number.)
* There can be no more than one vacant lot at the same coordinates.

Input

The input is given in the following format.


N K
x1 y1
x2 y2
...
xN yN


Output

Output the vacant lot numbers selected by Taro line by line in ascending order.

Examples

Input

3 2
2 1
1 2
1 3


Output

1
3


Input

4 3
2 1
1 2
1 3
2 4


Output

-1


Input

5 3
5 7
5 6
6 8
20 20
4 8


Output

2
3
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata, your task is to write a function `to_bytes(n)` (or `toBytes(n)` depending on language) that produces a list of bytes that represent a given non-negative integer `n`. Each byte in the list is represented by a string of `'0'` and `'1'` of length 8. The most significant byte is first in the list. The example test cases should provide you with all the details. You may assume that the argument `n` is valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Of course our child likes walking in a zoo. The zoo has n areas, that are numbered from 1 to n. The i-th area contains a_{i} animals in it. Also there are m roads in the zoo, and each road connects two distinct areas. Naturally the zoo is connected, so you can reach any area of the zoo from any other area using the roads.

Our child is very smart. Imagine the child want to go from area p to area q. Firstly he considers all the simple routes from p to q. For each route the child writes down the number, that is equal to the minimum number of animals among the route areas. Let's denote the largest of the written numbers as f(p, q). Finally, the child chooses one of the routes for which he writes down the value f(p, q).

After the child has visited the zoo, he thinks about the question: what is the average value of f(p, q) for all pairs p, q (p ≠ q)? Can you answer his question?


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 10^5; 0 ≤ m ≤ 10^5). The second line contains n integers: a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^5). Then follow m lines, each line contains two integers x_{i} and y_{i} (1 ≤ x_{i}, y_{i} ≤ n; x_{i} ≠ y_{i}), denoting the road between areas x_{i} and y_{i}.

All roads are bidirectional, each pair of areas is connected by at most one road.


-----Output-----

Output a real number — the value of $\frac{\sum_{p, q, p \neq q} f(p, q)}{n(n - 1)}$.

The answer will be considered correct if its relative or absolute error doesn't exceed 10^{ - 4}.


-----Examples-----
Input
4 3
10 20 30 40
1 3
2 3
4 3

Output
16.666667

Input
3 3
10 20 30
1 2
2 3
3 1

Output
13.333333

Input
7 8
40 20 10 30 20 50 40
1 2
2 3
3 4
4 5
5 6
6 7
1 4
5 7

Output
18.571429



-----Note-----

Consider the first sample. There are 12 possible situations:

  p = 1, q = 3, f(p, q) = 10.  p = 2, q = 3, f(p, q) = 20.  p = 4, q = 3, f(p, q) = 30.  p = 1, q = 2, f(p, q) = 10.  p = 2, q = 4, f(p, q) = 20.  p = 4, q = 1, f(p, q) = 10. 

Another 6 cases are symmetrical to the above. The average is $\frac{(10 + 20 + 30 + 10 + 20 + 10) \times 2}{12} \approx 16.666667$.

Consider the second sample. There are 6 possible situations:

  p = 1, q = 2, f(p, q) = 10.  p = 2, q = 3, f(p, q) = 20.  p = 1, q = 3, f(p, q) = 10. 

Another 3 cases are symmetrical to the above. The average is $\frac{(10 + 20 + 10) \times 2}{6} \approx 13.333333$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For given three points p1, p2, p, find the reflection point x of p onto p1p2.

<image>

Constraints

* 1 ≤ q ≤ 1000
* -10000 ≤ xi, yi ≤ 10000
* p1 and p2 are not identical.

Input


xp1 yp1 xp2 yp2
q
xp0 yp0
xp1 yp1
...
xpq−1 ypq−1


In the first line, integer coordinates of p1 and p2 are given. Then, q queries are given for integer coordinates of p.

Output

For each query, print the coordinate of the reflection point x. The output values should be in a decimal fraction with an error less than 0.00000001.

Examples

Input

0 0 2 0
3
-1 1
0 1
1 1


Output

-1.0000000000 -1.0000000000
0.0000000000 -1.0000000000
1.0000000000 -1.0000000000


Input

0 0 3 4
3
2 5
1 4
0 3


Output

4.2400000000 3.3200000000
3.5600000000 2.0800000000
2.8800000000 0.8400000000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
"Hey, it's homework time" — thought Polycarpus and of course he started with his favourite subject, IT. Polycarpus managed to solve all tasks but for the last one in 20 minutes. However, as he failed to solve the last task after some considerable time, the boy asked you to help him.

The sequence of *n* integers is called a permutation if it contains all integers from 1 to *n* exactly once.

You are given an arbitrary sequence *a*1,<=*a*2,<=...,<=*a**n* containing *n* integers. Each integer is not less than 1 and not greater than 5000. Determine what minimum number of elements Polycarpus needs to change to get a permutation (he should not delete or add numbers). In a single change he can modify any single sequence element (i. e. replace it with another integer).

Input Specification:
The first line of the input data contains an integer *n* (1<=≤<=*n*<=≤<=5000) which represents how many numbers are in the sequence. The second line contains a sequence of integers *a**i* (1<=≤<=*a**i*<=≤<=5000,<=1<=≤<=*i*<=≤<=*n*).

Output Specification:
Print the only number — the minimum number of changes needed to get the permutation.

Demo Input:
['3\n3 1 2\n', '2\n2 2\n', '5\n5 3 3 3 1\n']

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

Note:
The first sample contains the permutation, which is why no replacements are required.

In the second sample it is enough to replace the first element with the number 1 and that will make the sequence the needed permutation.

In the third sample we can replace the second element with number 4 and the fourth element with number 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vitaly has an array of n distinct integers. Vitaly wants to divide this array into three non-empty sets so as the following conditions hold: 

  1. The product of all numbers in the first set is less than zero ( < 0). 
  2. The product of all numbers in the second set is greater than zero ( > 0). 
  3. The product of all numbers in the third set is equal to zero. 
  4. Each number from the initial array must occur in exactly one set. 



Help Vitaly. Divide the given array.

Input

The first line of the input contains integer n (3 ≤ n ≤ 100). The second line contains n space-separated distinct integers a1, a2, ..., an (|ai| ≤ 103) — the array elements.

Output

In the first line print integer n1 (n1 > 0) — the number of elements in the first set. Then print n1 numbers — the elements that got to the first set.

In the next line print integer n2 (n2 > 0) — the number of elements in the second set. Then print n2 numbers — the elements that got to the second set.

In the next line print integer n3 (n3 > 0) — the number of elements in the third set. Then print n3 numbers — the elements that got to the third set.

The printed sets must meet the described conditions. It is guaranteed that the solution exists. If there are several solutions, you are allowed to print any of them.

Examples

Input

3
-1 2 0


Output

1 -1
1 2
1 0


Input

4
-1 -2 -3 0


Output

1 -1
2 -3 -2
1 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Penny has an array of $n$ integers, $[a_0,a_1,\ldots,a_{n-1}]$. She wants to find the number of unique multisets she can form using elements from the array such that the bitwise XOR of all the elements of the multiset is a prime number. Recall that a multiset is a set which can contain duplicate elements.

Given $\textit{q}$ queries where each query consists of an array of integers, can you help Penny find and print the number of valid multisets for each array? As these values can be quite large, modulo each answer by $10^9+7$ before printing it on a new line.

Input Format

The first line contains a single integer, $\textit{q}$, denoting the number of queries. The $2\cdot q$ subsequent lines describe each query in the following format:

The first line contains a single integer, $n$, denoting the number of integers in the array.
The second line contains $n$ space-separated integers describing the respective values of $a_0,a_1,\ldots,a_{n-1}$.

Constraints

$1\leq q\leq10$  
$1\leq n\leq1000000$
$3500\leq a_i\leq4500$

Output Format

On a new line for each query, print a single integer denoting the number of unique multisets Penny can construct using numbers from the array such that the bitwise XOR of all the multiset's elements is prime. As this value is quite large, your answer must be modulo $10^9+7$.

Sample Input
1   
3   
3511 3671 4153  

Sample Output
4

Explanation

The valid multisets are:

$\{3511\}\rightarrow3511$ is prime.
$\{3671\}\to3671$ is prime.
$\{4153\}\rightarrow4153$ is prime.
$\{3511,3671,4153\}\to3511\oplus3671\oplus4153\text{=5081}$, which is prime.

Because there are four valid multisets, we print the value of $4\%(10^9+7)=4$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a peculiar functioning setup.
Two Tanks are separated from each other by a wall .There is a pipe in the wall which connects  both tanks  which allows flow of water between them . Due to this ,there is change in temperature of both tanks , every minute temperature of Tank with larger temperature among two decreases by one and temperature of Tank  with smaller temperature among two increases by two until equilibrium is reached , But there is a problem .
The pipe can't control this flow of water if there is Non-equilibrium (inequality of temperature  on  both sides )  even after $m$ minutes and the pipe will burst after it , your task is to predict whether the pipe will burst or not .
Note: If equilibrium cannot be reached the process will continue forever.
The initial temperature of Cold Tank is $Tc$ , of Hot Tank it is $Th$. 

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, three  integers $m, Tc,Th$. 

-----Output:-----
For each testcase, output in a single line answer "Yes" if Pipe will burst after m minutes "No" if pipe will not burst.

-----Constraints-----
- $1 \leq T \leq 100000$
- $1 \leq m,Tc,Th \leq 10^9$
- $Tc \leq Th $

-----Sample Input:-----
2
4 5 10
2 2 5

-----Sample Output:-----
Yes
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an `x` and `y` find the smallest and greatest numbers **above** and **below** a given `n` that are divisible by both `x` and `y`.

### Examples
```python
greatest(2, 3, 20) => 18   # 18 is the greatest number under 20 that is divisible by both 2 and 3
smallest(2, 3, 20) => 24   # 24 is the smallest number above 20 that is divisible by both 2 and 3

greatest(5, 15, 100) => 90
smallest(5, 15, 100) => 105

greatest(123, 456, 789) => 0   # there are no numbers under 789 that are divisible by both 123 and 456
smallest(123, 456, 789) => 18696
```

**Notes:** 

1. you should never return `n` even if it is divisible by `x` and `y` always the number above or below it
2. `greatest` should return 0 if there are no numbers under `n` that are divisible by both `x` and `y`
3. and all arguments will be valid (integers greater than 0).

### Note for Haskell users

>Please take a look at [bkaes comment](http://www.codewars.com/kata/when-greatest-is-less-than-smallest/discuss#56418f0fbf1f44834d000050) and give us your opinion

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The USA Construction Operation (USACO) recently ordered Farmer John to arrange a row of $n$ haybale piles on the farm. The $i$-th pile contains $a_i$ haybales. 

However, Farmer John has just left for vacation, leaving Bessie all on her own. Every day, Bessie the naughty cow can choose to move one haybale in any pile to an adjacent pile. Formally, in one day she can choose any two indices $i$ and $j$ ($1 \le i, j \le n$) such that $|i-j|=1$ and $a_i>0$ and apply $a_i = a_i - 1$, $a_j = a_j + 1$. She may also decide to not do anything on some days because she is lazy.

Bessie wants to maximize the number of haybales in pile $1$ (i.e. to maximize $a_1$), and she only has $d$ days to do so before Farmer John returns. Help her find the maximum number of haybales that may be in pile $1$ if she acts optimally!


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 100$)  — the number of test cases. Next $2t$ lines contain a description of test cases  — two lines per test case.

The first line of each test case contains integers $n$ and $d$ ($1 \le n,d \le 100$) — the number of haybale piles and the number of days, respectively. 

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 100$)  — the number of haybales in each pile.


-----Output-----

For each test case, output one integer: the maximum number of haybales that may be in pile $1$ after $d$ days if Bessie acts optimally.


-----Example-----
Input
3
4 5
1 0 3 2
2 2
100 1
1 8
0

Output
3
101
0



-----Note-----

In the first test case of the sample, this is one possible way Bessie can end up with $3$ haybales in pile $1$:   On day one, move a haybale from pile $3$ to pile $2$  On day two, move a haybale from pile $3$ to pile $2$  On day three, move a haybale from pile $2$ to pile $1$  On day four, move a haybale from pile $2$ to pile $1$  On day five, do nothing  

In the second test case of the sample, Bessie can do nothing on the first day and move a haybale from pile $2$ to pile $1$ on the second day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anna is a girl so brave that she is loved by everyone in the city and citizens love her cookies. She is planning to hold a party with cookies. Now she has $a$ vanilla cookies and $b$ chocolate cookies for the party.

She invited $n$ guests of the first type and $m$ guests of the second type to the party. They will come to the party in some order. After coming to the party, each guest will choose the type of cookie (vanilla or chocolate) to eat. There is a difference in the way how they choose that type:

If there are $v$ vanilla cookies and $c$ chocolate cookies at the moment, when the guest comes, then  if the guest of the first type: if $v>c$ the guest selects a vanilla cookie. Otherwise, the guest selects a chocolate cookie.  if the guest of the second type: if $v>c$ the guest selects a chocolate cookie. Otherwise, the guest selects a vanilla cookie. 

After that:  If there is at least one cookie of the selected type, the guest eats one.  Otherwise (there are no cookies of the selected type), the guest gets angry and returns to home. 

Anna wants to know if there exists some order of guests, such that no one guest gets angry. Your task is to answer her question.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case, the only line contains four integers $a$, $b$, $n$, $m$ ($0 \le a,b,n,m \le 10^{18}, n+m \neq 0$).


-----Output-----

For each test case, print the answer in one line. If there exists at least one valid order, print "Yes". Otherwise, print "No".

You can print each letter in any case (upper or lower).


-----Example-----
Input
6
2 2 1 2
0 100 0 1
12 13 25 1
27 83 14 25
0 0 1 0
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

Output
Yes
No
No
Yes
No
Yes



-----Note-----

In the first test case, let's consider the order $\{1, 2, 2\}$ of types of guests. Then:  The first guest eats a chocolate cookie. After that, there are $2$ vanilla cookies and $1$ chocolate cookie.  The second guest eats a chocolate cookie. After that, there are $2$ vanilla cookies and $0$ chocolate cookies.  The last guest selects a chocolate cookie, but there are no chocolate cookies. So, the guest gets angry. 

So, this order can't be chosen by Anna.

Let's consider the order $\{2, 2, 1\}$ of types of guests. Then:  The first guest eats a vanilla cookie. After that, there is $1$ vanilla cookie and $2$ chocolate cookies.  The second guest eats a vanilla cookie. After that, there are $0$ vanilla cookies and $2$ chocolate cookies.  The last guest eats a chocolate cookie. After that, there are $0$ vanilla cookies and $1$ chocolate cookie. 

So, the answer to this test case is "Yes".

In the fifth test case, it is illustrated, that the number of cookies ($a + b$) can be equal to zero, but the number of guests ($n + m$) can't be equal to zero.

In the sixth test case, be careful about the overflow of $32$-bit integer type.

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