vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given an array $a$ of length $n$ and an integer $k$, you are tasked to find any two numbers $l$ and $r$ ($l \leq r$) such that:

For each $x$ $(l \leq x \leq r)$, $x$ appears in $a$ at least $k$ times (i.e. $k$ or more array elements are equal to $x$).

The value $r-l$ is maximized.

If no numbers satisfy the conditions, output -1.

For example, if $a=[11, 11, 12, 13, 13, 14, 14]$ and $k=2$, then:

for $l=12$, $r=14$ the first condition fails because $12$ does not appear at least $k=2$ times.

for $l=13$, $r=14$ the first condition holds, because $13$ occurs at least $k=2$ times in $a$ and $14$ occurs at least $k=2$ times in $a$.

for $l=11$, $r=11$ the first condition holds, because $11$ occurs at least $k=2$ times in $a$.

A pair of $l$ and $r$ for which the first condition holds and $r-l$ is maximal is $l = 13$, $r = 14$.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \leq k \leq n$) — the length of the array $a$ and the minimum amount of times each number in the range $[l, r]$ should appear respectively.

Then a single line follows, containing $n$ integers describing the array $a$ ($1 \leq a_i \leq 10^9$).

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


-----Output-----

For each test case output $2$ numbers, $l$ and $r$ that satisfy the conditions, or "-1" if no numbers satisfy the conditions.

If multiple answers exist, you can output any.


-----Examples-----

Input
4
7 2
11 11 12 13 13 14 14
5 1
6 3 5 2 1
6 4
4 3 4 3 3 4
14 2
1 1 2 2 2 3 3 3 3 4 4 4 4 4
Output
13 14
1 3
-1
1 4


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have recently been hired as an architect for the BAPC (Bureau of Architecture and Promising Constructions), responsible for top-quality buildings such as the Tower of Pisa. However, in the past couple of weeks, some of the structures that the BAPC have made have collapsed! It is up to you to figure out whether any other structures are in danger.

After some research it seems like the $x$-coordinate of the centers of gravity of some of the structures are off: if the center of gravity is too much to the left or to the right, the structure will fall over. Hence, you decide to check all the blueprints and see whether the structures are stable or not.

Given is a grid of up to size $100$ by $100$, using characters in .#/\_|-. The $\texttt{.}$ characters denote empty space, while each other character represents a completely filled $1\times 1$ box (any difference in symbols used is due to the artistic freedom of the other architects), whose center of mass is at the center of the box.

Every structure forms a single connected component that touches the ground, i.e. the bottom layer of the grid.

The structure falls to the left if the $x$-coordinate of the center of gravity is less than the $x$-coordinate of the leftmost point of the structure that touches the ground, and it falls to the right if the $x$-coordinate of the center of gravity is larger than the $x$-coordinate of the rightmost point of the structure that touches the ground. It is guaranteed that the center of gravity is never exactly above the leftmost or rightmost point where the building touches the ground.

Given a blueprint, is the structure balanced, does it fall to the left, or does it fall to the right?

-----Input-----
 - The first line has $1\leq h \leq 100$ and $1\leq w\leq 100$, the height and width of the grid.
 - Then follow $h$ lines with $w$ characters each. Each character is either ., indicating empty space, or one of #/\_|-, indicating a filled $1\times 1$ box .

-----Output-----
 - Print a single line containing left, balanced, or right.

-----Examples-----
Sample Input 1:
3 3
/-\
|.|
#.#
Sample Output 1:
balanced

Sample Input 2:
3 3
...
___
..|
Sample Output 2:
left

Sample Input 3:
3 3
./\
.\/
.|.
Sample Output 3:
balanced

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a table $a$ of size $2 \times n$ (i.e. two rows and $n$ columns) consisting of integers from $1$ to $n$.

In one move, you can choose some column $j$ ($1 \le j \le n$) and swap values $a_{1, j}$ and $a_{2, j}$ in it. Each column can be chosen no more than once.

Your task is to find the minimum number of moves required to obtain permutations of size $n$ in both first and second rows of the table or determine if it is impossible to do that.

You have to answer $t$ independent test cases.

Recall that the permutation of size $n$ is such an array of size $n$ that contains each integer from $1$ to $n$ exactly once (the order of elements doesn't matter).


-----Input-----

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

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of columns in the table. The second line of the test case contains $n$ integers $a_{1, 1}, a_{1, 2}, \dots, a_{1, n}$ ($1 \le a_{1, i} \le n$), where $a_{1, i}$ is the $i$-th element of the first row of the table. The third line of the test case contains $n$ integers $a_{2, 1}, a_{2, 2}, \dots, a_{2, n}$ ($1 \le a_{2, i} \le n$), where $a_{2, i}$ is the $i$-th element of the second row of the table.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case print the answer: -1 if it is impossible to obtain permutation of size $n$ in both first and the second rows of the table, or one integer $k$ in the first line, where $k$ is the minimum number of moves required to obtain permutations in both rows, and $k$ distinct integers $pos_1, pos_2, \dots, pos_k$ in the second line ($1 \le pos_i \le n$) in any order — indices of columns in which you need to swap values to obtain permutations in both rows. If there are several answers, you can print any.


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

Output
0

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nowadays all circuses in Berland have a round arena with diameter 13 meters, but in the past things were different.

In Ancient Berland arenas in circuses were shaped as a regular (equiangular) polygon, the size and the number of angles could vary from one circus to another. In each corner of the arena there was a special pillar, and the rope strung between the pillars marked the arena edges.

Recently the scientists from Berland have discovered the remains of the ancient circus arena. They found only three pillars, the others were destroyed by the time.

You are given the coordinates of these three pillars. Find out what is the smallest area that the arena could have.

Input

The input file consists of three lines, each of them contains a pair of numbers –– coordinates of the pillar. Any coordinate doesn't exceed 1000 by absolute value, and is given with at most six digits after decimal point.

Output

Output the smallest possible area of the ancient arena. This number should be accurate to at least 6 digits after the decimal point. It's guaranteed that the number of angles in the optimal polygon is not larger than 100.

Examples

Input

0.000000 0.000000
1.000000 1.000000
0.000000 1.000000


Output

1.00000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s$ consisting of $n$ lowercase Latin letters.

You have to remove at most one (i.e. zero or one) character of this string in such a way that the string you obtain will be lexicographically smallest among all strings that can be obtained using this operation.

String $s = s_1 s_2 \dots s_n$ is lexicographically smaller than string $t = t_1 t_2 \dots t_m$ if $n < m$ and $s_1 = t_1, s_2 = t_2, \dots, s_n = t_n$ or there exists a number $p$ such that $p \le min(n, m)$ and $s_1 = t_1, s_2 = t_2, \dots, s_{p-1} = t_{p-1}$ and $s_p < t_p$.

For example, "aaa" is smaller than "aaaa", "abb" is smaller than "abc", "pqr" is smaller than "z".


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of $s$.

The second line of the input contains exactly $n$ lowercase Latin letters — the string $s$.


-----Output-----

Print one string — the smallest possible lexicographically string that can be obtained by removing at most one character from the string $s$.


-----Examples-----
Input
3
aaa

Output
aa

Input
5
abcda

Output
abca



-----Note-----

In the first example you can remove any character of $s$ to obtain the string "aa".

In the second example "abca" < "abcd" < "abcda" < "abda" < "acda" < "bcda".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ho, Ho, Ho!
It's Christmas time and our friendly grandpa Santa Claus is busy distributing gifts to all the nice children. With the rising population, Santa's workload every year gets increased and he seeks your help to wrap the gifts with fancy wrapping papers while he gets them distributed. 
Everything was going great until you realised that you'll fall short of wrapping paper. But luckily, you get a very innovative idea, that will allow you to pack all the remaining gifts without worrying about lack of wrapping paper. Any guesses what the idea is? Using ice for wrapping, obviously! That's the only thing available at the North Pole.
Now, in order to reduce your trips to the ice factory, you decide to write a program that helps you visualize how much ice is needed for a particular gift. 

-----Input:-----
Input will consist of a single line with size $n$.

-----Output:-----
Print the ice wrapped gift box for the given size. 

-----Constraints-----
- $0 \leq n \leq 1000$

-----Sample Input:-----
4

-----Sample Output:-----
4 4 4 4 4 4 4
4 3 3 3 3 3 4
4 3 2 2 2 3 4
4 3 2 1 2 3 4
4 3 2 2 2 3 4 
4 3 3 3 3 3 4
4 4 4 4 4 4 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
How many integer sequences A_1,A_2,\ldots,A_N of length N satisfy all of the following conditions?
 - 0 \leq A_i \leq 9
 - There exists some i such that A_i=0 holds.
 - There exists some i such that A_i=9 holds.
The answer can be very large, so output it modulo 10^9 + 7.

-----Constraints-----
 - 1 \leq N \leq 10^6
 - N is an integer.

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

-----Output-----
Print the answer modulo 10^9 + 7.

-----Sample Input-----
2

-----Sample Output-----
2

Two sequences \{0,9\} and \{9,0\} satisfy all conditions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Major Mickle is commanded to protect a secret base which is being attacked by N tanks. Mickle has an ultimate laser rifle called Mickle's beam. Any object shot by this beam will be immediately destroyed, and there is no way for protection. Furthermore, the beam keeps going through even after destroying objects. The beam is such a powerful and horrible weapon, but there is one drawback: the beam consumes a huge amount of energy. For this reason, the number of shots should be always minimized.

Your job is to write a program that calculates the minimum number of shots required to destroy all the enemy tanks.

You can assume the following:

* the base is located on the origin (0, 0);
* each tank has a rectangular shape with edges parallel to the x- and y-axes;
* no tank may touch or include the origin;
* no two tanks share the same point;
* the width of beam is negligible; and
* a beam destroys every tank it touches or crosses.



Input

The input consists of an integer sequence.

The first integer indicates N (N ≤ 2,000). Each of the following N lines contains four integers which indicates the x- and y-coordinates of the lower-left corner and the upper-right corner of a tank respectively. You can assume that every coordinate may not exceed 10,000 in absolute value.

Output

Output the minimum number of shots of the beam.

Example

Input




Output

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The king of Berland organizes a ball! n pair are invited to the ball, they are numbered from 1 to n. Each pair consists of one man and one woman. Each dancer (either man or woman) has a monochrome costume. The color of each costume is represented by an integer from 1 to k, inclusive.

Let b_i be the color of the man's costume and g_i be the color of the woman's costume in the i-th pair. You have to choose a color for each dancer's costume (i.e. values b_1, b_2, ..., b_n and g_1, g_2, ... g_n) in such a way that:

  1. for every i: b_i and g_i are integers between 1 and k, inclusive; 
  2. there are no two completely identical pairs, i.e. no two indices i, j (i ≠ j) such that b_i = b_j and g_i = g_j at the same time; 
  3. there is no pair such that the color of the man's costume is the same as the color of the woman's costume in this pair, i.e. b_i ≠ g_i for every i; 
  4. for each two consecutive (adjacent) pairs both man's costume colors and woman's costume colors differ, i.e. for every i from 1 to n-1 the conditions b_i ≠ b_{i + 1} and g_i ≠ g_{i + 1} hold. 



Let's take a look at the examples of bad and good color choosing (for n=4 and k=3, man is the first in a pair and woman is the second):

Bad color choosing: 

  * (1, 2), (2, 3), (3, 2), (1, 2) — contradiction with the second rule (there are equal pairs); 
  * (2, 3), (1, 1), (3, 2), (1, 3) — contradiction with the third rule (there is a pair with costumes of the same color); 
  * (1, 2), (2, 3), (1, 3), (2, 1) — contradiction with the fourth rule (there are two consecutive pairs such that colors of costumes of men/women are the same). 



Good color choosing: 

  * (1, 2), (2, 1), (1, 3), (3, 1); 
  * (1, 2), (3, 1), (2, 3), (3, 2); 
  * (3, 1), (1, 2), (2, 3), (3, 2). 



You have to find any suitable color choosing or say that no suitable choosing exists.

Input

The only line of the input contains two integers n and k (2 ≤ n, k ≤ 2 ⋅ 10^5) — the number of pairs and the number of colors.

Output

If it is impossible to find any suitable colors choosing, print "NO".

Otherwise print "YES" and then the colors of the costumes of pairs in the next n lines. The i-th line should contain two integers b_i and g_i — colors of costumes of man and woman in the i-th pair, respectively.

You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.

Examples

Input


4 3


Output


YES
3 1
1 3
3 2
2 3


Input


10 4


Output


YES
2 1
1 3
4 2
3 4
4 3
3 2
2 4
4 1
1 4
3 1


Input


13 4


Output


NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two positive integers A and B. You need to construct two different binary strings (i.e, they are strings which consist of only 0s and 1s), which satisfy these two conditions:

Both the strings should be palindromes.
Each string should have exactly A 0s, and exactly B 1s in them.

Output Yes if two such different binary strings can be constructed and No otherwise.

Note: 
A string is said to be a palindrome, if the string and the reverse of the string are identical.
Two strings are said to be different if either their lengths are different, or if they differ in at least one character.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case contains two space-separated integers, A and B, in a new line.

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

For each test case, output on a new line 'Yes', if you can construct two different binary strings satisfying the conditions. If not, output No.

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 ≤ T ≤ 10^{5}$
$1 ≤ A, B ≤ 10^{6}$

----- Sample Input 1 ------ 
3
2 2
2 3
3 3

----- Sample Output 1 ------ 
Yes
Yes
No

----- explanation 1 ------ 
Test case $1$: Consider the binary strings $0110$ and $1001$. Both of them are palindromes, and both of them have exactly $2$ $0$s, and $2$ $1$s. Hence we can construct them, and so the answer is Yes.

Test case $2$: Consider the binary strings $01110$ and $10101$. Both of them are palindromes, and both of them have exactly $2$ $0$s, and $3$ $1$s. Hence we can construct them, and so the answer is Yes.

Test case $3$: There is no way to construct two such different strings. Hence the answer is No.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: I'm bored with life

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Holidays have finished. Thanks to the help of the hacker Leha, Noora managed to enter the university of her dreams which is located in a town Pavlopolis. It's well known that universities provide students with dormitory for the period of university studies. Consequently Noora had to leave Vičkopolis and move to Pavlopolis. Thus Leha was left completely alone in a quiet town Vičkopolis. He almost even fell into a depression from boredom!

Leha came up with a task for himself to relax a little. He chooses two integers *A* and *B* and then calculates the greatest common divisor of integers "*A* factorial" and "*B* factorial". Formally the hacker wants to find out GCD(*A*!,<=*B*!). It's well known that the factorial of an integer *x* is a product of all positive integers less than or equal to *x*. Thus *x*!<==<=1·2·3·...·(*x*<=-<=1)·*x*. For example 4!<==<=1·2·3·4<==<=24. Recall that GCD(*x*,<=*y*) is the largest positive integer *q* that divides (without a remainder) both *x* and *y*.

Leha has learned how to solve this task very effective. You are able to cope with it not worse, aren't you?

Input Specification:
The first and single line contains two integers *A* and *B* (1<=≤<=*A*,<=*B*<=≤<=109,<=*min*(*A*,<=*B*)<=≤<=12).

Output Specification:
Print a single integer denoting the greatest common divisor of integers *A*! and *B*!.

Demo Input:
['4 3\n']

Demo Output:
['6\n']

Note:
Consider the sample.

4! = 1·2·3·4 = 24. 3! = 1·2·3 = 6. The greatest common divisor of integers 24 and 6 is exactly 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mikhail walks on a Cartesian plane. He starts at the point $(0, 0)$, and in one move he can go to any of eight adjacent points. For example, if Mikhail is currently at the point $(0, 0)$, he can go to any of the following points in one move:   $(1, 0)$;  $(1, 1)$;  $(0, 1)$;  $(-1, 1)$;  $(-1, 0)$;  $(-1, -1)$;  $(0, -1)$;  $(1, -1)$. 

If Mikhail goes from the point $(x1, y1)$ to the point $(x2, y2)$ in one move, and $x1 \ne x2$ and $y1 \ne y2$, then such a move is called a diagonal move.

Mikhail has $q$ queries. For the $i$-th query Mikhail's target is to go to the point $(n_i, m_i)$ from the point $(0, 0)$ in exactly $k_i$ moves. Among all possible movements he want to choose one with the maximum number of diagonal moves. Your task is to find the maximum number of diagonal moves or find that it is impossible to go from the point $(0, 0)$ to the point $(n_i, m_i)$ in $k_i$ moves.

Note that Mikhail can visit any point any number of times (even the destination point!).


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 10^4$) — the number of queries.

Then $q$ lines follow. The $i$-th of these $q$ lines contains three integers $n_i$, $m_i$ and $k_i$ ($1 \le n_i, m_i, k_i \le 10^{18}$) — $x$-coordinate of the destination point of the query, $y$-coordinate of the destination point of the query and the number of moves in the query, correspondingly.


-----Output-----

Print $q$ integers. The $i$-th integer should be equal to -1 if Mikhail cannot go from the point $(0, 0)$ to the point $(n_i, m_i)$ in exactly $k_i$ moves described above. Otherwise the $i$-th integer should be equal to the the maximum number of diagonal moves among all possible movements.


-----Example-----
Input
3
2 2 3
4 3 7
10 1 9

Output
1
6
-1



-----Note-----

One of the possible answers to the first test case: $(0, 0) \to (1, 0) \to (1, 1) \to (2, 2)$.

One of the possible answers to the second test case: $(0, 0) \to (0, 1) \to (1, 2) \to (0, 3) \to (1, 4) \to (2, 3) \to (3, 2) \to (4, 3)$.

In the third test case Mikhail cannot reach the point $(10, 1)$ in 9 moves.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a permutation $A = (a_1, a_2, \dots , a_ N)$ of the integers $1, 2, \dots , N$, we define the greedily increasing subsequence (GIS) in the following way.

Let $g_1 = a_1$. For every $i > 1$, let $g_ i$ be the leftmost integer in $A$ that is strictly larger than $g_{i-1}$. If there for a given $i$ is no such integer, we say that the GIS of the sequence is the sequence $(g_1, g_2, ..., g_{i - 1})$.

Your task is to, given a permutation $A$, compute the GIS of $A$.

-----Input-----
The first line of input contains an integer $1 \le N \le 10^6$, the number of elements of the permutation $A$. The next line contains $N$ distinct integers between $1$ and $N$, the elements $a_1, \dots , a_ N$ of the permutation $A$.

-----Output-----
First, output a line containing the length $l$ of the GIS of $A$. Then, output $l$ integers, containing (in order) the elements of the GIS.

-----Explanation of sample 1-----
In this case, we have the permutation $2, 3, 1, 5, 4, 7, 6$. First, we have $g_1 = 2$. The leftmost integer larger than $2$ is $3$, so $g_2 = 3$. The leftmost integer larger than $3$ is $5$ ($1$ is too small), so $g_3 = 5$. The leftmost integer larger than $5$ is $7$, so $g_4 = 7$. Finally, there is no integer larger than $7$. Thus, the GIS of $2, 3, 1, 5, 4, 7, 6$ is $2, 3, 5, 7$.

-----Examples-----
Sample Input 1:
7
2 3 1 5 4 7 6
Sample Output 1:
4
2 3 5 7

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Grigory has n magic stones, conveniently numbered from 1 to n. The charge of the i-th stone is equal to c_i.

Sometimes Grigory gets bored and selects some inner stone (that is, some stone with index i, where 2 ≤ i ≤ n - 1), and after that synchronizes it with neighboring stones. After that, the chosen stone loses its own charge, but acquires the charges from neighboring stones. In other words, its charge c_i changes to c_i' = c_{i + 1} + c_{i - 1} - c_i.

Andrew, Grigory's friend, also has n stones with charges t_i. Grigory is curious, whether there exists a sequence of zero or more synchronization operations, which transforms charges of Grigory's stones into charges of corresponding Andrew's stones, that is, changes c_i into t_i for all i?

Input

The first line contains one integer n (2 ≤ n ≤ 10^5) — the number of magic stones.

The second line contains integers c_1, c_2, …, c_n (0 ≤ c_i ≤ 2 ⋅ 10^9) — the charges of Grigory's stones.

The second line contains integers t_1, t_2, …, t_n (0 ≤ t_i ≤ 2 ⋅ 10^9) — the charges of Andrew's stones.

Output

If there exists a (possibly empty) sequence of synchronization operations, which changes all charges to the required ones, print "Yes".

Otherwise, print "No".

Examples

Input


4
7 2 4 12
7 15 10 12


Output


Yes


Input


3
4 4 4
1 2 3


Output


No

Note

In the first example, we can perform the following synchronizations (1-indexed):

  * First, synchronize the third stone [7, 2, 4, 12] → [7, 2, 10, 12]. 
  * Then synchronize the second stone: [7, 2, 10, 12] → [7, 15, 10, 12]. 



In the second example, any operation with the second stone will not change its charge.

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