vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Oh no! As a result of recent elections the “Random Laws” party took control of the government. This is going to have bad consequences for Mr. Bourgeois’ company, which just approved the way new salaries will be calculated. The company has $N$ workers and the salary for worker $i$ is going to be determined as a number drawn uniformly from the range $[L_ i, R_ i]$. Since the company already figured out which workers are the most efficient ones, for each $i$ in $[2, N]$, we know that $L_{i-1} \leq L_ i$ and $R_{i-1} \leq R_ i$, but note that as a result of chance, worker $i-1$ might still end up with a larger salary than worker $i$.

The new government introduced a law, where any worker who got a smaller salary than a coworker can sue the company for the amount of their difference. What’s even more atrocious is that they can do it for every worker who got a larger salary. So if there were three employees: Alice, Bob, and Charlie, who got salaries of $1$, $3$, and $7$ coins respectively, then employee Bob can sue with regards to Charlie for $4$ coins, while Alice can sue for $2$ coins because of Bob and for $6$ coins because of Charlie. The total amount of damages the company will have to pay is $12$.

While the exact salary amounts are not known yet, Mr. Bourgeois would like to find out the expected amount of damages that his company will have to pay. Since the answer can be very big, output the answer divided by $N^2$.

-----Input-----
The first line contains $N$, ($1 \leq N \leq 100000$). The next $N$ lines each contain two real numbers $L_ i$ and $R_ i$ ($1 \leq L_ i \leq R_ i \leq 10^6$). All real numbers in the input have at most $6$ digits after the decimal point.

-----Output-----
Output one number: expected payment divided by $N^2$. Your answer will be considered correct if its absolute or relative error is less than $10^{-4}$.

-----Examples-----
Sample Input:
2
1.2 10.2
2.2 15.2
Sample Output:
1.114672365

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i-th card from the left is A_i.

You will do the following operation N-1 times:

* Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.



After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.

Find the maximum number of points you can gain.

Constraints

* 1 \leq N \leq 2000
* 1 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 \cdots A_{3N}


Output

Print the maximum number of points you can gain.

Examples

Input

2
1 2 1 2 2 1


Output

2


Input

3
1 1 2 2 3 3 3 2 1


Output

1


Input

3
1 1 2 2 2 3 3 3 1


Output

3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two multisets A and B. Each multiset has exactly n integers each between 1 and n inclusive. Multisets may contain multiple copies of the same number.

You would like to find a nonempty subset of A and a nonempty subset of B such that the sum of elements in these subsets are equal. Subsets are also multisets, i.e. they can contain elements with equal values.

If no solution exists, print  - 1. Otherwise, print the indices of elements in any such subsets of A and B that have the same sum.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 1 000 000) — the size of both multisets.

The second line contains n integers, denoting the elements of A. Each element will be between 1 and n inclusive.

The third line contains n integers, denoting the elements of B. Each element will be between 1 and n inclusive.

Output

If there is no solution, print a single integer  - 1. Otherwise, your solution should be printed on four lines.

The first line should contain a single integer ka, the size of the corresponding subset of A. The second line should contain ka distinct integers, the indices of the subset of A.

The third line should contain a single integer kb, the size of the corresponding subset of B. The fourth line should contain kb distinct integers, the indices of the subset of B.

Elements in both sets are numbered from 1 to n. If there are multiple possible solutions, print any of them.

Examples

Input

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


Output

1
2
3
5 8 10


Input

5
4 4 3 3 3
2 2 2 2 5


Output

2
2 3
2
3 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given array whose element values are randomly picked from single-digit integers `0` to `9`, return an array with the same digit order but all `0`'s paired. Paring two `0`'s generates one `0` at the location of the first.

Ex:
```python
pair_zeros([0, 1, 0, 2])
# paired: ^-----^ cull second zero
       == [0, 1, 2];
#   kept: ^

pair_zeros([0, 1, 0, 0])
# paired: ^-----^
       == [0, 1,    0];
#   kept: ^

pair_zeros([1, 0, 7, 0, 1])
# paired:    ^-----^
       == [1, 0, 7,    1];
#   kept:    ^

pair_zeros([0, 1, 7, 0, 2, 2, 0, 0, 1, 0])
# paired: ^--------^ 
#        [0, 1, 7,    2, 2, 0, 0, 1, 0]
#   kept: ^         paired: ^--^
       == [0, 1, 7,    2, 2, 0,    1, 0];
#   kept:                   ^
```

Here are the 2 important rules:

1. Pairing happens from left to right in the array. However, for each pairing, the "second" `0` will always be paired towards the first (right to left)
2. `0`'s generated by pairing can NOT be paired again

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasily the Programmer loves romance, so this year he decided to illuminate his room with candles.

Vasily has *a* candles.When Vasily lights up a new candle, it first burns for an hour and then it goes out. Vasily is smart, so he can make *b* went out candles into a new candle. As a result, this new candle can be used like any other new candle.

Now Vasily wonders: for how many hours can his candles light up the room if he acts optimally well? Help him find this number.

Input Specification:
The single line contains two integers, *a* and *b* (1<=≤<=*a*<=≤<=1000; 2<=≤<=*b*<=≤<=1000).

Output Specification:
Print a single integer — the number of hours Vasily can light up the room for.

Demo Input:
['4 2\n', '6 3\n']

Demo Output:
['7\n', '8\n']

Note:
Consider the first sample. For the first four hours Vasily lights up new candles, then he uses four burned out candles to make two new ones and lights them up. When these candles go out (stop burning), Vasily can make another candle. Overall, Vasily can light up the room for 7 hours.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Union of Doubly Linked Lists

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Doubly linked list is one of the fundamental data structures. A doubly linked list is a sequence of elements, each containing information about the previous and the next elements of the list. In this problem all lists have linear structure. I.e. each element except the first has exactly one previous element, each element except the last has exactly one next element. The list is not closed in a cycle.

In this problem you are given *n* memory cells forming one or more doubly linked lists. Each cell contains information about element from some list. Memory cells are numbered from 1 to *n*.

For each cell *i* you are given two values: 
 -  *l**i* — cell containing previous element for the element in the cell *i*; -  *r**i* — cell containing next element for the element in the cell *i*. 
If cell *i* contains information about the element which has no previous element then *l**i*<==<=0. Similarly, if cell *i* contains information about the element which has no next element then *r**i*<==<=0.

For example, for the picture above the values of *l* and *r* are the following: *l*1<==<=4, *r*1<==<=7; *l*2<==<=5, *r*2<==<=0; *l*3<==<=0, *r*3<==<=0; *l*4<==<=6, *r*4<==<=1; *l*5<==<=0, *r*5<==<=2; *l*6<==<=0, *r*6<==<=4; *l*7<==<=1, *r*7<==<=0.

Your task is to unite all given lists in a single list, joining them to each other in any order. In particular, if the input data already contains a single list, then there is no need to perform any actions. Print the resulting list in the form of values *l**i*, *r**i*.

Any other action, other than joining the beginning of one list to the end of another, can not be performed.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=100) — the number of memory cells where the doubly linked lists are located.

Each of the following *n* lines contains two integers *l**i*, *r**i* (0<=≤<=*l**i*,<=*r**i*<=≤<=*n*) — the cells of the previous and the next element of list for cell *i*. Value *l**i*<==<=0 if element in cell *i* has no previous element in its list. Value *r**i*<==<=0 if element in cell *i* has no next element in its list.

It is guaranteed that the input contains the correct description of a single or more doubly linked lists. All lists have linear structure: each element of list except the first has exactly one previous element; each element of list except the last has exactly one next element. Each memory cell contains information about one element from some list, each element of each list written in one of *n* given cells.

Output Specification:
Print *n* lines, the *i*-th line must contain two integers *l**i* and *r**i* — the cells of the previous and the next element of list for cell *i* after all lists from the input are united in a single list. If there are many solutions print any of them.

Demo Input:
['7\n4 7\n5 0\n0 0\n6 1\n0 2\n0 4\n1 0\n']

Demo Output:
['4 7\n5 6\n0 5\n6 1\n3 2\n2 4\n1 0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Phoenix's homeland, the Fire Nation had n cities that were connected by m roads, but the roads were all destroyed by an earthquake. The Fire Nation wishes to repair n-1 of these roads so that all the cities are connected again. 

The i-th city has a_i tons of asphalt. x tons of asphalt are used up when repairing a road, and to repair a road between i and j, cities i and j must have at least x tons of asphalt between them. In other words, if city i had a_i tons of asphalt and city j had a_j tons, there would remain a_i+a_j-x tons after repairing the road between them. Asphalt can be moved between cities if the road between them is already repaired.

Please determine if it is possible to connect all the cities, and if so, output any sequence of roads to repair.

Input

The first line contains integers n, m, and x (2 ≤ n ≤ 3 ⋅ 10^5; n-1 ≤ m ≤ 3 ⋅ 10^5; 1 ≤ x ≤ 10^9) — the number of cities, number of roads, and amount of asphalt needed to repair one road.

The next line contains n space-separated integer a_i (0 ≤ a_i ≤ 10^9) — the amount of asphalt initially at city i.

The next m lines contains two integers x_i and y_i (x_i≠ y_i; 1 ≤ x_i, y_i ≤ n) — the cities connected by the i-th road. It is guaranteed that there is at most one road between each pair of cities, and that the city was originally connected before the earthquake.

Output

If it is not possible to connect all the cities, print NO. Otherwise, print YES followed by n-1 integers e_1, e_2, ..., e_{n-1}, the order in which the roads should be repaired. e_i is the index of the i-th road to repair. If there are multiple solutions, print any.

Examples

Input


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


Output


YES
3
2
1
4


Input


2 1 2
1 1
1 2


Output


YES
1


Input


2 1 2
0 1
1 2


Output


NO


Input


5 6 5
0 9 4 0 10
1 2
1 3
2 3
3 4
1 4
4 5


Output


YES
6
4
1
2

Note

In the first example, the roads are repaired in the following order: 

  * Road 3 is repaired, connecting cities 3 and 4. City 4 originally had 4 tons of asphalt. After this road is constructed, 3 tons remain. 
  * Road 2 is repaired, connecting cities 2 and 3. The asphalt from city 4 can be transported to city 3 and used for the road. 2 tons remain. 
  * Road 1 is repaired, connecting cities 1 and 2. The asphalt is transported to city 2 and used for the road. 1 ton remain. 
  * Road 4 is repaired, connecting cities 4 and 5. The asphalt is transported to city 4 and used for the road. No asphalt remains. 

All the cities are now connected.

In the second example, cities 1 and 2 use all their asphalt together to build the road. They each have 1 ton, so together they have 2 tons, which is enough.

In the third example, there isn't enough asphalt to connect cities 1 and 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number 'N'. The task is to find the N^{th} number whose each digit is a prime number i.e 2, 3, 5, 7. In other words you have to find nth number of this sequence : 2, 3, 5, 7, 22, 23 ,.. and so on.
Example 1:
Input:
N = 10
Output: 33
Explanation:10^{th} number in the sequence of
numbers whose each digit is prime is 33.
Example 2:
Input:
N = 21
Output: 222
Explanation:21^{st} number in the sequence of
numbers whose each digit is prime is 222.
Your Task:
Complete primeDigits function and return the nth number of the given sequence made of prime digits.
Constraints:
1 <= N <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In some game by Playrix it takes t minutes for an oven to bake k carrot cakes, all cakes are ready at the same moment t minutes after they started baking. Arkady needs at least n cakes to complete a task, but he currently don't have any. However, he has infinitely many ingredients and one oven. Moreover, Arkady can build one more similar oven to make the process faster, it would take d minutes to build the oven. While the new oven is being built, only old one can bake cakes, after the new oven is built, both ovens bake simultaneously. Arkady can't build more than one oven.

Determine if it is reasonable to build the second oven, i.e. will it decrease the minimum time needed to get n cakes or not. If the time needed with the second oven is the same as with one oven, then it is unreasonable.


-----Input-----

The only line contains four integers n, t, k, d (1 ≤ n, t, k, d ≤ 1 000) — the number of cakes needed, the time needed for one oven to bake k cakes, the number of cakes baked at the same time, the time needed to build the second oven. 


-----Output-----

If it is reasonable to build the second oven, print "YES". Otherwise print "NO".


-----Examples-----
Input
8 6 4 5

Output
YES

Input
8 6 4 6

Output
NO

Input
10 3 11 4

Output
NO

Input
4 2 1 4

Output
YES



-----Note-----

In the first example it is possible to get 8 cakes in 12 minutes using one oven. The second oven can be built in 5 minutes, so after 6 minutes the first oven bakes 4 cakes, the second oven bakes 4 more ovens after 11 minutes. Thus, it is reasonable to build the second oven. 

In the second example it doesn't matter whether we build the second oven or not, thus it takes 12 minutes to bake 8 cakes in both cases. Thus, it is unreasonable to build the second oven.

In the third example the first oven bakes 11 cakes in 3 minutes, that is more than needed 10. It is unreasonable to build the second oven, because its building takes more time that baking the needed number of cakes using the only oven.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a far away kingdom lives a very greedy king. To defend his land, he built n guard towers. Apart from the towers the kingdom has two armies, each headed by a tyrannical and narcissistic general. The generals can't stand each other, specifically, they will never let soldiers of two armies be present in one tower.

During defence operations to manage a guard tower a general has to send part of his army to that tower. Each general asks some fee from the king for managing towers. As they live in a really far away kingdom, each general evaluates his fee in the following weird manner: he finds two remotest (the most distant) towers, where the soldiers of his army are situated and asks for the fee equal to the distance. Each tower is represented by a point on the plane with coordinates (x, y), and the distance between two points with coordinates (x1, y1) and (x2, y2) is determined in this kingdom as |x1 - x2| + |y1 - y2|.

The greedy king was not exactly satisfied with such a requirement from the generals, that's why he only agreed to pay one fee for two generals, equal to the maximum of two demanded fees. However, the king is still green with greed, and among all the ways to arrange towers between armies, he wants to find the cheapest one. Each tower should be occupied by soldiers of exactly one army.

He hired you for that. You should find the minimum amount of money that will be enough to pay the fees. And as the king is also very scrupulous, you should also count the number of arrangements that will cost the same amount of money. As their number can be quite large, it is enough for the king to know it as a remainder from dividing by 109 + 7.

Two arrangements are distinct if the sets of towers occupied by soldiers of the first general are distinct.

Input

The first line contains an integer n (2 ≤ n ≤ 5000), n is the number of guard towers. Then follow n lines, each of which contains two integers x, y — the coordinates of the i-th tower (0 ≤ x, y ≤ 5000). No two towers are present at one point.

Pretest 6 is one of the maximal tests for this problem.

Output

Print on the first line the smallest possible amount of money that will be enough to pay fees to the generals. 

Print on the second line the number of arrangements that can be carried out using the smallest possible fee. This number should be calculated modulo 1000000007 (109 + 7).

Examples

Input

2
0 0
1 1


Output

0
2


Input

4
0 0
0 1
1 0
1 1


Output

1
4


Input

3
0 0
1000 1000
5000 5000


Output

2000
2

Note

In the first example there are only two towers, the distance between which is equal to 2. If we give both towers to one general, then we well have to pay 2 units of money. If each general receives a tower to manage, to fee will be equal to 0. That is the smallest possible fee. As you can easily see, we can obtain it in two ways.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The `depth` of an integer `n` is defined to be how many multiples of `n` it is necessary to compute before all `10` digits have appeared at least once in some multiple. 

example:
```
let see n=42

Multiple         value         digits     comment
42*1              42            2,4 
42*2              84             8         4 existed
42*3              126           1,6        2 existed
42*4              168            -         all existed
42*5              210            0         2,1 existed
42*6              252            5         2 existed
42*7              294            9         2,4 existed
42*8              336            3         6 existed 
42*9              378            7         3,8 existed

```
Looking at the above table under `digits` column you can find all the digits from `0` to `9`, Hence it required `9` multiples of `42` to get all the digits. So the depth of `42` is `9`. Write a function named `computeDepth` which computes the depth of its integer argument.Only positive numbers greater than zero will be passed as an input.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jaap, Jan, and Thijs are on a trip to the desert after having attended the ACM ICPC World Finals 2015 in Morocco. The trip included a camel ride, and after returning from the ride, their guide invited them to a big camel race in the evening. The camels they rode will also participate and it is customary to bet on the results of the race. 

One of the most interesting bets involves guessing the complete order in which the camels will finish the race. This bet offers the biggest return on your money, since it is also the one that is the hardest to get right.

Jaap, Jan, and Thijs have already placed their bets, but the race will not start until an hour from now, so they are getting bored. They started wondering how many pairs of camels they have put in the same order. If camel $c$ is before camel $d$ on Jaap’s, Jan’s and Thijs’ bet, it means that all three of them put $c$ and $d$ in the same order. Can you help them to calculate the number of pairs of camels for which this happened?

-----Input-----
The input consists of:
 - one line with an integer $n$ ($2\leq n \leq 200000$), the number of camels;
 - one line with $n$ integers $a_1, \ldots , a_ n$ ($1 \le a_ i \le n$ for all $i$), Jaap’s bet. Here $a_1$ is the camel in the first position of Jaap’s bet, $a_2$ is the camel in the second position, and so on;
 - one line with Jan’s bet, in the same format as Jaap’s bet;
 - one line with Thijs’ bet, in the same format as Jaap’s bet.

The camels are numbered $1, \dots , n$. Each camel appears exactly once in each bet.

-----Output-----
Output the number of pairs of camels that appear in the same order in all $3$ bets.

-----Examples-----
Sample Input:
3
3 2 1
1 2 3
1 2 3
Sample Output:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A positive (strictly greater than zero) integer is called round if it is of the form d00...0. In other words, a positive integer is round if all its digits except the leftmost (most significant) are equal to zero. In particular, all numbers from $1$ to $9$ (inclusive) are round.

For example, the following numbers are round: $4000$, $1$, $9$, $800$, $90$. The following numbers are not round: $110$, $707$, $222$, $1001$.

You are given a positive integer $n$ ($1 \le n \le 10^4$). Represent the number $n$ as a sum of round numbers using the minimum number of summands (addends). In other words, you need to represent the given number $n$ as a sum of the least number of terms, each of which is a round number.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

Each test case is a line containing an integer $n$ ($1 \le n \le 10^4$).


-----Output-----

Print $t$ answers to the test cases. Each answer must begin with an integer $k$ — the minimum number of summands. Next, $k$ terms must follow, each of which is a round number, and their sum is $n$. The terms can be printed in any order. If there are several answers, print any of them.


-----Example-----
Input
5
5009
7
9876
10000
10

Output
2
5000 9
1
7 
4
800 70 6 9000 
1
10000 
1
10

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