vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Big Chandan is a dire lover of Biryani, especially Old Monk's Biryani. Today, he went over to have some of it. To his surprise, the waiter turns out be to be a coding geek and refuses to serves him unless Chandu solves his two- arrays problem, stated as:  

Given two non-increasing array of integers A,B  i.e A[i] ≥ A[i+1] and B[i] ≥ B[i+1] and for all i, 0 ≤ i < n-1.  

The monkiness of two numbers is given by: M (A[i],B[j]) = j - i
 , if j ≥i and B[j] ≥ A[i], or 0 otherwise. 

Find the monkiness of the two arrays, that is given by: M (A,B)=  max (M(A[i],B[j])) for 0≤ i, j< n-1.

Input Format:
The first line contains an integer, tc, denoting the number of test cases. The next line contains an integer, n, denoting the size of the two arrays. The size of both the arrays will be equal. After that line, the next line contains n integers denoting the numbers in the array A, and in the next line, there will be n numbers denoting the numbers in the array B.

Output format:
Print the monkiness of the two arrays.

Constraints:
1 ≤ Test Cases ≤ 50
1 ≤ N ≤ 10^5
1 ≤ Ai, Bi ≤ 10^12

SAMPLE INPUT
2
9
7 7 3 3 3 2 2 2 1
8 8 7 7 5 5 4 3 2
6
6 5 4 4 4 4
2 2 2 2 2 2

SAMPLE OUTPUT
5
0

Explanation

In the first case, we can see that 3 in the second array is the number which is equal to the 3 in the first array, and the difference between their positions is 5. So, the answer is 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On a shiny day, kindergarten kids are going to the picnic. All the kids bought some candies with them. As all of them bought different number of candies, soon quarrel started among them. Teacher decided to collect all the candies. Soon a huge heap of candies is created on the table. Teacher now decided to give equal number of candies to all, but wait. Shinchan was a curious boy, he wants know whether it is possible to do so or not? And after equal distribution how many candies does teacher will have from the remaining candies?

INPUT:
Line 1: number of test cases. T.
Line 2: in each T line you are given number of kids N.
Line 3: space separated number of candies each kid have, i.e. X.

OUTPUT
Line 1: if it is possible print “YES” , if it not possible to divide candies print “NO”.
Line 2: space separated two numbers, number of candies each kid get and candies teacher get.

CONSTRAINTS:
1 ≤ T ≤ 10;
2 ≤ N ≤ 1000;
1 ≤ X ≤ 10^10;

SAMPLE INPUT
2
4
10 12 14 8

5
2 3 5 12 2

SAMPLE OUTPUT
YES
11 0
NO
4 4

Explanation

In Case 1:
total candies = 44
each student will get 11 candies , and teacher will get 0, so ans is YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You’ve just entered a Japanese-style pub, or an izakaya in Japanese, for a drinking party (called nomi-kai) with your dear friends.

Now you are to make orders for glasses of hard and soft drink as requested by the participants. But unfortunately, most staffs in typical izakayas are part-time workers; they are not used to their work so they make mistakes at a certain probability for each order.

You are worrying about such mistakes. Today is a happy day for the participants, the dearest friends of yours.

Your task is to write a program calculating the probability at which the izakaya staff brings correct drinks for the entire orders. Cases in which the staff’s mistakes result in a correct delivery should be counted into the probability, since those cases are acceptable for you.



Input

The input consists of multiple test cases. Each test case begins with a line containing an interger N (1 ≤ N ≤ 8). The integer N indicates the number of kinds of drinks available in the izakaya.

The following N lines specify the probabilities for the drinks in the format shown below.


p11 p12 . . . p1N
p21 p22 . . . p2N
...
pN1 pN2 . . . pNN


Each real number pij indicates the probability where the staff delivers a glass of the drink j for an order of the drink i. It holds that pij ≥ 0 and pi1 + pi2 + . . . + piN = 1 for 1 ≤ i, j ≤ N. At the end of each test case, a line which contains N comes. The i-th integer ni represents the number of orders for the drink i by the participants (0 ≤ ni ≤ 4).

The last test case is followed by a line containing a zero.

Output

For Each test case, print a line containing the test case number (beginning with 1) followed by the natural logarithm of the probability where the staff brings correct drinks for the entire orders. Print the results with eight digits to the right of the decimal point. If the staff cannot bring correct drinks in any case, print “-INFINITY” instead. Use the format of the sample output.

Example

Input

3
0.7 0.1 0.2
0.1 0.8 0.1
0.0 0.0 1.0
4 3 2
8
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
2 2 2 2 2 2 2 2
2
1 0
1 0
2 2
0


Output

Case 1: -1.89723999
Case 2: -8.14438201
Case 3: -INFINITY

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's IPL time and as usual RCB are finding it tough to qualify for playoffs.  RCB needs a minimum of $X$ more points to qualify for playoffs in their remaining $Y$ matches. A win, tie and loss in a match will yield $2,1,0$ points respectively to a team.

You being a true RCB supporter want to find the minimum number of matches RCB needs to win to qualify for playoffs. It is guaranteed that RCB will qualify for playoffs if they win all their remaining $Y$ matches.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains of a single line of input, two space separated integers $X, Y$

------ Output: ------

For each testcase, output in a single line the minimum number of matches RCB must win to qualify for playoffs.

------ Constraints : ------

$1 ≤ T ≤ 10000$
$1 ≤ X ≤ 100$
$1 ≤ Y ≤ 100$
$1 ≤ X ≤ 2\cdot Y$

----- Sample Input 1 ------ 
2
10 5
1 5
----- Sample Output 1 ------ 
5
0
----- explanation 1 ------ 
- In first case $X=10$ and $Y=5$, so RCB needs $10$ points from remaining $5$ matches to qualify for playoffs. It is only possible if they win all their remaining $5$ matches.
- In second case $X=1$ and $Y=5$, so RCB needs $1$ points from their remaining $5$ matches to qualify for playoffs. It can be done if they tie any one of their $5$ matches and lose the remaining $4$. So they need to win $0$ matches.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice, Bob, and Charlie are contributing to buy a Netflix subscription. However, Netfix allows only two users to share a subscription.

Given that Alice, Bob, and Charlie have A, B, and C rupees respectively and a Netflix subscription costs X rupees, find whether any two of them can contribute to buy a subscription.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case contains four space-separated integers A, B, C, and X — the amount that Alice, Bob, and Charlie have, and the cost of a Netflix subscription respectively.

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

For each test case, output YES, if any two of Alice, Bob, and Charlie can contribute to buy a Netflix subscription or NO otherwise.

You may print each character in uppercase or lowercase. For example, NO, no, No, and nO are all considered identical.

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

$1 ≤ T ≤ 1000$
$1 ≤ A, B, C, X ≤ 100$

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

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
4
1 1 1 3
2 3 1 5
4 2 3 4
2 1 4 7

----- Sample Output 1 ------ 
NO
YES
YES
NO

----- explanation 1 ------ 
Test case $1$: No two people can contribute to collect enough money to buy a Netflix subscription.

Test case $2$: Alice and Bob can contribute and collect a total of $5$ rupees which is enough to buy a Netflix subscription of $5$ rupees.

Test case $3$: One possible way is, Bob and Charlie can contribute and collect a total of $5$ rupees which is enough to buy a Netflix subscription of $4$ rupees.  
Note that there are other possible ways as well.

Test case $4$: No two people can contribute to collect enough money to buy a Netflix subscription.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a city where the ground is a square of regular hexagons. Each square is represented by two integers as shown in the figure below.

<image>

The cat is about to go to the square (0, 0). The mischievous black rabbit knew this and decided to get in the way of the cat.

The black rabbit can jump to the square with the cat and block one of the six squares around it or two adjacent squares. The cat chooses one of the six surrounding squares that is not blocked. Each time the cat moves, the black rabbit can chase the cat and block again. When the black rabbit moves, the original block is released. The figure below shows the state of the block.

<image>

There are several squares in this city that are territories of cats. The territory is represented as a merger of n squares that form a regular hexagonal circumference. Black rabbits can enter the territory of cats. However, it cannot be blocked. That is, the cat can move freely within the territory.

There are k possible starting points for cats, which are masses (xi, yi) (1 ≤ i ≤ k). For each, the cat always reaches its destination (0, 0), or the black rabbit works well. Determine if the cat can reach its destination by interfering.



Input

Line 1: 1 ≤ n ≤ 40 000
Lines 2 ~ (n + 1): Vertices of a regular hexagon representing the territory of a cat
Lines (n + 2): 1 ≤ k ≤ 40 000
(n + 3) ~ (n + k + 2) Line: Cat's starting point xi, yi

-1 000 000 000 ≤ (each coordinate) ≤ 1 000 000 000

A regular hexagon representing a cat's territory is given the positions of the six vertices counterclockwise.

Output

For each candidate starting point, "YES" if the cat can always reach the destination (0,0), or "NO" if the cat does not reach the destination if the black rabbit interferes well, line by line. Output.

Example

Input

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


Output

YES
NO
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two strings s and t consisting of small Latin letters, string s can also contain '?' characters. 

Suitability of string s is calculated by following metric:

Any two letters can be swapped positions, these operations can be performed arbitrary number of times over any pair of positions. Among all resulting strings s, you choose the one with the largest number of non-intersecting occurrences of string t. Suitability is this number of occurrences.

You should replace all '?' characters with small Latin letters in such a way that the suitability of string s is maximal.


-----Input-----

The first line contains string s (1 ≤ |s| ≤ 10^6).

The second line contains string t (1 ≤ |t| ≤ 10^6).


-----Output-----

Print string s with '?' replaced with small Latin letters in such a way that suitability of that string is maximal.

If there are multiple strings with maximal suitability then print any of them.


-----Examples-----
Input
?aa?
ab

Output
baab

Input
??b?
za

Output
azbz

Input
abcd
abacaba

Output
abcd



-----Note-----

In the first example string "baab" can be transformed to "abab" with swaps, this one has suitability of 2. That means that string "baab" also has suitability of 2.

In the second example maximal suitability you can achieve is 1 and there are several dozens of such strings, "azbz" is just one of them.

In the third example there are no '?' characters and the suitability of the string is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two arrays $a$ and $b$, each consisting of $n$ positive integers, and an integer $x$. Please determine if one can rearrange the elements of $b$ so that $a_i + b_i \leq x$ holds for each $i$ ($1 \le i \le n$).


-----Input-----

The first line of input contains one integer $t$ ($1 \leq t \leq 100$) — the number of test cases. $t$ blocks follow, each describing an individual test case.

The first line of each test case contains two integers $n$ and $x$ ($1 \leq n \leq 50$; $1 \leq x \leq 1000$) — the length of arrays $a$ and $b$, and the parameter $x$, described in the problem statement.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_1 \le a_2 \le \dots \le a_n \leq x$) — the elements of array $a$ in non-descending order.

The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_1 \le b_2 \le \dots \le b_n \leq x$) — the elements of array $b$ in non-descending order.

Test cases are separated by a blank line.


-----Output-----

For each test case print Yes if one can rearrange the corresponding array $b$ so that $a_i + b_i \leq x$ holds for each $i$ ($1 \le i \le n$) or No otherwise.

Each character can be printed in any case.


-----Example-----
Input
4
3 4
1 2 3
1 1 2

2 6
1 4
2 5

4 4
1 2 3 4
1 2 3 4

1 5
5
5

Output
Yes
Yes
No
No



-----Note-----

In the first test case, one can rearrange $b$ so it'll look like $[1, 2, 1]$. In this case, $1 + 1 \leq 4$; $2 + 2 \leq 4$; $3 + 1 \leq 4$.

In the second test case, one can set $b$ to $[5, 2]$, then $1 + 5 \leq 6$; $4 + 2 \leq 6$.

In the third test case, no matter how one shuffles array $b$, $a_4 + b_4 = 4 + b_4 > 4$.

In the fourth test case, there is only one rearrangement of array $b$ and it doesn't satisfy the condition since $5 + 5 > 5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Most of us like playing video games. Benni prefers to play the video game Digbuild. Digbuild is primarily about surviving for as long as possible. In the game almost everything is possible. You can climb mountains, build castles, and fish, just to name a few options. The gameworld consists of large cubes, all the same size, whose corners are always in integral coordinates in three dimensional space. The player can both break these cubes (or blocks) and place blocks next to ones already there. There are also other items in the gameworld, auxiliary to these blocks. A few examples would be beds to sleep on, frames for photographs, and torches to light the world.

Benni isn’t a fan of building. He’d much rather dig tunnels in the ground. Benni always digs his tunnels horizontally and parallel to the $x$-axis of the gameworld. They are also always $3$ blocks high and $3$ blocks wide. Benni has just finished digging an $n$ block long tunnel and decided to go get a glass of water. When he sits down again to play some more he notices the tunnels are rather poorly lit. He realizes he has to place some torches on the floor of his tunnel to light the up. Benni is rather insistent on his tunnel not becoming ugly so he has to places the torches strategically. Benni considers his tunnel to be ugly if two blocks sharing a face both hold a torch.

In Digbuild you can only place one torch per block. Benni is so against his tunnel being ugly he’d rather have them unlit completely (i.e. not placing a torch is not considered ugly).

In how many different ways can Benni place the torches such that his tunnel doesn’t become ugly? Since this number may be rather large you are asked to find the answer $\mod 10^9 + 7$.

-----Input-----
The first and only line in the input contains the integer $1 \leq n \leq 10^{18}$.

-----Output-----
The only line in the output should contain the number of non-ugly torch arrangements in an $n$ block long tunnel, $\mod 10^9 + 7$.

-----Examples-----
Sample Input 1:
1
Sample Output 1:
5

Sample Input 2:
4
Sample Output 2:
227

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Fox and Box Accumulation

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fox Ciel has *n* boxes in her room. They have the same size and weight, but they might have different strength. The *i*-th box can hold at most *x**i* boxes on its top (we'll call *x**i* the strength of the box). 

Since all the boxes have the same size, Ciel cannot put more than one box directly on the top of some box. For example, imagine Ciel has three boxes: the first has strength 2, the second has strength 1 and the third has strength 1. She cannot put the second and the third box simultaneously directly on the top of the first one. But she can put the second box directly on the top of the first one, and then the third box directly on the top of the second one. We will call such a construction of boxes a pile.

Fox Ciel wants to construct piles from all the boxes. Each pile will contain some boxes from top to bottom, and there cannot be more than *x**i* boxes on the top of *i*-th box. What is the minimal number of piles she needs to construct?

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=100). The next line contains *n* integers *x*1,<=*x*2,<=...,<=*x**n* (0<=≤<=*x**i*<=≤<=100).

Output Specification:
Output a single integer — the minimal possible number of piles.

Demo Input:
['3\n0 0 10\n', '5\n0 1 2 3 4\n', '4\n0 0 0 0\n', '9\n0 1 0 2 0 1 1 2 10\n']

Demo Output:
['2\n', '1\n', '4\n', '3\n']

Note:
In example 1, one optimal way is to build 2 piles: the first pile contains boxes 1 and 3 (from top to bottom), the second pile contains only box 2.

In example 2, we can build only 1 pile that contains boxes 1, 2, 3, 4, 5 (from top to bottom).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an acyclic directed graph, consisting of n vertices and m edges. The graph contains no multiple edges and no self-loops.

The vertex is called a source if it has no incoming edges. The vertex is called a sink if it has no outgoing edges. These definitions imply that some vertices can be both source and sink.

The number of sources in the given graph is equal to the number of sinks in it, and each of these numbers doesn't exceed 20.

The following algorithm is applied to the graph:

  1. if the graph has no sources and sinks then quit; 
  2. choose arbitrary source s, arbitrary sink t, add an edge from t to s to the graph and go to step 1 (that operation pops s out of sources and t out of sinks). Note that s and t may be the same vertex, then a self-loop is added. 



At the end you check if the graph becomes strongly connected (that is, any vertex is reachable from any other vertex).

Your task is to check that the graph becomes strongly connected no matter the choice of sources and sinks on the second step of the algorithm.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 10^6) — the number of vertices and the number of edges in the graph, respectively.

Each of the next m lines contains two integers v_i, u_i (1 ≤ v_i, u_i ≤ n, v_i ≠ u_i) — the description of the i-th edge of the original graph.

It is guaranteed that the number of sources and the number of sinks in the graph are the same and they don't exceed 20. It is guaranteed that the given graph contains no multiple edges. It is guaranteed that the graph contains no cycles.

Output

Print "YES" if the graph becomes strongly connected no matter the choice of sources and sinks on the second step of the algorithm. Otherwise print "NO".

Examples

Input

3 1
1 2


Output

NO


Input

3 3
1 2
1 3
2 3


Output

YES


Input

4 4
1 2
1 3
4 2
4 3


Output

YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence BDF is a subsequence of ABCDEF. A substring of a string is a continuous subsequence of the string. For example, BCD is a substring of ABCDEF.

You are given two strings s1, s2 and another string called virus. Your task is to find the longest common subsequence of s1 and s2, such that it doesn't contain virus as a substring.

Input

The input contains three strings in three separate lines: s1, s2 and virus (1 ≤ |s1|, |s2|, |virus| ≤ 100). Each string consists only of uppercase English letters.

Output

Output the longest common subsequence of s1 and s2 without virus as a substring. If there are multiple answers, any of them will be accepted. 

If there is no valid common subsequence, output 0.

Examples

Input

AJKEQSLOBSROFGZ
OVGURWZLWVLUXTH
OZ


Output

ORZ


Input

AA
A
A


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Visiting a Friend

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pig is visiting a friend.

Pig's house is located at point 0, and his friend's house is located at point *m* on an axis.

Pig can use teleports to move along the axis.

To use a teleport, Pig should come to a certain point (where the teleport is located) and choose where to move: for each teleport there is the rightmost point it can move Pig to, this point is known as the limit of the teleport.

Formally, a teleport located at point *x* with limit *y* can move Pig from point *x* to any point within the segment [*x*;<=*y*], including the bounds.

Determine if Pig can visit the friend using teleports only, or he should use his car.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*<=≤<=100,<=1<=≤<=*m*<=≤<=100) — the number of teleports and the location of the friend's house.

The next *n* lines contain information about teleports.

The *i*-th of these lines contains two integers *a**i* and *b**i* (0<=≤<=*a**i*<=≤<=*b**i*<=≤<=*m*), where *a**i* is the location of the *i*-th teleport, and *b**i* is its limit.

It is guaranteed that *a**i*<=≥<=*a**i*<=-<=1 for every *i* (2<=≤<=*i*<=≤<=*n*).

Output Specification:
Print "YES" if there is a path from Pig's house to his friend's house that uses only teleports, and "NO" otherwise.

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

Demo Input:
['3 5\n0 2\n2 4\n3 5\n', '3 7\n0 4\n2 5\n6 7\n']

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

Note:
The first example is shown on the picture below:

Pig can use the first teleport from his house (point 0) to reach point 2, then using the second teleport go from point 2 to point 3, then using the third teleport go from point 3 to point 5, where his friend lives.

The second example is shown on the picture below:

You can see that there is no path from Pig's house to his friend's house that uses only teleports.

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