vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Yurii is sure he can do everything. Can he solve this task, though?

He has an array $a$ consisting of $n$ positive integers. Let's call a subarray $a[l...r]$ good if the following conditions are simultaneously satisfied:   $l+1 \leq r-1$, i. e. the subarray has length at least $3$;  $(a_l \oplus a_r) = (a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1})$, where $\oplus$ denotes the bitwise XOR operation. 

In other words, a subarray is good if the bitwise XOR of the two border elements is equal to the sum of the rest of the elements. 

Yurii wants to calculate the total number of good subarrays. What is it equal to?

An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

The first line contains a single integer $n$ ($3 \leq n \leq 2\cdot 10^5$) — the length of $a$. 

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \lt 2^{30}$) — elements of $a$. 


-----Output-----

Output a single integer — the number of good subarrays. 


-----Examples-----
Input
8
3 1 2 3 1 2 3 15

Output
6
Input
10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854

Output
2


-----Note-----

There are $6$ good subarrays in the example:   $[3,1,2]$ (twice) because $(3 \oplus 2) = 1$;  $[1,2,3]$ (twice) because $(1 \oplus 3) = 2$;  $[2,3,1]$ because $(2 \oplus 1) = 3$;  $[3,1,2,3,1,2,3,15]$ because $(3 \oplus 15) = (1+2+3+1+2+3)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
'In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals' (cited from https://en.wikipedia.org/wiki/Conjunctive_normal_form)

In the other words, CNF is a formula of type <image>, where & represents a logical "AND" (conjunction), <image> represents a logical "OR" (disjunction), and vij are some boolean variables or their negations. Each statement in brackets is called a clause, and vij are called literals.

You are given a CNF containing variables x1, ..., xm and their negations. We know that each variable occurs in at most two clauses (with negation and without negation in total). Your task is to determine whether this CNF is satisfiable, that is, whether there are such values of variables where the CNF value is true. If CNF is satisfiable, then you also need to determine the values of the variables at which the CNF is true. 

It is guaranteed that each variable occurs at most once in each clause.

Input

The first line contains integers n and m (1 ≤ n, m ≤ 2·105) — the number of clauses and the number variables, correspondingly.

Next n lines contain the descriptions of each clause. The i-th line first contains first number ki (ki ≥ 1) — the number of literals in the i-th clauses. Then follow space-separated literals vij (1 ≤ |vij| ≤ m). A literal that corresponds to vij is x|vij| either with negation, if vij is negative, or without negation otherwise.

Output

If CNF is not satisfiable, print a single line "NO" (without the quotes), otherwise print two strings: string "YES" (without the quotes), and then a string of m numbers zero or one — the values of variables in satisfying assignment in the order from x1 to xm.

Examples

Input

2 2
2 1 -2
2 2 -1


Output

YES
11


Input

4 3
1 1
1 2
3 -1 -2 3
1 -3


Output

NO


Input

5 6
2 1 2
3 1 -2 3
4 -3 5 4 6
2 -6 -4
1 5


Output

YES
100010

Note

In the first sample test formula is <image>. One of possible answer is x1 = TRUE, x2 = TRUE.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Analyzing the mistakes people make while typing search queries is a complex and an interesting work. As there is no guaranteed way to determine what the user originally meant by typing some query, we have to use different sorts of heuristics.

Polycarp needed to write a code that could, given two words, check whether they could have been obtained from the same word as a result of typos. Polycarpus suggested that the most common typo is skipping exactly one letter as you type a word.

Implement a program that can, given two distinct words *S* and *T* of the same length *n* determine how many words *W* of length *n*<=+<=1 are there with such property that you can transform *W* into both *S*, and *T* by deleting exactly one character. Words *S* and *T* consist of lowercase English letters. Word *W* also should consist of lowercase English letters.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=100<=000) — the length of words *S* and *T*.

The second line contains word *S*.

The third line contains word *T*.

Words *S* and *T* consist of lowercase English letters. It is guaranteed that *S* and *T* are distinct words.

Output Specification:
Print a single integer — the number of distinct words *W* that can be transformed to *S* and *T* due to a typo.

Demo Input:
['7\nreading\ntrading\n', '5\nsweet\nsheep\n', '3\ntoy\ntry\n']

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

Note:
In the first sample test the two given words could be obtained only from word "treading" (the deleted letters are marked in bold).

In the second sample test the two given words couldn't be obtained from the same word by removing one letter.

In the third sample test the two given words could be obtained from either word "tory" or word "troy".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Omar loves problem solving very much and today he faces the following problem. 

Given a multiset A of N integers {a_1, a_2, \ldots, a_N} and an integer L, his task is to perform L operations indexed from 1 to L in the ascending order of their indices.

Let's consider the operation with index i. Moreover, for i > 1, let p_{max} be a prime number in prime factorization of i with the greatest exponent in the factorization. If there are multiple primes with the greatest exponent in prime factorization of i, let p_{max} be the smallest one among them. The operation with index i is beneficial if and only if i = 1 or the remainder of division p_{max} by i is odd. Otherwise the operation is harmful. 

For example, operation with index i = 2 is harmful, because p_{max} \bmod i = 2 \bmod 2 = 0 which is even. On the other hand, operation with index i = 9 is beneficial, because p_{max} \bmod i = 3 \bmod 9 = 3 which is odd.

Omar must perform all L operations in ascending order of their indices. For each beneficial operation, he has to choose an integer from A and double its value. On the other hand, for each harmful operation, he has to choose an integer from A and divide its value by 2 using integer division. If during any operation any element of A becomes 0, then he removes this element from A. In addition, once A becomes empty, it is not affected by any future operations. In order for the problem to be a challenging one, the task is to maximize the sum of elements in A after performing all the operations.

Since Omar is not familiar with any math, he asks you for help in solving the problem.

Input:

In the first line of the input there are two space separated integers N and L denoting the size of the multiset A and the number of operations to perform. In the second line, there are N space separated integers denoting the elements of A.

Output:

In the first line, print a single integer K denoting the size of multiset A after all operations are performed.
In the second line, print exactly K space separated integers denoting the elements of A after all operations are performed. Print them in the non-decreasing order of their values. Since these values can be very large, print each value taken modulo 10^9+7 (Notice that this modulo operation is applied when the order of these elements is determined and it does not affect this order).

Constraints:

1 ≤ N, L ≤ 5 \cdot 10 ^ 5
1 ≤ a_i ≤ 10 ^ 6     

SAMPLE INPUT
5 4
2 4 5 8 10

SAMPLE OUTPUT
4
2 5 8 20

Explanation

In First Case:  

For Operations from index 1 to 4.  

For index = 1 , we will choose 10 and double it. The array changes to  2 , 4, 5, 8, 20.
For index = 2 , we will choose 2 and make it half. The array changes to  1 , 4, 5, 8, 20.
For index = 3, we will choose 1 and make it half.  The array changes to   4, 5, 8, 20.
For index = 4 , we will choose 4 and make it half. The array changes to  2 , 5, 8, 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A big football championship will occur soon! n teams will compete in it, and each pair of teams will play exactly one game against each other.

There are two possible outcomes of a game:

  * the game may result in a tie, then both teams get 1 point; 
  * one team might win in a game, then the winning team gets 3 points and the losing team gets 0 points. 



The score of a team is the number of points it gained during all games that it played.

You are interested in a hypothetical situation when all teams get the same score at the end of the championship. A simple example of that situation is when all games result in ties, but you want to minimize the number of ties as well.

Your task is to describe a situation (choose the result of each game) so that all teams get the same score, and the number of ties is the minimum possible.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases.

Then the test cases follow. Each test case is described by one line containing one integer n (2 ≤ n ≤ 100) — the number of teams.

Output

For each test case, print (n(n - 1))/(2) integers describing the results of the games in the following order: the first integer should correspond to the match between team 1 and team 2, the second — between team 1 and team 3, then 1 and 4, ..., 1 and n, 2 and 3, 2 and 4, ..., 2 and n, and so on, until the game between the team n - 1 and the team n.

The integer corresponding to the game between the team x and the team y should be 1 if x wins, -1 if y wins, or 0 if the game results in a tie.

All teams should get the same score, and the number of ties should be the minimum possible. If there are multiple optimal answers, print any of them. It can be shown that there always exists a way to make all teams have the same score.

Example

Input


2
2
3


Output


0 
1 -1 1 

Note

In the first test case of the example, both teams get 1 point since the game between them is a tie.

In the second test case of the example, team 1 defeats team 2 (team 1 gets 3 points), team 1 loses to team 3 (team 3 gets 3 points), and team 2 wins against team 3 (team 2 gets 3 points).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has ordered a pizza delivery. The pizza can be considered a perfect circle. There were $n$ premade cuts in the pizza when it was delivered. Each cut is a straight segment connecting the center of the pizza with its boundary.
Let $O$ be the center of the pizza, $P_i$ be the endpoint of the $i$-th cut lying on the boundary, and $R$ be the point of the boundary straight to the right of $O$. Then the counterclockwise-measured angle $\angle ROP_i$ is equal to $a_i$ degrees, where $a_i$ is an integer between $0$ and $359$. Note that angles between $0$ and $180$ angles correspond to $P_i$ in the top half of the pizza, while angles between $180$ and $360$ angles correspond to the bottom half.
Vasya may cut his pizza a few more times, and the new cuts still have to be straight segments starting at the center. He wants to make the pizza separated into several equal slices, with each slice being a circular sector with no cuts inside of it. How many new cuts Vasya will have to make?

-----Input:-----
The first line of input contains $T$ , i.e number of test cases per file.
The first line of each test case contains a single integer $n-$  the numbers of premade cuts ($2 \leq n \leq 360$).
The second lines contains $n$ integers $a_1, \ldots, a_n-$ angles of the cuts $1, \ldots, n$ respectively ($0 \leq a_1 < \ldots, a_{n - 1} < 360$).

-----Output:-----
Print a single integer$-$ the smallest number of additional cuts Vasya has to make so that the pizza is divided into several equal slices.

-----Constraints-----
- $1  \leq T  \leq 36$
- $2 \leq n \leq 360$
- $0 \leq a_1 < \ldots, a_{n - 1} < 360$

-----Sample Input:-----
3
4 
0 90 180 270
2
90 210
2
0 1

-----Sample Output:-----
0
1
358

-----EXPLANATION:-----
In the first sample the pizza is already cut into four equal slices.
In the second sample the pizza will be cut into three equal slices after making one extra cut at $330$ degrees.
In the third sample Vasya will have to cut his pizza into $360$ pieces of $1$ degree angle each.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You always wanted to be a soldier and play it out at the battleground live. When you came at Techfest 2013, you encountered Lazer Tag, a game that satiated your innate hunger for taking aim and shooting enemies. 
Lazer Tag consists of a group play, where you are assigned a fixed number of bullets (popularly known as Laser shots) during the whole game. Each right shoot on your target enemy, gives you one point. 
 Consider the series of your hits and misses which can be represented in the form of “x” and “o” where “o” represents a hit and “x” represents a miss. Suppose the series is of the form “xxxoooxxxxooxxo” Then your final score will be = 3^2 + 2^2 +1^2 i.e add up the squares of every maximal number of consecutive hits in the entire game play. 
 The probability of hitting the jth shot correctly (1≤j≤n) is P(j). In simpler terms, the probability of getting an “o” in the series at jth turn is P(j). You need to calculate the expected score at the end of your round.
 

Input
The input consists of an integer n - number of shots. In the next line, n space-separated real numbers p(1) p(2) p(3) p(4) ...... p(n) 
 

Output
Print a single number - Expected score for the play. Answer will be correct if absolute or relative error doesn't exceed 10 ^-6
 

Constraints
1 ≤ n ≤ 10^5 
0 ≤ p(j) ≤ 1 
There will be atmost six digits after decimal point in given p(j).
 

Example
Input:
3
1 1 1

Output:
9.000000 

Input:
4
0.6 0.5 0.8 0.2
Output:
4.556000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A family consisting of father bear, mother bear and son bear owns three cars. Father bear can climb into the largest car and he likes it. Also, mother bear can climb into the middle car and she likes it. Moreover, son bear can climb into the smallest car and he likes it. It's known that the largest car is strictly larger than the middle car, and the middle car is strictly larger than the smallest car. 

Masha came to test these cars. She could climb into all cars, but she liked only the smallest car. 

It's known that a character with size a can climb into some car with size b if and only if a ≤ b, he or she likes it if and only if he can climb into this car and 2a ≥ b.

You are given sizes of bears and Masha. Find out some possible integer non-negative sizes of cars.

Input

You are given four integers V1, V2, V3, Vm(1 ≤ Vi ≤ 100) — sizes of father bear, mother bear, son bear and Masha, respectively. It's guaranteed that V1 > V2 > V3.

Output

Output three integers — sizes of father bear's car, mother bear's car and son bear's car, respectively.

If there are multiple possible solutions, print any.

If there is no solution, print "-1" (without quotes).

Examples

Input

50 30 10 10


Output

50
30
10


Input

100 50 10 21


Output

-1

Note

In first test case all conditions for cars' sizes are satisfied.

In second test case there is no answer, because Masha should be able to climb into smallest car (so size of smallest car in not less than 21), but son bear should like it, so maximum possible size of it is 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef loves problems about digits and he came up with an interesting one.

Chef has given you two integers N and K. You should find the minimum non-negative integer X, such that N + X has at most K distinct digits in its decimal representation.

For example, 1231 has three distinct digits and 100 has two distinct digits.

------ 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 consists of two space-separated integers N and K, as described in the problem statement.

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

For each test case, output on a new line the minimum non-negative integer X which satisfies the problem conditions.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ 10$

----- Sample Input 1 ------ 
9
30 1
56 4
364 2
125 3
37662730 3
41872528 4
73170084 8
90032975 1
7487471 3
----- Sample Output 1 ------ 
3
0
2
0
603
1583
0
9967024
3
----- explanation 1 ------ 
Test case $1$: $30$ has $2$ distinct digits which is more than $1$, so we should add $3$ to $30$ to make it equal to $33$ which has only $1$ distinct digit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Decompose a number `num` into an array (tuple in Haskell, array of arrays `long[][]` in C# or Java) of the form `[[k1,k2,k3...], r]`,  `([k1,k2,k3...], r)` in Haskell, `[[k1,k2,k3...], [r]]` in C# or Java) such that:

1. each kn is more than one
2. eack kn is maximized (first maximizing for 2 then 3 then 4 and so on)
3. and 2^(k1) + 3^(k2) + 4^(k3) + ... + n^(kn-1) + r = num


##Examples
```
# when there are no `k` more than 1:

3 

[[], 3] = 

3

# when the remainder is zero:

8330475

[[22, 13, 10, 8, 7, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2], 0] = 

2 ^ 22 + 3 ^ 13 + 4 ^ 10 + 5 ^ 8 + 6 ^ 7 + 7 ^ 6 + 8 ^ 6 + 9 ^ 5 + 10 ^ 5 + 11 ^ 5 + 12 ^ 4 + 13 ^ 4 + 14 ^ 4 + 15 ^ 3 + 16 ^ 3 + 17 ^ 3 + 18 ^ 3 + 19 ^ 3 + 20 ^ 3 + 21 ^ 2 + 22 ^ 2 + 23 ^ 2 + 24 ^ 2 + 0 = 8330475

# when there is both `k` and a remainder:

26 

[[4, 2], 1] = 

2 ^ 4 + 3 ^ 2 + 1 = 26

# when there is neither `k` nor a remainder:

0

[[], 0] = 

0
```

As allways any feedback would be much appreciated

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers A and B. Calculate their sum and output it without leading zeros.

Input

Two lines of input data contain integers A and B (1 ≤ A, B ≤ 105).

Output

Output A + B without leading zeros.

Examples

Input

12
3


Output

15


Input

100
5


Output

105

Note

The code provided in the post about the round doesn't solve the task.

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
Recently the construction of Berland collider has been completed. Collider can be represented as a long narrow tunnel that contains *n* particles. We associate with collider 1-dimensional coordinate system, going from left to right. For each particle we know its coordinate and velocity at the moment of start of the collider. The velocities of the particles don't change after the launch of the collider. Berland scientists think that the big bang will happen at the first collision of particles, whose velocities differs in directions. Help them to determine how much time elapses after the launch of the collider before the big bang happens.

Input Specification:
The first line contains single integer *n* (1<=≤<=*n*<=≤<=5·105) — amount of particles in the collider. Next *n* lines contain description of particles. Each particle is described by two integers *x**i*, *v**i* (<=-<=109<=≤<=*x**i*,<=*v**i*<=≤<=109,<=*v**i*<=≠<=0) — coordinate and velocity respectively. All the coordinates are distinct. The particles are listed in order of increasing of coordinates. All the coordinates are in meters, and all the velocities — in meters per second. The negative velocity means that after the start of collider the particle will move to the left, and the positive — that the particle will move to the right.

Output Specification:
If there will be no big bang, output -1. Otherwise output one number — how much time in seconds elapses after the launch of the collider before the big bang happens. Your answer must have a relative or absolute error less than 10<=-<=9.

Demo Input:
['3\n-5 9\n0 1\n5 -1\n', '6\n1 3\n2 3\n3 3\n4 -3\n5 -1\n6 -100\n']

Demo Output:
['1.00000000000000000000\n', '0.02912621359223301065\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
$n$ students attended the first meeting of the Berland SU programming course ($n$ is even). All students will be divided into two groups. Each group will be attending exactly one lesson each week during one of the five working days (Monday, Tuesday, Wednesday, Thursday and Friday), and the days chosen for the groups must be different. Furthermore, both groups should contain the same number of students.

Each student has filled a survey in which they told which days of the week are convenient for them to attend a lesson, and which are not.

Your task is to determine if it is possible to choose two different week days to schedule the lessons for the group (the first group will attend the lesson on the first chosen day, the second group will attend the lesson on the second chosen day), and divide the students into two groups, so the groups have equal sizes, and for each student, the chosen lesson day for their group is convenient.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

Then the descriptions of $t$ testcases follow.

The first line of each testcase contains one integer $n$ ($2 \le n \le 1000$) — the number of students.

The $i$-th of the next $n$ lines contains $5$ integers, each of them is $0$ or $1$. If the $j$-th integer is $1$, then the $i$-th student can attend the lessons on the $j$-th day of the week. If the $j$-th integer is $0$, then the $i$-th student cannot attend the lessons on the $j$-th day of the week.

Additional constraints on the input: for each student, at least one of the days of the week is convenient, the total number of students over all testcases doesn't exceed $10^5$.


-----Output-----

For each testcase print an answer. If it's possible to divide the students into two groups of equal sizes and choose different days for the groups so each student can attend the lesson in the chosen day of their group, print "YES" (without quotes). Otherwise, print "NO" (without quotes).


-----Examples-----

Input
2
4
1 0 0 1 0
0 1 0 0 1
0 0 0 1 0
0 1 0 1 0
2
0 0 0 1 0
0 0 0 1 0
Output
YES
NO


-----Note-----

In the first testcase, there is a way to meet all the constraints. For example, the first group can consist of the first and the third students, they will attend the lessons on Thursday (the fourth day); the second group can consist of the second and the fourth students, and they will attend the lessons on Tuesday (the second day).

In the second testcase, it is impossible to divide the students into groups so they attend the lessons on different days.

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