vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We guessed a permutation $p$ consisting of $n$ integers. The permutation of length $n$ is the array of length $n$ where each element from $1$ to $n$ appears exactly once. This permutation is a secret for you.

For each position $r$ from $2$ to $n$ we chose some other index $l$ ($l < r$) and gave you the segment $p_l, p_{l + 1}, \dots, p_r$ in sorted order (i.e. we rearranged the elements of this segment in a way that the elements of this segment are sorted). Thus, you are given exactly $n-1$ segments of the initial permutation but elements inside each segment are sorted. The segments are given to you in random order.

For example, if the secret permutation is $p=[3, 1, 4, 6, 2, 5]$ then the possible given set of segments can be:  $[2, 5, 6]$  $[4, 6]$  $[1, 3, 4]$  $[1, 3]$  $[1, 2, 4, 6]$ 

Your task is to find any suitable permutation (i.e. any permutation corresponding to the given input data). It is guaranteed that the input data corresponds to some permutation (i.e. such permutation exists).

You have to answer $t$ independent test cases.


-----Input-----

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

The first line of the test case contains one integer $n$ ($2 \le n \le 200$) — the length of the permutation.

The next $n-1$ lines describe given segments.

The $i$-th line contains the description of the $i$-th segment. The line starts with the integer $k_i$ ($2 \le k_i \le n$) — the length of the $i$-th segment. Then $k_i$ integers follow. All integers in a line are distinct, sorted in ascending order, between $1$ and $n$, inclusive.

It is guaranteed that the required $p$ exists for each test case.

It is also guaranteed that the sum of $n$ over all test cases does not exceed $200$ ($\sum n \le 200$).


-----Output-----

For each test case, print the answer: $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ should be distinct) — any suitable permutation (i.e. any permutation corresponding to the test case input).


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

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine you start on the 5th floor of a building, then travel down to the 2nd floor, then back up to the 8th floor. You have travelled a total of 3 + 6 = 9 floors of distance.

Given an array representing a series of floors you must reach by elevator, return an integer representing the total distance travelled for visiting each floor in the array in order. 

```
// simple examples
elevatorDistance([5,2,8]) = 9
elevatorDistance([1,2,3]) = 2
elevatorDistance([7,1,7,1]) = 18

// if two consecutive floors are the same,
//distance travelled between them is 0
elevatorDistance([3,3]) = 0
```

Array will always contain at least 2 floors. Random tests will contain 2-20 elements in array, and floor values between 0 and 30.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The arrival times of N trains are given in the format hours : minutes : seconds. However for the sake of simplicity the time is considered only in seconds format i.e., 3600hours + 60minutes + seconds (Let's say this x). Now if x is a prime number, the halt for the train at the station is 5 minutes, if it's an odd number the halt is 3 minutes else the halt is 2 minutes. Now your task is find the minimum number of platforms required to accomodate all the arriving  trains in a station at any time.

Constraint:

1 ≤ N ≤ 100000

0 ≤ H ≤ 23

0 ≤ M,S ≤ 59

Input:

First line contains a number N

Next N lines contains 3 space separated integers H M S

Output:

Single integer containing the minimum of platforms needed to accomodate the trains

SAMPLE INPUT
5
11 57 9
20 25 53
8 41 3
16 58 30
21 47 8

SAMPLE OUTPUT
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sitting in a station waiting room, Joisino is gazing at her train ticket.
The ticket is numbered with four digits A, B, C and D in this order, each between 0 and 9 (inclusive).
In the formula A op1 B op2 C op3 D = 7, replace each of the symbols op1, op2 and op3 with + or - so that the formula holds.
The given input guarantees that there is a solution. If there are multiple solutions, any of them will be accepted.

-----Constraints-----
 - 0≤A,B,C,D≤9
 - All input values are integers.
 - It is guaranteed that there is a solution.

-----Input-----
Input is given from Standard Input in the following format:
ABCD

-----Output-----
Print the formula you made, including the part =7.
Use the signs + and -.
Do not print a space between a digit and a sign.

-----Sample Input-----
1222

-----Sample Output-----
1+2+2+2=7

This is the only valid solution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya had three strings $a$, $b$ and $s$, which consist of lowercase English letters. The lengths of strings $a$ and $b$ are equal to $n$, the length of the string $s$ is equal to $m$. 

Vasya decided to choose a substring of the string $a$, then choose a substring of the string $b$ and concatenate them. Formally, he chooses a segment $[l_1, r_1]$ ($1 \leq l_1 \leq r_1 \leq n$) and a segment $[l_2, r_2]$ ($1 \leq l_2 \leq r_2 \leq n$), and after concatenation he obtains a string $a[l_1, r_1] + b[l_2, r_2] = a_{l_1} a_{l_1 + 1} \ldots a_{r_1} b_{l_2} b_{l_2 + 1} \ldots b_{r_2}$.

Now, Vasya is interested in counting number of ways to choose those segments adhering to the following conditions:

  segments $[l_1, r_1]$ and $[l_2, r_2]$ have non-empty intersection, i.e. there exists at least one integer $x$, such that $l_1 \leq x \leq r_1$ and $l_2 \leq x \leq r_2$;  the string $a[l_1, r_1] + b[l_2, r_2]$ is equal to the string $s$. 


-----Input-----

The first line contains integers $n$ and $m$ ($1 \leq n \leq 500\,000, 2 \leq m \leq 2 \cdot n$) — the length of strings $a$ and $b$ and the length of the string $s$.

The next three lines contain strings $a$, $b$ and $s$, respectively. The length of the strings $a$ and $b$ is $n$, while the length of the string $s$ is $m$.

All strings consist of lowercase English letters.


-----Output-----

Print one integer — the number of ways to choose a pair of segments, which satisfy Vasya's conditions.


-----Examples-----
Input
6 5
aabbaa
baaaab
aaaaa

Output
4

Input
5 4
azaza
zazaz
azaz

Output
11

Input
9 12
abcabcabc
xyzxyzxyz
abcabcayzxyz

Output
2



-----Note-----

Let's list all the pairs of segments that Vasya could choose in the first example:

  $[2, 2]$ and $[2, 5]$;  $[1, 2]$ and $[2, 4]$;  $[5, 5]$ and $[2, 5]$;  $[5, 6]$ and $[3, 5]$;

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya plays the Plane of Tanks.

Tanks are described with the following attributes: 

  * the number of hit points; 
  * the interval between two gun shots (the time required to recharge the gun); 
  * the probability that the gun shot will not pierce armor of the enemy tank; 
  * the damage to the enemy's tank. 



The gun damage is described with a segment [l, r], where l and r are integer numbers. The potential gun damage x is chosen with equal probability among all integer numbers of the segment [l, r]. If the shot pierces the armor of an enemy's tank then the enemy loses x hit points. If the number of hit points becomes non-positive then the enemy tank is considered destroyed. 

It is possible that the shot does not pierce the armor of a tank. In this case the number of hit points doesn't change. The probability that the armor will not be pierced is considered as the shooting tank attribute and does not depend on players' behavior.

The victory is near and there is only one enemy tank left. Vasya is ready for the battle — one more battle between the Good and the Evil is inevitable! Two enemies saw each other and each of them fired a shot at the same moment... The last battle has begun! Help Vasya to determine what is the probability that he will win the battle by destroying the enemy tank? 

If both tanks are destroyed (after simultaneous shots), then Vasya is considered a winner. You can assume that each player fires a shot just after the gun recharge and each tank has infinite number of ammo.

Input

The first line contains five integer numbers separated with spaces describing Vasya's tank: the number of hit points hp (10 ≤ hp ≤ 200), the interval between two shots dt (1 ≤ dt ≤ 30), gun damage segment l and r (10 ≤ l ≤ r ≤ 100), the probability that the enemy's tank armor will not be pierced p (0 ≤ p ≤ 100) (percents).

The second line describes the tank of Vasya's enemy in the same format.

Output

Print the only number with absolute or relative error no more than 10 - 4 — probability of Vasya's victory.

Examples

Input

100 3 50 50 0
100 3 50 50 0


Output

1.000000


Input

100 3 50 50 0
100 2 48 50 0


Output

0.888889


Input

100 3 50 50 0
100 1 50 50 50


Output

0.500000

Note

In the first example both tanks are destroyed at once after the second shot. The probability of destroying the enemy tank is 1.

In the second example Vasya's enemy tank fires the second shot before Vasya's tank, but has no time for the third shot. In order to destroy Vasya's tank it is necessary to fire two shots with damage 50. The probability of that event is <image> = <image>. Otherwise, Vasya wins.

In the third example Vasya's enemy tank fires three shots with probability of armor piercing 0.5. In order to destroy Vasya's tank it is necessary that at least 2 of 3 shots pierce the armor of Vasya's tank. The probability of this event is 0.5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine that Alice is playing a card game with her friend Bob. They both have exactly 8 cards and there is an integer on each card, ranging from 0 to 4. In each round, Alice or Bob in turns choose two cards from different players, let them be a and b, where a is the number on the player's card, and b is the number on the opponent's card. It is necessary that a ⋅ b ≠ 0. Then they calculate c = (a + b) mod 5 and replace the number a with c. The player who ends up with numbers on all 8 cards being 0, wins.

Now Alice wants to know who wins in some situations. She will give you her cards' numbers, Bob's cards' numbers and the person playing the first round. Your task is to determine who wins if both of them choose the best operation in their rounds.

Input

The first line contains one positive integer T (1 ≤ T ≤ 100 000), denoting the number of situations you need to consider.

The following lines describe those T situations. For each situation:

  * The first line contains a non-negative integer f (0 ≤ f ≤ 1), where f = 0 means that Alice plays first and f = 1 means Bob plays first. 
  * The second line contains 8 non-negative integers a_1, a_2, …, a_8 (0 ≤ a_i ≤ 4), describing Alice's cards. 
  * The third line contains 8 non-negative integers b_1, b_2, …, b_8 (0 ≤ b_i ≤ 4), describing Bob's cards. 



We guarantee that if f=0, we have ∑_{i=1}^{8}a_i ≠ 0. Also when f=1, ∑_{i=1}^{8}b_i ≠ 0 holds.

Output

Output T lines. For each situation, determine who wins. Output 

  * "Alice" (without quotes) if Alice wins. 
  * "Bob" (without quotes) if Bob wins. 
  * "Deal" (without quotes) if it gets into a deal, i.e. no one wins. 

Example

Input

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


Output

Alice
Bob
Alice
Deal

Note

In the first situation, Alice has all her numbers 0. So she wins immediately.

In the second situation, Bob picks the numbers 4 and 1. Because we have (4 + 1) mod 5 = 0, Bob wins after this operation.

In the third situation, Alice picks the numbers 1 and 4. She wins after this operation.

In the fourth situation, we can prove that it falls into a loop.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little X used to play a card game called "24 Game", but recently he has found it too easy. So he invented a new game.

Initially you have a sequence of n integers: 1, 2, ..., n. In a single step, you can pick two of them, let's denote them a and b, erase them from the sequence, and append to the sequence either a + b, or a - b, or a × b.

After n - 1 steps there is only one number left. Can you make this number equal to 24?

Input

The first line contains a single integer n (1 ≤ n ≤ 105).

Output

If it's possible, print "YES" in the first line. Otherwise, print "NO" (without the quotes).

If there is a way to obtain 24 as the result number, in the following n - 1 lines print the required operations an operation per line. Each operation should be in form: "a op b = c". Where a and b are the numbers you've picked at this operation; op is either "+", or "-", or "*"; c is the result of corresponding operation. Note, that the absolute value of c mustn't be greater than 1018. The result of the last operation must be equal to 24. Separate operator sign and equality sign from numbers with spaces.

If there are multiple valid answers, you may print any of them.

Examples

Input

1


Output

NO


Input

8


Output

YES
8 * 7 = 56
6 * 5 = 30
3 - 4 = -1
1 - 2 = -1
30 - -1 = 31
56 - 31 = 25
25 + -1 = 24

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence b_1, b_2, …, b_n. Find the lexicographically minimal permutation a_1, a_2, …, a_{2n} such that b_i = min(a_{2i-1}, a_{2i}), or determine that it is impossible.

Input

Each test contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 100).

The first line of each test case consists of one integer n — the number of elements in the sequence b (1 ≤ n ≤ 100).

The second line of each test case consists of n different integers b_1, …, b_n — elements of the sequence b (1 ≤ b_i ≤ 2n).

It is guaranteed that the sum of n by all test cases doesn't exceed 100.

Output

For each test case, if there is no appropriate permutation, print one number -1.

Otherwise, print 2n integers a_1, …, a_{2n} — required lexicographically minimal permutation of numbers from 1 to 2n.

Example

Input


5
1
1
2
4 1
3
4 1 3
4
2 3 4 5
5
1 5 7 2 8


Output


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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In my town ,there live a coder named Chef . He is a cool programmer . One day , he participate in a programming contest ,the contest give him only one problem . If he can’t solve the problem ,the problem setter will kill him . But the round allow you to help Chef. Can you save the life of Chef from problem setter ? :p
You are given two point of a straightline in X and Y axis and they are A(x1 , y1) and B(x2 ,y2) . Problem setter will give you another point C(x3 , y3) . If C exist in AB straightline ,then print “YES” . Otherwise ,print “NO” in first line and print the minimum distance from C to AB straightline in second line .
Please , save the life of Chef .
Note : It is not possible that A and B point is similar .

-----Input:-----
The first line of the input contains a single integer t (1≤t≤100) — the number of test cases .
Each test case starts with four integers( x1, y1 , x2 , y2 ) in first line .
Next line contains a single number q ,the number of queries . Each query contains two integers ( x3 ,y3 )

-----Output:-----
Print , q number of “YES” or “NO” (as it mentioned above) in each test case .For every test case , print “Test case : i ” ( 1<= i <=T )

-----Constraints-----
-1000 <=  x1 , y1 , x2 , y2 , x3 , y3 <= 1000

-----Sample Input:-----
2
3  5  6  5
2
4  5
6  8
3  4  7  10
1
7  4

-----Sample Output:-----
Test case : 1
YES
NO
3.000000
Test case : 2
NO
3.328201

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

Time Limit: 3 seconds

Memory Limit: 256 megabytes

Problem Description:
Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya got an array consisting of *n* numbers, it is the gift for his birthday. Now he wants to sort it in the non-decreasing order. However, a usual sorting is boring to perform, that's why Petya invented the following limitation: one can swap any two numbers but only if at least one of them is lucky. Your task is to sort the array according to the specified limitation. Find any possible sequence of the swaps (the number of operations in the sequence should not exceed 2*n*).

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=105) — the number of elements in the array. The second line contains *n* positive integers, not exceeding 109 — the array that needs to be sorted in the non-decreasing order.

Output Specification:
On the first line print number *k* (0<=≤<=*k*<=≤<=2*n*) — the number of the swaps in the sorting. On the following *k* lines print one pair of distinct numbers (a pair per line) — the indexes of elements to swap. The numbers in the array are numbered starting from 1. If it is impossible to sort the given sequence, print the single number -1.

If there are several solutions, output any. Note that you don't have to minimize *k*. Any sorting with no more than 2*n* swaps is accepted.

Demo Input:
['2\n4 7\n', '3\n4 2 1\n', '7\n77 66 55 44 33 22 11\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ishaan is playing with strings these days. He has found a new string. He wants to modify it as per the following rules to make it valid:
	The string should not have three consecutive same characters (Refer example for explanation).
	He can add any number of characters anywhere in the string. 
Find the minimum number of characters which Ishaan must insert in the string to make it valid.
Example 1:
Input:
S = aabbbcc
Output: 1
Explanation: In aabbbcc 3 b's occur
consecutively, we add a 'd',and Hence,
output will be aabbdbcc.
Example 1:
Input:
S = aaaaa
Output: 2
Explanation:  In aaaaa 5 a's occur
consecutively,we need to add 2 'b', and
Hence, the output will be aababaa.
Your Task:
This is a function problem. You only need to complete the function modified() that returns the answer.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints : 
1 <= Length of S <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Emuskald is an avid horticulturist and owns the world's longest greenhouse — it is effectively infinite in length.

Over the years Emuskald has cultivated n plants in his greenhouse, of m different plant species numbered from 1 to m. His greenhouse is very narrow and can be viewed as an infinite line, with each plant occupying a single point on that line.

Emuskald has discovered that each species thrives at a different temperature, so he wants to arrange m - 1 borders that would divide the greenhouse into m sections numbered from 1 to m from left to right with each section housing a single species. He is free to place the borders, but in the end all of the i-th species plants must reside in i-th section from the left.

Of course, it is not always possible to place the borders in such way, so Emuskald needs to replant some of his plants. He can remove each plant from its position and place it anywhere in the greenhouse (at any real coordinate) with no plant already in it. Since replanting is a lot of stress for the plants, help Emuskald find the minimum number of plants he has to replant to be able to place the borders.


-----Input-----

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 5000, n ≥ m), the number of plants and the number of different species. Each of the following n lines contain two space-separated numbers: one integer number s_{i} (1 ≤ s_{i} ≤ m), and one real number x_{i} (0 ≤ x_{i} ≤ 10^9), the species and position of the i-th plant. Each x_{i} will contain no more than 6 digits after the decimal point.

It is guaranteed that all x_{i} are different; there is at least one plant of each species; the plants are given in order "from left to the right", that is in the ascending order of their x_{i} coordinates (x_{i} < x_{i} + 1, 1 ≤ i < n).


-----Output-----

Output a single integer — the minimum number of plants to be replanted.


-----Examples-----
Input
3 2
2 1
1 2.0
1 3.100

Output
1

Input
3 3
1 5.0
2 5.5
3 6.0

Output
0

Input
6 3
1 14.284235
2 17.921382
1 20.328172
3 20.842331
1 25.790145
1 27.204125

Output
2



-----Note-----

In the first test case, Emuskald can replant the first plant to the right of the last plant, so the answer is 1.

In the second test case, the species are already in the correct order, so no replanting is needed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The local transport authority is organizing an online picture contest.
Participants must take pictures of transport means in an original way, and then post the picture on Instagram using a specific ```hashtag```.

The local transport authority needs your help. They want you to take out the ```hashtag``` from the posted message. Your task is to implement the function

```python
def omit_hashtag(message, hashtag):
```

## Examples 

```
* ("Sunny day! #lta #vvv", "#lta") -> "Sunny day!  #vvv" (notice the double space)
* ("#lta #picture_contest", "#lta") -> " #picture_contest"
```

## Notes

* When multiple occurences of the hashtag are found, delete only the first one.

* In C, you should modify the ```message```, as the function returns a void type. In Python, you should return the answer.

* There can be erroneous messages where the hashtag isn't present. The message should in this case stay untouched.

* The hashtag only consists of alphanumeric characters.

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