vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Simone’s mother often complains about how Simone never helps with chores at home. In return, Simone often points out that many of the chores her mother assigns her are NP-complete to perform optimally (like cleaning the house, seating her little brothers around the dinner table in a conflict-free way, splitting the brothers’ Halloween loot in a fair manner and so on). 

Being a computer scientist, her mother finds this a fair objection. Looking over her list of potential chores, she picked one she thinks should be easy to solve – pairing a number of different kinds of socks.

In the beginning, there are $2n$ socks stacked in a pile. To pair the socks, Simone can repeatedly make one of three moves:
 - Move the sock from the top of the original pile to the top of an auxiliary pile (which is originally empty).
 - Move the sock from the top of the auxiliary pile to the top of the original pile.
 - Pair the top socks from each pile together, if they are of the same type.

Simone only has one auxiliary pile, for a total of two piles. There may be more than two socks of each type. In this case, Simone can pair them up however she wants.

Your task is to help Simone to determine the least number of moves she needs to pair the socks, if it is possible at all.

-----Input-----
The first line of input contains the integer $n$ ($1 \le n \le 10^5$) as described above. The next line contains $2n$ integers $a_1, \ldots , a_{2n}$ ($1 \le a_ i \le 10^9$ for each $i$), where $a_ i$ denotes the type of sock number $i$. Initially, sock $1$ is at the top of the pile and sock $2n$ is at the bottom.

-----Output-----
If Simone can pair all the socks, output the least number of moves she needs to do this. If it is impossible to do so, output “impossible” (without the quotes).

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

Sample Input 2:
1
3 7
Sample Output 2:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Bender has a digital table of size n × n, each cell can be switched on or off. He wants the field to have at least c switched on squares. When this condition is fulfilled, Mr Bender will be happy.

We'll consider the table rows numbered from top to bottom from 1 to n, and the columns — numbered from left to right from 1 to n. Initially there is exactly one switched on cell with coordinates (x, y) (x is the row number, y is the column number), and all other cells are switched off. Then each second we switch on the cells that are off but have the side-adjacent cells that are on.

For a cell with coordinates (x, y) the side-adjacent cells are cells with coordinates (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1).

In how many seconds will Mr. Bender get happy?


-----Input-----

The first line contains four space-separated integers n, x, y, c (1 ≤ n, c ≤ 10^9; 1 ≤ x, y ≤ n; c ≤ n^2).


-----Output-----

In a single line print a single integer — the answer to the problem.


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

Output
0

Input
9 3 8 10

Output
2



-----Note-----

Initially the first test has one painted cell, so the answer is 0. In the second test all events will go as is shown on the figure. [Image].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a dynamic list $L$ of integers, perform a sequence of the following operations. $L$ has a special element called END at the end of the list and an element of $L$ is indicated by a cursor.

* insert($x$): Insert $x$ before the element indicated by the cursor. After this operation, the cursor points the inserted element.
* move($d$): Move the cursor to the end by $d$, if $d$ is positive. Move the cursor to the front by $d$, if $d$ is negative.
* erase(): Delete the element indicated by the cursor. After this operation, the cursor points the element next to the deleted element. In case there is no such element, the cursor should point END.



In the initial state, $L$ is empty and the cursor points END.

Constraints

* $1 \leq q \leq 500,000$
* The cursor indicates an element of $L$ or END during the operations
* Erase operation will not given when the cursor points END
* $-1,000,000,000 \leq x \leq 1,000,000,000$
* Moving distance of the cursor ($\sum{|d|}$) does not exceed 1,000,000
* $L$ is not empty after performing all operations

Input

The input is given in the following format.


$q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $x$


or


1 $d$


or


2


where the first digits 0, 1 and 2 represent insert, move and erase operations respectively.

Output

Print all elements of the list in order after performing given operations. Print an element in a line.

Example

Input

5
0 1
0 2
0 3
1 1
2


Output

3
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iahub isn't well prepared on geometry problems, but he heard that this year there will be a lot of geometry problems on the IOI selection camp. Scared, Iahub locked himself in the basement and started thinking of new problems of this kind. One of them is the following.

Iahub wants to draw n distinct points and m segments on the OX axis. He can draw each point with either red or blue. The drawing is good if and only if the following requirement is met: for each segment [li, ri] consider all the red points belong to it (ri points), and all the blue points belong to it (bi points); each segment i should satisfy the inequality |ri - bi| ≤ 1.

Iahub thinks that point x belongs to segment [l, r], if inequality l ≤ x ≤ r holds.

Iahub gives to you all coordinates of points and segments. Please, help him to find any good drawing.

Input

The first line of input contains two integers: n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 100). The next line contains n space-separated integers x1, x2, ..., xn (0 ≤ xi ≤ 100) — the coordinates of the points. The following m lines contain the descriptions of the m segments. Each line contains two integers li and ri (0 ≤ li ≤ ri ≤ 100) — the borders of the i-th segment.

It's guaranteed that all the points are distinct.

Output

If there is no good drawing for a given test, output a single integer -1. Otherwise output n integers, each integer must be 0 or 1. The i-th number denotes the color of the i-th point (0 is red, and 1 is blue).

If there are multiple good drawings you can output any of them.

Examples

Input

3 3
3 7 14
1 5
6 10
11 15


Output

0 0 0

Input

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


Output

1 0 1 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
 
Example 1:
 
 
Input: "bcabc"
Output: "abc"
 
 
Example 2:
 
 
Input: "cbacdcbc"
Output: "acdb"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Julius Caesar protected his confidential information by encrypting it using a cipher. Caesar's cipher shifts each letter by a number of letters.  If the shift takes you past the end of the alphabet, just rotate back to the front of the alphabet.  In the case of a rotation by 3, w, x, y and z would map to z, a, b and c.

Original alphabet:      abcdefghijklmnopqrstuvwxyz
Alphabet rotated +3:    defghijklmnopqrstuvwxyzabc

Example 

$s=\textbf{There's-a-star-waiting-in-the-sky}$ 

$k=3$  

The alphabet is rotated by $3$, matching the mapping above.  The encrypted string is $\textbf{Wkhuh'v-d-vwdupdq-zdlwlqj-lq-wkh-vnb}$.  

Note: The cipher only encrypts letters; symbols, such as -, remain unencrypted.  

Function Description  

Complete the caesarCipher function in the editor below.  

caesarCipher has the following parameter(s):

string s: cleartext  
int k: the alphabet rotation factor  

Returns  

string:  the encrypted string  

Input Format

The first line contains the integer, $n$, the length of the unencrypted string. 

The second line contains the unencrypted string, $\boldsymbol{\mathrm{~S~}}$. 

The third line contains $\boldsymbol{\mbox{k}}$, the number of letters to rotate the alphabet by.

Constraints

$1\leq n\leq100$ 

$0\leq k\leq100$ 

$\boldsymbol{\mathrm{~S~}}$ is a valid ASCII string without any spaces.   

Sample Input
11
middle-Outz
2

Sample Output
okffng-Qwvb

Explanation
Original alphabet:      abcdefghijklmnopqrstuvwxyz
Alphabet rotated +2:    cdefghijklmnopqrstuvwxyzab

m -> o
i -> k
d -> f
d -> f
l -> n
e -> g
-    -
O -> Q
u -> w
t -> v
z -> b

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree that has n vertices, which are numbered from 1 to n, where the vertex number one is the root. Each edge has weight wi and strength pi.

Botanist Innokentiy, who is the only member of the jury of the Olympiad in Informatics, doesn't like broken trees. 

The tree is broken if there is such an edge the strength of which is less than the sum of weight of subtree's edges to which it leads.

It is allowed to reduce weight of any edge by arbitrary integer value, but then the strength of its edge is reduced by the same value. It means if the weight of the edge is 10, and the strength is 12, then by the reducing the weight by 7 its weight will equal 3, and the strength will equal 5. 

It is not allowed to increase the weight of the edge.

Your task is to get the tree, which is not broken, by reducing the weight of edges of the given tree, and also all edged should have the positive weight, moreover, the total weight of all edges should be as large as possible.

It is obvious that the strength of edges can not be negative, however it can equal zero if the weight of the subtree equals zero. 

Input

The first line contains the integer n (1 ≤ n ≤ 2·105) — the number of vertices in the tree. The next n - 1 lines contains the description of edges. Each line contains four integers x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), where x and y — vertices which connect the edge (the vertex number x is the parent of the vertex number y), w and p are the weight and the strength of the edge, accordingly. It is guaranteed that the edges describe the tree with the root in the vertex 1.

Output

If it is impossible to get unbroken tree from the given tree, print -1 in the only line.

Otherwise, the output data should contain n lines:

In the first line print the number n — the number of vertices on the tree. 

In the next n - 1 lines print the description of edges of the resulting tree. Each line should contain four integers x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), where x and y — vertices, which the edge connects (the vertex number x is the parent of the vertex number y), w and p are the new weight and the strength of the edge, accordingly. 

Print edges in the same order as they are given in input data: the first two integers of each line should not be changed. 

Examples

Input

3
1 3 5 7
3 2 4 3


Output

3
1 3 5 7
3 2 4 3


Input

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


Output

-1

Input

5
1 2 2 4
2 4 1 9
4 5 5 6
4 3 4 8


Output

5
1 2 2 4
2 4 1 9
4 5 1 2
4 3 2 6


Input

7
1 2 5 2
2 3 4 3
1 4 3 7
4 5 4 1
4 6 3 2
6 7 1 6


Output

7
1 2 5 2
2 3 2 1
1 4 3 7
4 5 3 0
4 6 3 2
6 7 1 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Toad Mikhail has an array of 2^k integers a_1, a_2, …, a_{2^k}.

Find two permutations p and q of integers 0, 1, …, 2^k-1, such that a_i is equal to p_i ⊕ q_i for all possible i, or determine there are no such permutations. Here ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

Input

The first line contains one integer k (2 ≤ k ≤ 12), denoting that the size of the array is 2^k.

The next line contains 2^k space-separated integers a_1, a_2, …, a_{2^k} (0 ≤ a_i < 2^k) — the elements of the given array.

Output

If the given array can't be represented as element-wise XOR of two permutations of integers 0, 1, …, 2^k-1, print "Fou".

Otherwise, print "Shi" in the first line.

The next two lines should contain the description of two suitable permutations. The first of these lines should contain 2^k space-separated distinct integers p_{1}, p_{2}, …, p_{2^k}, and the second line should contain 2^k space-separated distinct integers q_{1}, q_{2}, …, q_{2^k}.

All elements of p and q should be between 0 and 2^k - 1, inclusive; p_i ⊕ q_i should be equal to a_i for all i such that 1 ≤ i ≤ 2^k. If there are several possible solutions, you can print any.

Examples

Input


2
0 1 2 3


Output


Shi
2 0 1 3 
2 1 3 0 


Input


2
0 0 0 0


Output


Shi
0 1 2 3 
0 1 2 3 


Input


2
0 1 2 2


Output


Fou

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that solves an algebraic expression given as a string. 

* The expression can include only sums and products. 

* The numbers in the expression are in standard notation (NOT scientific).

* In contrast, the function should return a string with the calculated value given in scientific notation with 5 decimal digits. 

# Example:
```python
strexpression = "5 * 4 + 6"
sum_prod(strexpression) = "2.60000e+01"
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The flag of Berland is such rectangular field *n*<=×<=*m* that satisfies following conditions:
 -  Flag consists of three colors which correspond to letters 'R', 'G' and 'B'. -  Flag consists of three equal in width and height stripes, parralel to each other and to sides of the flag. Each stripe has exactly one color. -  Each color should be used in exactly one stripe. 
You are given a field *n*<=×<=*m*, consisting of characters 'R', 'G' and 'B'. Output "YES" (without quotes) if this field corresponds to correct flag of Berland. Otherwise, print "NO" (without quotes).

Input Specification:
The first line contains two integer numbers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100) — the sizes of the field.

Each of the following *n* lines consisting of *m* characters 'R', 'G' and 'B' — the description of the field.

Output Specification:
Print "YES" (without quotes) if the given field corresponds to correct flag of Berland . Otherwise, print "NO" (without quotes).

Demo Input:
['6 5\nRRRRR\nRRRRR\nBBBBB\nBBBBB\nGGGGG\nGGGGG\n', '4 3\nBRG\nBRG\nBRG\nBRG\n', '6 7\nRRRGGGG\nRRRGGGG\nRRRGGGG\nRRRBBBB\nRRRBBBB\nRRRBBBB\n', '4 4\nRRRR\nRRRR\nBBBB\nGGGG\n']

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

Note:
The field in the third example doesn't have three parralel stripes.

Rows of the field in the fourth example are parralel to each other and to borders. But they have different heights — 2, 1 and 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sasha grew up and went to first grade. To celebrate this event her mother bought her a multiplication table $M$ with $n$ rows and $n$ columns such that $M_{ij}=a_i \cdot a_j$ where $a_1, \dots, a_n$ is some sequence of positive integers.

Of course, the girl decided to take it to school with her. But while she was having lunch, hooligan Grisha erased numbers on the main diagonal and threw away the array $a_1, \dots, a_n$. Help Sasha restore the array!


-----Input-----

The first line contains a single integer $n$ ($3 \leqslant n \leqslant 10^3$), the size of the table. 

The next $n$ lines contain $n$ integers each. The $j$-th number of the $i$-th line contains the number $M_{ij}$ ($1 \leq M_{ij} \leq 10^9$). The table has zeroes on the main diagonal, that is, $M_{ii}=0$.


-----Output-----

In a single line print $n$ integers, the original array $a_1, \dots, a_n$ ($1 \leq a_i \leq 10^9$). It is guaranteed that an answer exists. If there are multiple answers, print any.


-----Examples-----
Input
5
0 4 6 2 4
4 0 6 2 4
6 6 0 3 6
2 2 3 0 2
4 4 6 2 0

Output
2 2 3 1 2 
Input
3
0 99990000 99970002
99990000 0 99980000
99970002 99980000 0

Output
9999 10000 9998

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After you had helped George and Alex to move in the dorm, they went to help their friend Fedor play a new computer game «Call of Soldiers 3».

The game has (m + 1) players and n types of soldiers in total. Players «Call of Soldiers 3» are numbered form 1 to (m + 1). Types of soldiers are numbered from 0 to n - 1. Each player has an army. Army of the i-th player can be described by non-negative integer x_{i}. Consider binary representation of x_{i}: if the j-th bit of number x_{i} equal to one, then the army of the i-th player has soldiers of the j-th type. 

Fedor is the (m + 1)-th player of the game. He assume that two players can become friends if their armies differ in at most k types of soldiers (in other words, binary representations of the corresponding numbers differ in at most k bits). Help Fedor and count how many players can become his friends.


-----Input-----

The first line contains three integers n, m, k (1 ≤ k ≤ n ≤ 20; 1 ≤ m ≤ 1000).

The i-th of the next (m + 1) lines contains a single integer x_{i} (1 ≤ x_{i} ≤ 2^{n} - 1), that describes the i-th player's army. We remind you that Fedor is the (m + 1)-th player.


-----Output-----

Print a single integer — the number of Fedor's potential friends.


-----Examples-----
Input
7 3 1
8
5
111
17

Output
0

Input
3 3 3
1
2
3
4

Output
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:


    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...


Example 1:


Input: 1
Output: "A"


Example 2:


Input: 28
Output: "AB"


Example 3:


Input: 701
Output: "ZY"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Check Tutorial tab to know how to to solve.  

Task 

The provided code stub reads two integers from STDIN, $\boldsymbol{\alpha}$ and $\boldsymbol{b}$.  Add code to print three lines where: 

 The first line contains the sum of the two numbers.   
 The second line contains the difference of the two numbers (first - second).   
 The third line contains the product of the two numbers.   

Example 

$\boldsymbol{a}=3$ 

$b=5$  

Print the following:

8
-2
15

Input Format

The first line contains the first integer, $\boldsymbol{\alpha}$. 

The second line contains the second integer, $\boldsymbol{b}$.  

Constraints

$1\leq a\leq10^{10}$ 

$1\leq b\leq10^{10}$  

Output Format

Print the three lines as explained above.   

Sample Input 0
3
2

Sample Output 0
5
1
6

Explanation 0

$3+2\implies5$ 

$3-2\Longrightarrow1$ 

$3*2\Longrightarrow6$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pinkie Pie has bought a bag of patty-cakes with different fillings! But it appeared that not all patty-cakes differ from one another with filling. In other words, the bag contains some patty-cakes with the same filling.

Pinkie Pie eats the patty-cakes one-by-one. She likes having fun so she decided not to simply eat the patty-cakes but to try not to eat the patty-cakes with the same filling way too often. To achieve this she wants the minimum distance between the eaten with the same filling to be the largest possible. Herein Pinkie Pie called the distance between two patty-cakes the number of eaten patty-cakes strictly between them.

Pinkie Pie can eat the patty-cakes in any order. She is impatient about eating all the patty-cakes up so she asks you to help her to count the greatest minimum distance between the eaten patty-cakes with the same filling amongst all possible orders of eating!

Pinkie Pie is going to buy more bags of patty-cakes so she asks you to solve this problem for several bags!


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 100$): the number of bags for which you need to solve the problem.

The first line of each bag description contains a single integer $n$ ($2 \le n \le 10^5$): the number of patty-cakes in it. The second line of the bag description contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$): the information of patty-cakes' fillings: same fillings are defined as same integers, different fillings are defined as different integers. It is guaranteed that each bag contains at least two patty-cakes with the same filling. 

It is guaranteed that the sum of $n$ over all bags does not exceed $10^5$.


-----Output-----

For each bag print in separate line one single integer: the largest minimum distance between the eaten patty-cakes with the same filling amongst all possible orders of eating for that bag.


-----Example-----
Input
4
7
1 7 1 6 4 4 6
8
1 1 4 6 4 6 4 7
3
3 3 3
6
2 5 2 3 1 4

Output
3
2
0
4



-----Note-----

For the first bag Pinkie Pie can eat the patty-cakes in the following order (by fillings): $1$, $6$, $4$, $7$, $1$, $6$, $4$ (in this way, the minimum distance is equal to $3$).

For the second bag Pinkie Pie can eat the patty-cakes in the following order (by fillings): $1$, $4$, $6$, $7$, $4$, $1$, $6$, $4$ (in this way, the minimum distance is equal to $2$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Print the factorial of the given integer number n. The factorial of n is equal to 1·2·...·n.

Input

The only line contains n (1 ≤ n ≤ 10).

Output

Print the factorial of n.

Examples

Input

3


Output

6


Input

5


Output

120

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After obtaining a lot of gold from capturing different kingdoms, King Kala buys a large area of land. N trees are planted on the land, numbered from 1 to N. Each tree i, has coordinates as Xi, Yi. King Kala has two sons who, as their father, are selfish. To divide the land between two sons, King Kala draws a partition line on the land which is given by three coefficients of the line equation A, B and C. Now, Prince Parmar, being the elder son got a chance to pick any one side. But he wants the side of the partition which contains the maximum number of trees. How many trees can he get?

Input

The first line contains the number of test cases T. In each test case, the first line contains N. The next line contains three space separated integers A, B and C. The next N lines contain Xi, Yi which are the co-ordinates of N trees.

Output

For each test case, print the maximum number of trees which are completely on one side of the partition line.

Constraints

1 ≤ T ≤10
1 ≤ N ≤ 10^5
-100 ≤ A,B ≤ 100
-10^5 ≤ C, Xi, Yi ≤ 10^5

SAMPLE INPUT
1
4
1 -1 0
2 1
1 3
4 2
3 3

SAMPLE OUTPUT
2

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