vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Cd and pwd commands

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya is writing an operating system shell, and it should have commands for working with directories. To begin with, he decided to go with just two commands: cd (change the current directory) and pwd (display the current directory).

Directories in Vasya's operating system form a traditional hierarchical tree structure. There is a single root directory, denoted by the slash character "/". Every other directory has a name — a non-empty string consisting of lowercase Latin letters. Each directory (except for the root) has a parent directory — the one that contains the given directory. It is denoted as "..".

The command cd takes a single parameter, which is a path in the file system. The command changes the current directory to the directory specified by the path. The path consists of the names of directories separated by slashes. The name of the directory can be "..", which means a step up to the parent directory. «..» can be used in any place of the path, maybe several times. If the path begins with a slash, it is considered to be an absolute path, that is, the directory changes to the specified one, starting from the root. If the parameter begins with a directory name (or ".."), it is considered to be a relative path, that is, the directory changes to the specified directory, starting from the current one.

The command pwd should display the absolute path to the current directory. This path must not contain "..".

Initially, the current directory is the root. All directories mentioned explicitly or passed indirectly within any command cd are considered to exist. It is guaranteed that there is no attempt of transition to the parent directory of the root directory.

Input Specification:
The first line of the input data contains the single integer *n* (1<=≤<=*n*<=≤<=50) — the number of commands.

Then follow *n* lines, each contains one command. Each of these lines contains either command pwd, or command cd, followed by a space-separated non-empty parameter.

The command parameter cd only contains lower case Latin letters, slashes and dots, two slashes cannot go consecutively, dots occur only as the name of a parent pseudo-directory. The command parameter cd does not end with a slash, except when it is the only symbol that points to the root directory. The command parameter has a length from 1 to 200 characters, inclusive.

Directories in the file system can have the same names.

Output Specification:
For each command pwd you should print the full absolute path of the given directory, ending with a slash. It should start with a slash and contain the list of slash-separated directories in the order of being nested from the root to the current folder. It should contain no dots.

Demo Input:
['7\npwd\ncd /home/vasya\npwd\ncd ..\npwd\ncd vasya/../petya\npwd\n', '4\ncd /a/b\npwd\ncd ../a/b\npwd\n']

Demo Output:
['/\n/home/vasya/\n/home/\n/home/petya/\n', '/a/b/\n/a/a/b/\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we'll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.

You are given an array of n positive integers. For each of them determine whether it is Т-prime or not.

Input

The first line contains a single positive integer, n (1 ≤ n ≤ 105), showing how many numbers are in the array. The next line contains n space-separated integers xi (1 ≤ xi ≤ 1012).

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is advised to use the cin, cout streams or the %I64d specifier.

Output

Print n lines: the i-th line should contain "YES" (without the quotes), if number xi is Т-prime, and "NO" (without the quotes), if it isn't.

Examples

Input

3
4 5 6


Output

YES
NO
NO

Note

The given test has three numbers. The first number 4 has exactly three divisors — 1, 2 and 4, thus the answer for this number is "YES". The second number 5 has two divisors (1 and 5), and the third number 6 has four divisors (1, 2, 3, 6), hence the answer for them is "NO".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer m, and a list of n distinct integers between 0 and m - 1.

You would like to construct a sequence satisfying the properties:

  * Each element is an integer between 0 and m - 1, inclusive. 
  * All prefix products of the sequence modulo m are distinct. 
  * No prefix product modulo m appears as an element of the input list. 
  * The length of the sequence is maximized. 



Construct any sequence satisfying the properties above.

Input

The first line of input contains two integers n and m (0 ≤ n < m ≤ 200 000) — the number of forbidden prefix products and the modulus.

If n is non-zero, the next line of input contains n distinct integers between 0 and m - 1, the forbidden prefix products. If n is zero, this line doesn't exist.

Output

On the first line, print the number k, denoting the length of your sequence.

On the second line, print k space separated integers, denoting your sequence.

Examples

Input

0 5


Output

5
1 2 4 3 0


Input

3 10
2 9 1


Output

6
3 9 2 9 8 0

Note

For the first case, the prefix products of this sequence modulo m are [1, 2, 3, 4, 0].

For the second case, the prefix products of this sequence modulo m are [3, 7, 4, 6, 8, 0].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You found a useless array a of 2n positive integers. You have realized that you actually don't need this array, so you decided to throw out all elements of a.

It could have been an easy task, but it turned out that you should follow some rules: 

  1. In the beginning, you select any positive integer x.
  2. Then you do the following operation n times: 
    * select two elements of array with sum equals x; 
    * remove them from a and replace x with maximum of that two numbers. 



For example, if initially a = [3, 5, 1, 2], you can select x = 6. Then you can select the second and the third elements of a with sum 5 + 1 = 6 and throw them out. After this operation, x equals 5 and there are two elements in array: 3 and 2. You can throw them out on the next operation.

Note, that you choose x before the start and can't change it as you want between the operations.

Determine how should you behave to throw out all elements of a.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains the single integer n (1 ≤ n ≤ 1000).

The second line of each test case contains 2n integers a_1, a_2, ..., a_{2n} (1 ≤ a_i ≤ 10^6) — the initial array a.

It is guaranteed that the total sum of n over all test cases doesn't exceed 1000.

Output

For each test case in the first line print YES if it is possible to throw out all elements of the array and NO otherwise.

If it is possible to throw out all elements, print the initial value of x you've chosen. Print description of n operations next. For each operation, print the pair of integers you remove.

Example

Input


4
2
3 5 1 2
3
1 1 8 8 64 64
2
1 1 2 4
5
1 2 3 4 5 6 7 14 3 11


Output


YES
6
1 5
2 3
NO
NO
YES
21
14 7
3 11
5 6
2 4
3 1

Note

The first test case was described in the statement.

In the second and third test cases, we can show that it is impossible to throw out all elements of array a.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given N numbers A[i], find the count of prime numbers.

Input Specifications:

The first line contains number of Test cases, T.
For each test case T,
    The first line contains N.
    N lines follow with A[1] to A[n]

Output Specifications

For every test case T, a count of the total number of prime numbers

Hint: 0 and 1 are not prime numbers

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 1000000
0 ≤ A[i] ≤ 1000
Register for IndiaHacksSAMPLE INPUT
1
5
45 
31
7
28
90

SAMPLE OUTPUT
2

Register for IndiaHacks

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array with repeated elements, the task is to find the maximum distance between two occurrences of an element.
Example 1:
Input
n= 6
arr = {1, 1, 2, 2, 2, 1}
Output
5
Explanation
arr[] = {1, 1, 2, 2, 2, 1}
Max Distance: 5
Distance for 1 is: 5-0 = 5
Distance for 2 is : 4-2 = 2
Max Distance 5
Example 2:
Input
n = 12
arr = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Output
10
Explanation
arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Max Distance 10
maximum distance for 2 is 11-1 = 10
maximum distance for 1 is 4-2 = 2
maximum distance for 4 is 10-5 = 5
Your Task:
Complete maxDistance() function which takes both the given array and their size as function arguments and returns the maximum distance between 2 same elements. 
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1<=N<=10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've been in love with Coronavirus-chan for a long time, but you didn't know where she lived until now. And just now you found out that she lives in a faraway place called Naha. 

You immediately decided to take a vacation and visit Coronavirus-chan. Your vacation lasts exactly $x$ days and that's the exact number of days you will spend visiting your friend. You will spend exactly $x$ consecutive (successive) days visiting Coronavirus-chan.

They use a very unusual calendar in Naha: there are $n$ months in a year, $i$-th month lasts exactly $d_i$ days. Days in the $i$-th month are numbered from $1$ to $d_i$. There are no leap years in Naha.

The mood of Coronavirus-chan (and, accordingly, her desire to hug you) depends on the number of the day in a month. In particular, you get $j$ hugs if you visit Coronavirus-chan on the $j$-th day of the month.

You know about this feature of your friend and want to plan your trip to get as many hugs as possible (and then maybe you can win the heart of Coronavirus-chan). 

Please note that your trip should not necessarily begin and end in the same year.


-----Input-----

The first line of input contains two integers $n$ and $x$ ($1 \le n \le 2 \cdot 10^5$) — the number of months in the year and the number of days you can spend with your friend.

The second line contains $n$ integers $d_1, d_2, \ldots, d_n$, $d_i$ is the number of days in the $i$-th month ($1 \le d_i \le 10^6$).

It is guaranteed that $1 \le x \le d_1 + d_2 + \ldots + d_n$.


-----Output-----

Print one integer — the maximum number of hugs that you can get from Coronavirus-chan during the best vacation in your life.


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

Output
5
Input
3 6
3 3 3

Output
12
Input
5 6
4 2 3 1 3

Output
15


-----Note-----

In the first test case, the numbers of the days in a year are (indices of days in a corresponding month) $\{1,1,2,3,1\}$. Coronavirus-chan will hug you the most if you come on the third day of the year: $2+3=5$ hugs.

In the second test case, the numbers of the days are $\{1,2,3,1,2,3,1,2,3\}$. You will get the most hugs if you arrive on the third day of the year: $3+1+2+3+1+2=12$ hugs.

In the third test case, the numbers of the days are $\{1,2,3,4,1,2, 1,2,3, 1, 1,2,3\}$. You will get the most hugs if you come on the twelfth day of the year: your friend will hug you $2+3+1+2+3+4=15$ times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has gotten interested in programming contests in TCMCF+++ rules. On the contest n problems were suggested and every problem had a cost — a certain integral number of points (perhaps, negative or even equal to zero). According to TCMCF+++ rules, only accepted problems can earn points and the overall number of points of a contestant was equal to the product of the costs of all the problems he/she had completed. If a person didn't solve anything, then he/she didn't even appear in final standings and wasn't considered as participant. Vasya understood that to get the maximal number of points it is not always useful to solve all the problems. Unfortunately, he understood it only after the contest was finished. Now he asks you to help him: find out what problems he had to solve to earn the maximal number of points.

Input

The first line contains an integer n (1 ≤ n ≤ 100) — the number of the suggested problems. The next line contains n space-separated integers ci ( - 100 ≤ ci ≤ 100) — the cost of the i-th task. The tasks' costs may coinсide.

Output

Print space-separated the costs of the problems that needed to be solved to get the maximal possible number of points. Do not forget, please, that it was necessary to solve at least one problem. If there are several solutions to that problem, print any of them.

Examples

Input

5
1 2 -3 3 3


Output

3 1 2 3 


Input

13
100 100 100 100 100 100 100 100 100 100 100 100 100


Output

100 100 100 100 100 100 100 100 100 100 100 100 100 


Input

4
-2 -2 -2 -2


Output

-2 -2 -2 -2 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Heidi and Doctor Who hopped out of the TARDIS and found themselves at EPFL in 2018. They were surrounded by stormtroopers and Darth Vader was approaching. Miraculously, they managed to escape to a nearby rebel base but the Doctor was very confused. Heidi reminded him that last year's HC2 theme was Star Wars. Now he understood, and he's ready to face the evils of the Empire!

The rebels have $s$ spaceships, each with a certain attacking power $a$.

They want to send their spaceships to destroy the empire bases and steal enough gold and supplies in order to keep the rebellion alive.

The empire has $b$ bases, each with a certain defensive power $d$, and a certain amount of gold $g$.

A spaceship can attack all the bases which have a defensive power less than or equal to its attacking power.

If a spaceship attacks a base, it steals all the gold in that base.

The rebels are still undecided which spaceship to send out first, so they asked for the Doctor's help. They would like to know, for each spaceship, the maximum amount of gold it can steal.


-----Input-----

The first line contains integers $s$ and $b$ ($1 \leq s, b \leq 10^5$), the number of spaceships and the number of bases, respectively.

The second line contains $s$ integers $a$ ($0 \leq a \leq 10^9$), the attacking power of each spaceship.

The next $b$ lines contain integers $d, g$ ($0 \leq d \leq 10^9$, $0 \leq g \leq 10^4$), the defensive power and the gold of each base, respectively.


-----Output-----

Print $s$ integers, the maximum amount of gold each spaceship can steal, in the same order as the spaceships are given in the input.


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

Output
1 9 11 9 11



-----Note-----

The first spaceship can only attack the first base.

The second spaceship can attack the first and third bases.

The third spaceship can attack the first, second and third bases.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As we all know caterpillars love to eat leaves. Usually, a caterpillar sits on leaf, eats as much of it as it can (or wants), then stretches out to its full length to reach a new leaf with its front end, and finally "hops" to it by contracting its back end to that leaf.
We have with us a very long, straight branch of a tree with leaves distributed uniformly along its length, and a set of caterpillars sitting on the first leaf. (Well, our leaves are big enough to accommodate upto $20$ caterpillars!). As time progresses our caterpillars eat and hop repeatedly, thereby damaging many leaves. Not all caterpillars are of the same length, so different caterpillars may eat different sets of leaves. We would like to find out the number of leaves that will be undamaged at the end of this eating spree. We assume that adjacent leaves are a unit distance apart and the length of the caterpillars is also given in the same unit.
For example suppose our branch had $20$ leaves (placed $1$ unit apart) and $3$ caterpillars of length $3, 2$ and $5$ units respectively. Then, first caterpillar would first eat leaf $1$, then hop to leaf $4$ and eat it and then hop to leaf $7$ and eat it and so on. So the first caterpillar would end up eating the leaves at positions $1,4,7,10,13,16$ and $19$. The second caterpillar would eat the leaves at positions $1,3,5,7,9,11,13,15,17$ and $19$. The third caterpillar would eat the leaves at positions $1,6,11$ and $16$. Thus we would have undamaged leaves at positions $2,8,12,14,18$ and $20$. So the answer to this example is $6$.

-----Input:-----
The first line of the input contains two integers $N$ and $K$, where $N$ is the number of leaves and $K$ is the number of caterpillars. Lines $2,3,...,K+1$ describe the lengths of the $K$ caterpillars. Line $i+1$ ($1 \leq i \leq K$) contains a single integer representing the length of the $i^{th}$ caterpillar.

-----Output:-----
A line containing a single integer, which is the number of leaves left on the branch after all the caterpillars have finished their eating spree.

-----Constraints:-----
- $1 \leq N \leq 1000000000$.
- $1 \leq K \leq 20$.
- The length of the caterpillars lie between $1$ and $N$.
- $50 \%$ of test cases will also satisfy $1 \leq N \leq 10000000$ and $1 \leq K \leq 16$.

-----Sample Input:-----
20 3
3
2
5

-----Sample Output:-----
6

-----Hint:-----
You may use $64$-bit integers (long long in C/C++) to avoid errors while multiplying large integers. The maximum value you can store in a $32$-bit integer is $2^{31}-1$, which is approximately $2 \cdot 10^9$. $64$-bit integers can store values greater than $10^{18}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During the lunch break all n Berland State University students lined up in the food court. However, it turned out that the food court, too, has a lunch break and it temporarily stopped working.

Standing in a queue that isn't being served is so boring! So, each of the students wrote down the number of the student ID of the student that stands in line directly in front of him, and the student that stands in line directly behind him. If no one stands before or after a student (that is, he is the first one or the last one), then he writes down number 0 instead (in Berland State University student IDs are numerated from 1).

After that, all the students went about their business. When they returned, they found out that restoring the queue is not such an easy task.

Help the students to restore the state of the queue by the numbers of the student ID's of their neighbors in the queue.

Input

The first line contains integer n (2 ≤ n ≤ 2·105) — the number of students in the queue. 

Then n lines follow, i-th line contains the pair of integers ai, bi (0 ≤ ai, bi ≤ 106), where ai is the ID number of a person in front of a student and bi is the ID number of a person behind a student. The lines are given in the arbitrary order. Value 0 is given instead of a neighbor's ID number if the neighbor doesn't exist.

The ID numbers of all students are distinct. It is guaranteed that the records correspond too the queue where all the students stand in some order.

Output

Print a sequence of n integers x1, x2, ..., xn — the sequence of ID numbers of all the students in the order they go in the queue from the first student to the last one.

Examples

Input

4
92 31
0 7
31 0
7 141


Output

92 7 31 141 

Note

The picture illustrates the queue for the first sample.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing the following simple game with a friend:
 - The first player picks a positive integer $X$.
 - The second player gives a list of $k$ distinct positive integers $Y_1, \ldots , Y_ k$ such that $(Y_1+1)(Y_2+1) \cdots (Y_ k+1) = X$, and gets $k$ points.

Write a program that plays the second player.

-----Input-----
The input consists of a single integer $X$ satisfying $10^3 \le X \le 10^{15}$, giving the number picked by the first player.

-----Output-----
Write a single integer $k$, giving the number of points obtained by the second player, assuming she plays as good as possible.

-----Examples-----
Sample Input:
1099511627776
Sample Output:
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pierre is famous for his macarons. He makes round macarons, stored in square boxes of size $1\times 1$, and oval-shaped macarons, stored in rectangular boxes of size $1\times 2$ (or, rotated, in rectangular boxes of size $2\times 1$). For the purpose of a buffet, Pierre wishes to tile a rectangular table of size $N\times M$ with the two kinds of macarons, meaning that the table must be completely full, with no empty space left. The width $N$ of the table is small, for the guest to be able to grab the macarons easily, and the length $M$ of the table is large, to accommodate a huge number of guests. To keep the table pretty, the orientation of macarons should always be aligned with the sides of the table.

Pierre wishes to know how many ways there are to tile the table. Can you help him?Input

The input consists of the following integers:
 - the value of $N$, an integer, on the first line;
 - the value of $M$, an integer, on the second line.Limits

The input satisfies $1 \leq N \leq 8$ and $1 \leq M \leq 10^{18}$.Output

The output should consist of the total number of tilings, given modulo $10^9$, on a single line.

-----Examples-----
Sample Input:
2
2
Sample Output:
7

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

It's been more than 20 minutes since the negligent waiter has taken your order for the house special prime tofu steak with a side of chili fries.

Out of boredom, you start fiddling around with the condiments tray. To be efficient, you want to be familiar with the choice of sauces and spices before your order is finally served.

You also examine the toothpick holder and try to analyze its inner workings when - yikes - the holder's lid falls off and all 23 picks lay scattered on the table.

Being a good and hygiene oriented citizen, you decide not to just put them back in the holder. Instead of letting all the good wood go to waste, you start playing around with the picks.

In the first "round", you lay down one toothpick vertically. You've used a total of one toothpick.

In the second "round", at each end of the first toothpick, you add a perpendicular toothpick at its center point. You added two additional toothpicks for a total of three toothpicks.

In the next rounds, you continue to add perpendicular toothpicks to each free end of toothpicks already on the table.

With your 23 toothpicks, you can complete a total of six rounds:


You wonder if you'd be able to implement this sequence in your favorite programming language. Because your food still hasn't arrived, you decide to take out your laptop and start implementing...

Challenge
Implement a script that returns the amount of toothpicks needed to complete n amount of rounds of the toothpick sequence.

```
0 <= n <= 5000
```

Hint
You can attempt this brute force or get some inspiration from the math department.

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