vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You run a delivery company and must deploy a fleet of vehicles to deliver goods to clients. All of the goods and delivery trucks are initially located at your warehouse. 

The road network consists of one-way streets between junctions. The warehouse and clients are all located at a junction. You know the driving time across each street.

You guarantee extremely fast shipping: the trucks start driving immediately at the start of the day and each client $i$ will receive the package at time $T_ i$ where $T_ i$ is the shortest possible driving time for a truck to go from the warehouse to the location of the client $i$.

What is the minimum number of trucks you have to deploy to ensure this guarantee is met? That is, what is the minimum number of trucks such that it is possible to give each truck a driving route so that every client $i$ is visited by some truck at time $T_ i$. Assume it takes no time to load the trucks with the appropriate goods at the start of the day, and it takes no time to drop goods off at a client once the truck arrives at the client. These goods are small enough that each truck can carry goods for as many clients as necessary.

-----Input-----
The input consists of a single test case. The first line of each test case consists of three numbers $N$, $M$, and $C$. Here $N$ denotes the number of junctions in the road network ($2 \leq N \leq 10^3$), $M$ denotes the number of streets ($1 \leq M \leq 10^5$), and $C$ denotes the number of clients ($1 \leq C \leq 300$, $C < N$).

The junctions are numbered $0$ to $N-1$. The warehouse is always at junction $0$. The second line consists of $C$ distinct integers between $1$ and $N-1$ indicating the junctions where the clients reside.

The rest of the input consists of $M$ lines, each containing integers $U,V,W$ where $0 \leq U,V \leq N-1$ and $U \neq V$. This indicates there is a one-way street from $U$ to $V$ with driving time $W$. Each street’s driving time $W$ satisfies $1 \leq W \leq 10^9$. It will always be possible to reach every client from the warehouse.

There will be at most one street from a vertex $U$ to another vertex $V$, but there may be streets from both $U$ to $V$ and from $V$ to $U$.

-----Output-----
Output a single integer that is the minimum number of vehicles required to ensure each client $i$ is visited at time $T_ i$ by some vehicle.

-----Explanations of Sample Inputs-----
In the first sample, one vehicle can follow the path $(0,1,2)$ and the other can follow $(0,3)$. In the second sample, the only solution is to use paths $(0,1)$, $(0,2)$, and $(0,3)$. In the final sample, one vehicle can follow $(0,1)$, another $(0,4,6)$, and the last one $(0,2,3,5,7)$.

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

Sample Input 2:
4 5 3
1 2 3
0 1 1
0 3 1
0 2 1
1 2 1
3 2 1
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array, arr[] of N elements such that every element of the array is an integer in the range 1 to n, the task is to find the sum of all the distinct elements of the array.
 
Example 1:
Input: N = 9
arr[] = {5, 1, 2, 4, 6, 7, 3, 6, 7}
Output: 28
Explanation: The distinct elements in 
the array are 1, 2, 3, 4, 5, 6, 7.
Example 2:
Input: N = 3, arr[] = {1, 1, 1}
Output: 1
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function sumOfDistinct() that takes array arr[]  and integer N as parameters and returns the sum of a distinct elements of the array.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers find the pair in the array with maximum GCD. Find the maximum possible GCD.
Example 1:
Input: N = 5, a[] = {1, 2, 3, 4, 5}
Output: 2
Explanation: Maximum gcd is GCD(2, 4)
= 2.
Ã¢â¬â¹Example 2:
Input: N = 3, a[] = {3, 5, 2}
Output: 1
Explanation: Maximum gcd is 1.
Your Task:  
Your task is to complete the function MaxGcd() which takes the N and list of N elements as inputs and returns the answer.
Expected Time Complexity: O(N * log N)
Expected Auxiliary Space: O(max(a_{i}))
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ a_{i} ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Marek and his schoolmates have just finished their studies at the university. They wanted to celebrate it with a game of paintball. After an hour of playing a very strange thing happened – everyone had exactly one bullet left. Marek, being a very curious person, wanted to know whether it’s possible that everyone will be hit exactly once provided nobody moves.

-----Task-----
You are given a description of the situation during a paintball game when every player has only one bullet. The description of the game consists of pairs of players who can see each other. If a player can see another player, he can fire at him. Your task is to find a target for each player such that everyone will be hit.

-----Input-----
The first line of input contains two space separated integers $N$ and $M$, satisfying $2\leq N\leq 1000$ and $0\leq M\leq 5000$, where $N$ is the number of players. Players are numbered $1, 2, \ldots , N$. $M$ lines follow, each line containing two space separated integers $A$ and $B$ ($1\leq A < B\leq N$), denoting that players $A$ and $B$ can see each other. Each pair of players appears at most once in the input.

-----Output-----
If there is no assignment of targets such that everyone will be hit, output Impossible. Otherwise output $N$ lines. The $i$-th line should contain the number of the target of the $i$-th player. If there is more than one solution, output any one.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A big company decided to launch a new series of rectangular displays, and decided that the display must have exactly n pixels. 

Your task is to determine the size of the rectangular display — the number of lines (rows) of pixels a and the number of columns of pixels b, so that:

  there are exactly n pixels on the display;  the number of rows does not exceed the number of columns, it means a ≤ b;  the difference b - a is as small as possible. 


-----Input-----

The first line contains the positive integer n (1 ≤ n ≤ 10^6) — the number of pixels display should have.


-----Output-----

Print two integers — the number of rows and columns on the display. 


-----Examples-----
Input
8

Output
2 4

Input
64

Output
8 8

Input
5

Output
1 5

Input
999999

Output
999 1001



-----Note-----

In the first example the minimum possible difference equals 2, so on the display should be 2 rows of 4 pixels.

In the second example the minimum possible difference equals 0, so on the display should be 8 rows of 8 pixels.

In the third example the minimum possible difference equals 4, so on the display should be 1 row of 5 pixels.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Leha decided to move to a quiet town Vičkopolis, because he was tired by living in Bankopolis. Upon arrival he immediately began to expand his network of hacked computers. During the week Leha managed to get access to n computers throughout the town. Incidentally all the computers, which were hacked by Leha, lie on the same straight line, due to the reason that there is the only one straight street in Vičkopolis.

Let's denote the coordinate system on this street. Besides let's number all the hacked computers with integers from 1 to n. So the i-th hacked computer is located at the point x_{i}. Moreover the coordinates of all computers are distinct. 

Leha is determined to have a little rest after a hard week. Therefore he is going to invite his friend Noora to a restaurant. However the girl agrees to go on a date with the only one condition: Leha have to solve a simple task.

Leha should calculate a sum of F(a) for all a, where a is a non-empty subset of the set, that consists of all hacked computers. Formally, let's denote A the set of all integers from 1 to n. Noora asks the hacker to find value of the expression $\sum_{a \subseteq A, a \neq \varnothing} F(a)$. Here F(a) is calculated as the maximum among the distances between all pairs of computers from the set a. Formally, $F(a) = \operatorname{max}_{i, j \in a}|x_{i} - x_{j}|$. Since the required sum can be quite large Noora asks to find it modulo 10^9 + 7.

Though, Leha is too tired. Consequently he is not able to solve this task. Help the hacker to attend a date.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 3·10^5) denoting the number of hacked computers.

The second line contains n integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 10^9) denoting the coordinates of hacked computers. It is guaranteed that all x_{i} are distinct.


-----Output-----

Print a single integer — the required sum modulo 10^9 + 7.


-----Examples-----
Input
2
4 7

Output
3

Input
3
4 3 1

Output
9



-----Note-----

There are three non-empty subsets in the first sample test:$\{4 \}$, $\{7 \}$ and $\{4,7 \}$. The first and the second subset increase the sum by 0 and the third subset increases the sum by 7 - 4 = 3. In total the answer is 0 + 0 + 3 = 3.

There are seven non-empty subsets in the second sample test. Among them only the following subsets increase the answer: $\{4,3 \}$, $\{4,1 \}$, $\{3,1 \}$, $\{4,3,1 \}$. In total the sum is (4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) = 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice has a cute cat. To keep her cat fit, Alice wants to design an exercising walk for her cat! 

Initially, Alice's cat is located in a cell (x,y) of an infinite grid. According to Alice's theory, cat needs to move: 

  * exactly a steps left: from (u,v) to (u-1,v); 
  * exactly b steps right: from (u,v) to (u+1,v); 
  * exactly c steps down: from (u,v) to (u,v-1); 
  * exactly d steps up: from (u,v) to (u,v+1). 



Note that the moves can be performed in an arbitrary order. For example, if the cat has to move 1 step left, 3 steps right and 2 steps down, then the walk right, down, left, right, right, down is valid.

Alice, however, is worrying that her cat might get lost if it moves far away from her. So she hopes that her cat is always in the area [x_1,x_2]× [y_1,y_2], i.e. for every cat's position (u,v) of a walk x_1 ≤ u ≤ x_2 and y_1 ≤ v ≤ y_2 holds.

Also, note that the cat can visit the same cell multiple times.

Can you help Alice find out if there exists a walk satisfying her wishes?

Formally, the walk should contain exactly a+b+c+d unit moves (a to the left, b to the right, c to the down, d to the up). Alice can do the moves in any order. Her current position (u, v) should always satisfy the constraints: x_1 ≤ u ≤ x_2, y_1 ≤ v ≤ y_2. The staring point is (x, y).

You are required to answer t test cases independently.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^3) — the number of testcases. 

The first line of each test case contains four integers a, b, c, d (0 ≤ a,b,c,d ≤ 10^8, a+b+c+d ≥ 1).

The second line of the test case contains six integers x, y, x_1, y_1, x_2, y_2 (-10^8 ≤ x_1≤ x ≤ x_2 ≤ 10^8, -10^8 ≤ y_1 ≤ y ≤ y_2 ≤ 10^8).

Output

For each test case, output "YES" in a separate line, if there exists a walk satisfying her wishes. Otherwise, output "NO" in a separate line. 

You can print each letter in any case (upper or lower).

Example

Input


6
3 2 2 2
0 0 -2 -2 2 2
3 1 4 1
0 0 -1 -1 1 1
1 1 1 1
1 1 1 1 1 1
0 0 0 1
0 0 0 0 0 1
5 1 1 1
0 0 -100 -100 0 100
1 1 5 1
0 0 -100 -100 100 0


Output


Yes
No
No
Yes
Yes
Yes

Note

In the first test case, one valid exercising walk is $$$(0,0)→ (-1,0) → (-2,0)→ (-2,1) → (-2,2)→ (-1,2)→(0,2)→ (0,1)→ (0,0) → (-1,0)$$$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given heights of consecutive buildings. You can move from the roof of a building to the roof of next adjacent building. You need to find the maximum number of consecutive steps you can put forward such that you gain an increase in altitude with each step.
Example 1:
Input:
N = 5
A[] = {1,2,2,3,2}
Output: 1
Explanation: 1, 2 or 2, 3 are the only consecutive 
buildings with increasing heights thus maximum number
of consecutive steps with increase in gain in altitude
would be 1 in both cases.
Example 2:
Input:
N = 4
A[] = {1,2,3,4}
Output: 3
Explanation: 1 to 2 to 3 to 4 is the jump of
length 3 to have maximum number of 
buildings with increasing heights, so maximum steps
with increasing altitude becomes 3.
Your Task:
The task is to complete the function maxStep() which takes an array A[] (denoting the heights of buildings) and its size N as inputs and returns the maximum number of steps to gain increase in altitude.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1). 
Constraints:
1 <= N <= 10^{6}
1 <= A_{i }<= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
“Sabotage!” exclaimed J.R. Diddly, president and founder of Diddly Widgets Inc. 

“Vandalism, perhaps. Nothing’s actually been damaged.” responded Robert Lackey, the chief accountant.

Both were staring up at the large counter suspended above the factory floor, a counter that had faithfully recorded the number of widgets that had come off the assembly line since the factory was opened. But someone had changed the number being displayed so that it formed...

“It’s a palindrome.” said Lackey. “It reads the same forwards as backwards.”

“What I don’t understand,” said Diddly, “is why our security guards didn’t catch the vandals during their regular sweeps. It must have taken them hours to click forward to this new number, one step at a time.”

“No.” replied Lackey. “Although we only advance the rightmost digit each time a new widget is built, it’s possible to spin any of the digits. With a little planning, this might have taken only a few seconds.”

-----Description-----
Consider a digital counter consisting of $k$ wheels, each showing a digit from 0 to 9. Each wheel is mounted so that it can advance to the next digit in a single step, e.g., from 3 to 4, or from 8 to 9.

It is also possible to advance from digit 9 to digit 0. However, when this happens, the wheel on its immediate left will also advance to the next digit automatically. This can have a cascade effect on multiple wheels to the left, but they all happen in a single step.

Given the current setting of the counter, find the smallest number of steps until one can reach a palindrome. The palindrome must respect leading zeros, e.g., 0011 is not a palindrome.

For example, for input 610, it takes four steps. This can be done by incrementing the 6 wheel four times, resulting in 010.

-----Input-----
Input will consist of single line containing an integer of $1$ to $40$ digits. The number of digits in the input is the number of wheels on the counter. Numbers may contain leading zeros.

-----Output-----
Print a single line of output containing one integer, the minimum number of wheel advances required to produce a palindrome.

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

Sample Input 2:
009990001
Sample Output 2:
3

Sample Input 3:
29998
Sample Output 3:
5

Sample Input 4:
610
Sample Output 4:
4

Sample Input 5:
981
Sample Output 5:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob has X rupees and goes to a market. The cost of apples is Rs. A per kg and the cost of oranges is Rs. B per kg.

Determine whether he can buy at least 1 kg each of apples and oranges.

------ Input Format ------ 

- The first line of input will contain an integer X, the amount of money Bob has.
- The second line of input contains two space-separated integers A and B, the cost per kg of apples and oranges respectively.

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

Print a single line containing Yes if Bob can buy the fruits and No otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings yes, Yes, yEs, and YES will all be treated as identical).

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

$1 ≤ X,A,B ≤ 10^{5}$

------ subtasks ------ 

Subtask 1 (100 points):
Original constraints.

----- Sample Input 1 ------ 
14 
2 2
----- Sample Output 1 ------ 
Yes
----- explanation 1 ------ 
The cost of buying $1$ kg each of apple and orange is $2+2 = 4$. Since Bob has more than $4$ rupees, the answer will be Yes.

----- Sample Input 2 ------ 
1 
1 1
----- Sample Output 2 ------ 
No
----- explanation 2 ------ 
Bob can only buy either $1$ kg of apples or $1$ kg of oranges with $1$ rupee, hence the answer is No.

----- Sample Input 3 ------ 
5
3 2

----- Sample Output 3 ------ 
Yes
----- explanation 3 ------ 
The cost of buying $1$ kg each of apple and orange is $3+2 = 5$. Since Bob has exactly $5$ rupees, the answer will be Yes.

----- Sample Input 4 ------ 
10000
5000 6000

----- Sample Output 4 ------ 
No
----- explanation 4 ------ 
The cost of buying $1$ kg each of apple and orange is $5000+6000 = 11000$. Since Bob has only $10000$ rupees, the answer will be No.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is Friday the 13th today, and even though you're a modern well-educated person, you can't help feeling a bit nervous about it. You decide to look for evidence against this superstition (or for it). As a first step, you recall all Fridays the 13th in your life and calculate how many of them were unusually bad — like that time when you decided to play a game on ZX Spectrum and ended up breaking your TV set. The problem is, you can't remember some Fridays, and you're not sure why — were they really that bad?

You have assembled a sequence of your recollections. Character "0" stands for a normal day, "1" — for a nasty one, and "?" means you have no idea what kind of day that was. Being a programmer, you decide to approximate these unknown days with independent random variables, which take value 1 with probability p, and 0 with probability (1 - p).

Given a string of your memories and the value of p, calculate out the expected value of average badness of your Fridays the 13th.

Input

The first line of the input contains a string s which represents your Fridays; s will contain between 1 and 50 characters, inclusive. Each character of s will be "0", "1" or "?".

The second line of the input contains a double p (0 ≤ p ≤ 1). Double p is given with at most 2 digits after the decimal point.

Output

Output the expected value of average badness of your Fridays with exactly 5 decimal places. Please, use standard mathematical rules when you are rounding an answer.

Examples

Input

?111?1??1
1.0


Output

1.00000


Input

01?10??10000
0.5


Output

0.37500

Note

In the first case, you're doomed. DOOMED! Sorry, just had to say that.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?
Example 1:
Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3
Example 2:
Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4
Example 3:
Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
Note: 1 <= N <= 10 ^ 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bad news came to Mike's village, some thieves stole a bunch of chocolates from the local factory! Horrible! 

Aside from loving sweet things, thieves from this area are known to be very greedy. So after a thief takes his number of chocolates for himself, the next thief will take exactly k times more than the previous one. The value of k (k > 1) is a secret integer known only to them. It is also known that each thief's bag can carry at most n chocolates (if they intend to take more, the deal is cancelled) and that there were exactly four thieves involved. 

Sadly, only the thieves know the value of n, but rumours say that the numbers of ways they could have taken the chocolates (for a fixed n, but not fixed k) is m. Two ways are considered different if one of the thieves (they should be numbered in the order they take chocolates) took different number of chocolates in them.

Mike want to track the thieves down, so he wants to know what their bags are and value of n will help him in that. Please find the smallest possible value of n or tell him that the rumors are false and there is no such n.

Input

The single line of input contains the integer m (1 ≤ m ≤ 1015) — the number of ways the thieves might steal the chocolates, as rumours say.

Output

Print the only integer n — the maximum amount of chocolates that thieves' bags can carry. If there are more than one n satisfying the rumors, print the smallest one.

If there is no such n for a false-rumoured m, print  - 1.

Examples

Input

1


Output

8


Input

8


Output

54


Input

10


Output

-1

Note

In the first sample case the smallest n that leads to exactly one way of stealing chocolates is n = 8, whereas the amounts of stealed chocolates are (1, 2, 4, 8) (the number of chocolates stolen by each of the thieves).

In the second sample case the smallest n that leads to exactly 8 ways is n = 54 with the possibilities: (1, 2, 4, 8), (1, 3, 9, 27), (2, 4, 8, 16), (2, 6, 18, 54), (3, 6, 12, 24), (4, 8, 16, 32), (5, 10, 20, 40), (6, 12, 24, 48).

There is no n leading to exactly 10 ways of stealing chocolates in the third sample case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a street with $n$ houses in a line, numbered from $1$ to $n$. The house $i$ is initially painted in color $c_i$. The street is considered beautiful if all houses are painted in the same color. Tom, the painter, is in charge of making the street beautiful. Tom's painting capacity is defined by an integer, let's call it $k$.

On one day, Tom can do the following repainting process that consists of two steps:

He chooses two integers $l$ and $r$ such that $ 1 \le l \le r \le n $ and $ r - l + 1 = k $.

For each house $i$ such that $l \le i \le r$, he can either repaint it with any color he wants, or ignore it and let it keep its current color.

Note that in the same day Tom can use different colors to repaint different houses.

Tom wants to know the minimum number of days needed to repaint the street so that it becomes beautiful.


-----Input-----

The first line of input contains a single integer $t$ ($ 1 \le t \le 10^4$), the number of test cases. Description of test cases follows.

In the first line of a test case description there are two integers $n$ and $k$ ($1 \le k \le n \le 10^5$).

The second line contains $n$ space-separated integers. The $i$-th of these integers represents $c_i$ ($1 \le c_i \le 100$), the color which house $i$ is initially painted in.

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


-----Output-----

Print $t$ lines, each with one integer: the minimum number of days Tom needs to make the street beautiful for each test case.


-----Examples-----

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


-----Note-----

In the first test case Tom should paint houses 1 and 2 in the first day in color 2, houses 5 and 6 in the second day in color 2, and the last house in color 2 on the third day.

In the second test case Tom can, for example, spend 6 days to paint houses 1, 2, 4, 5, 6, 7 in color 3.

In the third test case Tom can paint the first house in the first day and houses 6, 7, and 8 in the second day in color 3.

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