vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Once again, Boris needs the help of Anton in creating a task. This time Anton needs to solve the following problem:

There are two arrays of integers $a$ and $b$ of length $n$. It turned out that array $a$ contains only elements from the set $\{-1, 0, 1\}$.

Anton can perform the following sequence of operations any number of times:  Choose any pair of indexes $(i, j)$ such that $1 \le i < j \le n$. It is possible to choose the same pair $(i, j)$ more than once.   Add $a_i$ to $a_j$. In other words, $j$-th element of the array becomes equal to $a_i + a_j$. 

For example, if you are given array $[1, -1, 0]$, you can transform it only to $[1, -1, -1]$, $[1, 0, 0]$ and $[1, -1, 1]$ by one operation.

Anton wants to predict if it is possible to apply some number (zero or more) of these operations to the array $a$ so that it becomes equal to array $b$. Can you help him?


-----Input-----

Each test contains multiple test cases. 

The first line contains the number of test cases $t$ ($1 \le t \le 10000$). The description of the test cases follows.

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

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-1 \le a_i \le 1$)  — elements of array $a$. There can be duplicates among elements.

The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($-10^9 \le b_i \le 10^9$)  — elements of array $b$. There can be duplicates among elements.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

For each test case, output one line containing "YES" if it's possible to make arrays $a$ and $b$ equal by performing the described operations, or "NO" if it's impossible.

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


-----Example-----
Input
5
3
1 -1 0
1 1 -2
3
0 1 1
0 2 2
2
1 0
1 41
2
-1 0
-1 -41
5
0 1 -1 1 -1
1 1 -1 1 -1

Output
YES
NO
YES
YES
NO



-----Note-----

In the first test-case we can choose $(i, j)=(2, 3)$ twice and after that choose $(i, j)=(1, 2)$ twice too. These operations will transform $[1, -1, 0] \to [1, -1, -2] \to [1, 1, -2]$

In the second test case we can't make equal numbers on the second position.

In the third test case we can choose $(i, j)=(1, 2)$ $41$ times. The same about the fourth test case.

In the last lest case, it is impossible to make array $a$ equal to the array $b$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a circular track of length M consisting of M checkpoints and M bidirectional roads such that each road has a length of 1 unit.

Chef is currently at checkpoint A and wants to reach checkpoint B. Find the minimum length of the road he needs to travel.

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

- First line will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single line of input, three integers A, B, and M - the initial checkpoint, the final checkpoint, and the total number of checkpoints respectively.

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

For each test case, output the minimum length Chef needs to travel.

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

$1 ≤ T ≤ 1000$
$2 ≤ M ≤ 10^{9}$
$1 ≤ A, B ≤ M$
$A \neq B$

----- Sample Input 1 ------ 
4
1 3 100
1 98 100
40 30 50
2 1 2

----- Sample Output 1 ------ 
2
3
10
1

----- explanation 1 ------ 
Test Case $1$: Chef can go from $1$ to $3$ as: $1 \rightarrow 2$ and then $2 \rightarrow 3$. Thus, total length travelled is $2$ units.

Test Case $2$: Chef can go from $1$ to $98$ as: $98 arrow 99 arrow 100 arrow 1$. Thus, minimum distance travelled is $3$ units.

Test Case $3$: Chef can go from $40$ to $30$ as: $30 arrow 31 arrow 32 arrow \dots arrow 39 arrow 40$. Thus, minimum distance travelled is $10$ units.

Test Case $4$: Chef can go from $2$ to $1$ as: $1 arrow 2$. Thus, minimum distance travelled is $1$ unit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
ABCXYZ company has up to 100 employees.
The company decides to create a unique identification number (UID) for each of its employees.
The company has assigned you the task of validating all the randomly generated UIDs.

A valid UID must follow the rules below:

It must contain at least 2 uppercase English alphabet characters.
It must contain at least 3 digits (0-9).
It should only contain alphanumeric characters (a-z, A-Z & 0-9).
No character should repeat.
There must be exactly 10 characters in a valid UID.

=====Input Format=====
The first line contains an integer T, the number of test cases.
The next T lines contains an employee's UID.

=====Output Format=====
For each test case, print 'Valid' if the UID is valid. Otherwise, print 'Invalid', on separate lines. Do not print the quotation marks.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This kata is  blatantly copied from  inspired by This Kata
Welcome

this is the second in the series of the string iterations kata!

Here we go!

---------------------------------------------------------------------------------

We have a string s

Let's say you start with this: "String"

The first thing you do is reverse it: "gnirtS"

Then you will take the string from the 1st position and reverse it again: "gStrin"

Then you will take the string from the 2nd position and reverse it again: "gSnirt"

Then you will take the string from the 3rd position and reverse it again: "gSntri"

Continue this pattern until you have done every single position, and then you will return the string you have created. For this particular string, you would return: 
"gSntir"

now,

The Task:

In this kata, we also have a number x

take that reversal function, and apply it to the string x times.


return the result of the string after applying the reversal function to it x times.

    example where s = "String" and x = 3:

    after 0 iteration  s = "String"
    after 1 iteration  s = "gSntir"
    after 2 iterations s = "rgiStn"
    after 3 iterations s = "nrtgSi"
    
    so you would return "nrtgSi".

 Note 

String lengths may exceed 2 million


x exceeds a billion


be read to optimize



if this is too hard, go here https://www.codewars.com/kata/string-%3E-n-iterations-%3E-string/java

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You’ve been put in charge of an art exhibit from the famous minimalist sculptor J (even his name is minimalist!). J’s work involves the careful layout of vertically dispositioned orthogonal parallelpipeds in a set of tapering obelisks — in other words, he puts smaller boxes on top of larger boxes. His most recent triumph is called “2 by 3’s Decreasing,” in which he has various sets of six boxes arranged in two stacks of three boxes each. One such set is shown below:

J has sent you the art exhibit and it is your job to set up each of the six-box sets at various locations throughout the museum. But when the sculptures arrived at the museum, uncultured barbarians (i.e., delivery men) simply dropped each set of six boxes on the floor, not realizing the aesthetic appeal of their original layout. You need to reconstruct each set of two towers, but you have no idea which box goes on top of the other! All you know is the following: for each set of six, you have the heights of the two towers, and you know that in any tower the largest height box is always on the bottom and the smallest height box is on the top. Armed with this information, you hope to be able to figure out which boxes go together before tomorrow night’s grand opening gala.

-----Input-----
The input consists of eight positive integers. The first six represent the heights of the six boxes. These values will be given in no particular order and no two will be equal.

The last two values (which will never be the same) are the heights of the two towers.

All box heights will be $\leq 100$ and the sum of the box heights will equal the sum of the tower heights.

-----Output-----
Output the heights of the three boxes in the first tower (i.e., the tower specified by the first tower height in the input), then the heights of the three boxes in the second tower. Each set of boxes should be output in order of decreasing height. Each test case will have a unique answer.

-----Examples-----
Sample Input:
12 8 2 4 10 3 25 14
Sample Output:
12 10 3 8 4 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The store sells $n$ beads. The color of each bead is described by a lowercase letter of the English alphabet ("a"–"z"). You want to buy some beads to assemble a necklace from them.

A necklace is a set of beads connected in a circle.

For example, if the store sells beads "a", "b", "c", "a", "c", "c", then you can assemble the following necklaces (these are not all possible options): [Image] 

And the following necklaces cannot be assembled from beads sold in the store: [Image] The first necklace cannot be assembled because it has three beads "a" (of the two available). The second necklace cannot be assembled because it contains a bead "d", which is not sold in the store. 

We call a necklace $k$-beautiful if, when it is turned clockwise by $k$ beads, the necklace remains unchanged. For example, here is a sequence of three turns of a necklace.  [Image]  As you can see, this necklace is, for example, $3$-beautiful, $6$-beautiful, $9$-beautiful, and so on, but it is not $1$-beautiful or $2$-beautiful.

In particular, a necklace of length $1$ is $k$-beautiful for any integer $k$. A necklace that consists of beads of the same color is also beautiful for any $k$.

You are given the integers $n$ and $k$, and also the string $s$ containing $n$ lowercase letters of the English alphabet — each letter defines a bead in the store. You can buy any subset of beads and connect them in any order. Find the maximum length of a $k$-beautiful necklace you can assemble.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases in the test. Then $t$ test cases follow.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n, k \le 2000$).

The second line of each test case contains the string $s$ containing $n$ lowercase English letters — the beads in the store.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2000$.


-----Output-----

Output $t$ answers to the test cases. Each answer is a positive integer — the maximum length of the $k$-beautiful necklace you can assemble.


-----Example-----
Input
6
6 3
abcbac
3 6
aaa
7 1000
abczgyo
5 4
ababa
20 10
aaebdbabdbbddaadaadc
20 5
ecbedececacbcbccbdec

Output
6
3
5
4
15
10



-----Note-----

The first test case is explained in the statement.

In the second test case, a $6$-beautiful necklace can be assembled from all the letters.

In the third test case, a $1000$-beautiful necklace can be assembled, for example, from beads "abzyo".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Is it rated?

Here it is. The Ultimate Question of Competitive Programming, Codeforces, and Everything. And you are here to answer it.

Another Codeforces round has been conducted. No two participants have the same number of points. For each participant, from the top to the bottom of the standings, their rating before and after the round is known.

It's known that if at least one participant's rating has changed, then the round was rated for sure.

It's also known that if the round was rated and a participant with lower rating took a better place in the standings than a participant with higher rating, then at least one round participant's rating has changed.

In this problem, you should not make any other assumptions about the rating system.

Determine if the current round is rated, unrated, or it's impossible to determine whether it is rated of not.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 1000) — the number of round participants.

Each of the next n lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 4126) — the rating of the i-th participant before and after the round, respectively. The participants are listed in order from the top to the bottom of the standings.


-----Output-----

If the round is rated for sure, print "rated". If the round is unrated for sure, print "unrated". If it's impossible to determine whether the round is rated or not, print "maybe".


-----Examples-----
Input
6
3060 3060
2194 2194
2876 2903
2624 2624
3007 2991
2884 2884

Output
rated

Input
4
1500 1500
1300 1300
1200 1200
1400 1400

Output
unrated

Input
5
3123 3123
2777 2777
2246 2246
2246 2246
1699 1699

Output
maybe



-----Note-----

In the first example, the ratings of the participants in the third and fifth places have changed, therefore, the round was rated.

In the second example, no one's rating has changed, but the participant in the second place has lower rating than the participant in the fourth place. Therefore, if the round was rated, someone's rating would've changed for sure.

In the third example, no one's rating has changed, and the participants took places in non-increasing order of their rating. Therefore, it's impossible to determine whether the round is rated or not.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer N.

Find a permutation P = [P_{1}, P_{2}, \ldots, P_{N}] of the integers \{1, 2, \ldots, N\} such that sum of averages of all consecutive triplets is minimized, i.e. 

\sum_{i=1}^{N-2} \frac{P_{i} + P_{i+1} + P_{i+2}}{3}

is minimized.

If multiple permutations are possible, print any of them.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains an integer N, the size of the permutation.

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

For each test case, output on a new line a permutation which satisfies the above conditions.

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

$1 ≤ T ≤ 1000$
$3 ≤ N ≤ 10^{5}$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

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

----- Sample Output 1 ------ 
3 2 1 4
3 2 1
----- explanation 1 ------ 
Test case $1$: The sum is $\frac{P_{1} + P_{2} + P_{3}}{3} + \frac{P_{2} + P_{3} + P_{4}}{3} = \frac{3 + 2 + 1}{3} + \frac{2 + 1 + 4}{3} = 6/3 + 7/3 = 4.333\ldots$ Among all possible permutations of $\{1, 2, 3, 4\}$, this is one of the permutations which provides the minimum result.

Test case $2$: The sum is $\frac{3+2+1}{3} = 6/3 = 2$. Every permutation of size $3$ will have this value, hence it is the minimum possible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A lot of people dream of convertibles (also often called cabriolets). Some of convertibles, however, don't have roof at all, and are vulnerable to rain. This is why Melon Ask, the famous inventor, decided to create a rain protection mechanism for convertibles.

The workplace of the mechanism is a part of plane just above the driver. Its functional part consists of two rails with sliding endpoints of a piece of stretching rope. For the sake of simplicity we can consider this as a pair of parallel segments in a plane with the rope segment, whose endpoints we are free to choose as any points on these rails segments.

<image>

The algorithmic part of the mechanism detects each particular raindrop and predicts when and where it reaches the plane. At this exact moment the rope segment must contain the raindrop point (so the rope adsorbs the raindrop).

You are given the initial position of the rope endpoints and all information about raindrops. You are to choose the minimal possible speed v of the endpoints sliding (both endpoints can slide in any direction along their segments independently of each other) in such a way that it is possible to catch all raindrops moving both endpoints with speed not greater than v, or find out that it's impossible no matter how high the speed is.

Input

The first line contains three integers n, w and h (1 ≤ n ≤ 10^5, 1≤ w, h ≤ 10^3), meaning that there are n raindrops, and two rails are represented as segments connecting (0, 0) and (w, 0) and connecting (0, h) and (w, h).

The second line contains two integers e_1 and e_2, meaning that the initial (that is, at the moment t = 0) positions of the endpoints are (e_1, 0) and (e_2, h) (0≤ e_1, e_2≤ w).

The i-th of the following n lines contains three integers t_i, x_i and y_i (1≤ t_i≤ 10^5, 0≤ x_i ≤ w, 0 < y_i < h) meaning that the i-th raindrop touches the plane at the point (x_i, y_i) at the time moment t_i. It is guaranteed that t_i ≤ t_{i+1} for all valid i.

Output

If it is impossible to catch all raindrops, print -1.

Otherwise, print the least possible maximum speed of the rope endpoints for which it is possible to catch them all. Your answer is considered correct if the absolute or relative error doesn't exceed 10^{-4}.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-4}.

Examples

Input

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


Output

1.0000000019


Input

2 5 5
0 0
2 4 1
3 1 4


Output

2.1428571437


Input

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


Output

-1

Note

That is how one can act in the first sample test:

<image>

Here is the same for the second:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:


Input: [3,2,3]
Output: 3

Example 2:


Input: [2,2,1,1,1,2,2]
Output: 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Piegirl found the red button. You have one last chance to change the inevitable end.

The circuit under the button consists of n nodes, numbered from 0 to n - 1. In order to deactivate the button, the n nodes must be disarmed in a particular order. Node 0 must be disarmed first. After disarming node i, the next node to be disarmed must be either node (2·i) modulo n or node (2·i) + 1 modulo n. The last node to be disarmed must be node 0. Node 0 must be disarmed twice, but all other nodes must be disarmed exactly once. 

Your task is to find any such order and print it. If there is no such order, print -1.

Input

Input consists of a single integer n (2 ≤ n ≤ 105).

Output

Print an order in which you can to disarm all nodes. If it is impossible, print -1 instead. If there are multiple orders, print any one of them.

Examples

Input

2


Output

0 1 0


Input

3


Output

-1

Input

4


Output

0 1 3 2 0


Input

16


Output

0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mike is trying rock climbing but he is awful at it. 

There are n holds on the wall, i-th hold is at height a_{i} off the ground. Besides, let the sequence a_{i} increase, that is, a_{i} < a_{i} + 1 for all i from 1 to n - 1; we will call such sequence a track. Mike thinks that the track a_1, ..., a_{n} has difficulty $d = \operatorname{max}_{1 \leq i \leq n - 1}(a_{i + 1} - a_{i})$. In other words, difficulty equals the maximum distance between two holds that are adjacent in height.

Today Mike decided to cover the track with holds hanging on heights a_1, ..., a_{n}. To make the problem harder, Mike decided to remove one hold, that is, remove one element of the sequence (for example, if we take the sequence (1, 2, 3, 4, 5) and remove the third element from it, we obtain the sequence (1, 2, 4, 5)). However, as Mike is awful at climbing, he wants the final difficulty (i.e. the maximum difference of heights between adjacent holds after removing the hold) to be as small as possible among all possible options of removing a hold. The first and last holds must stay at their positions.

Help Mike determine the minimum difficulty of the track after removing one hold.


-----Input-----

The first line contains a single integer n (3 ≤ n ≤ 100) — the number of holds.

The next line contains n space-separated integers a_{i} (1 ≤ a_{i} ≤ 1000), where a_{i} is the height where the hold number i hangs. The sequence a_{i} is increasing (i.e. each element except for the first one is strictly larger than the previous one).


-----Output-----

Print a single number — the minimum difficulty of the track after removing a single hold.


-----Examples-----
Input
3
1 4 6

Output
5

Input
5
1 2 3 4 5

Output
2

Input
5
1 2 3 7 8

Output
4



-----Note-----

In the first sample you can remove only the second hold, then the sequence looks like (1, 6), the maximum difference of the neighboring elements equals 5.

In the second test after removing every hold the difficulty equals 2.

In the third test you can obtain sequences (1, 3, 7, 8), (1, 2, 7, 8), (1, 2, 3, 8), for which the difficulty is 4, 5 and 5, respectively. Thus, after removing the second element we obtain the optimal answer — 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke got an integer sequence from his mother, as a birthday present. The sequence has N elements, and the i-th of them is i. Snuke performs the following Q operations on this sequence. The i-th operation, described by a parameter q_i, is as follows:

* Take the first q_i elements from the sequence obtained by concatenating infinitely many copy of the current sequence, then replace the current sequence with those q_i elements.



After these Q operations, find how many times each of the integers 1 through N appears in the final sequence.

Constraints

* 1 ≦ N ≦ 10^5
* 0 ≦ Q ≦ 10^5
* 1 ≦ q_i ≦ 10^{18}
* All input values are integers.

Input

The input is given from Standard Input in the following format:


N Q
q_1
:
q_Q


Output

Print N lines. The i-th line (1 ≦ i ≦ N) should contain the number of times integer i appears in the final sequence after the Q operations.

Examples

Input

5 3
6
4
11


Output

3
3
3
2
0


Input

10 10
9
13
18
8
10
10
9
19
22
27


Output

7
4
4
3
3
2
2
2
0
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have been given an integer array A on size N.
You must report the number of ordered pairs (i,j) such that A[i] & A[j] is zero.
Here '&' denotes the BITWISE AND.
(i,j) and (j,i) are considered different.  

Input
First line contains T-Number of Test cases.
First line of each test contains N. Next line contains N integers - the i'th integer A[i].
Output
Output the number of such pairs for each test case.  

Constraints 
T ≤ 10
N ≤ 100000
A[i] ≤ 1000000

SAMPLE INPUT
1
5
41 47 34 40 29 

SAMPLE OUTPUT
2

Explanation

These are the required pairs
3 5
5 3

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