TheForces Round #19 (Briefest-Forces)
A. Dice Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game with two special dices.For a throw,Alice'll get an integer number in $$$[l_1, r_1]$$$,and Bob'll get an integer number in $$$[l_2, r_2]$$$.The probability of each number appearing is equal.

They will throw their dice twice and sum up two numbers they will get.If their sums are equal,they tie.Otherwise the person with a larger sum will win the game.

You task is to determine if the probability of Alice's winning is strictly higher than Bob's .

Input

The first line of the test case contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$), which denotes the number of test cases.

The first line of each test case contains two integers $$$l_1$$$ and $$$r_1$$$ ($$$1 \le l_1 \lt r_1 \le 10^9$$$), which describes the dice of Alice.

The second line of each test case contains two integers $$$l_2$$$ and $$$r_2$$$ ($$$1 \le l_2 \lt r_2 \le 10^9$$$), which describes the dice of Bob.

Output

For each test case, output "Yes" (without quotes) if the probability of Alice's winning is strictly higher than Bob's, and "No" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
2
1 2
2 3
8 9
6 8
Output
NO
YES
Note

In sample case $$$1$$$, there are total $$$9$$$ possible final results as given below:

$$$[2, 4],$$$ $$$[2, 5],$$$ $$$[2, 6],$$$ $$$[3, 4],$$$ $$$[3, 5],$$$ $$$[3, 6],$$$ $$$[4, 4],$$$ $$$[4, 5],$$$ $$$[4, 6]$$$

Among these, Alice can not win any games, So the probability that Alice will win is $$$0$$$. Thus, the answer is "NO".

B. K Integers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two integers $$$n,k$$$,determine if there are $$$k$$$ positive integers $$$a_1,a_2,...,a_k$$$ satisfy:

  1. $$$a_1+a_2+...+a_k=n$$$;
  2. $$$gcd(a_1,a_2,..,a_k) \gt 1$$$.
Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of a line of input.The only line of each test case contains two integers $$$n,k(2 \leq k \leq n \leq 10^5)$$$.

Output

For each test case, output "Yes" (without quotes) if there are $$$k$$$ posotive integers $$$a_1,a_2,...,a_k$$$ satisfy the condition above, and "No" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
5
4 2
4 3
15 4
100000 2
100000 100000
Output
YES
NO
YES
YES
NO
Note

Test case $$$1$$$:

$$$a_1=2,a_2=2$$$ satisfy the condition since $$$a_1+a_2=4$$$ and $$$gcd(a_1,a_2)=gcd(2,2)=2 \gt 1$$$.

Test case $$$2$$$:

There're not $$$3$$$ positive integers satisfy the condition.

C. Count Triples
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given three arrays $$$a,b,c$$$ of length $$$n$$$ and a number $$$m$$$.

Your task is to count the number of triples $$$(i,j,k)$$$ such that $$$a_i\times b_j \times c_k=m$$$.

Input

The first line of input contains two numbers $$$n(1\le n\le 5\times 10^5),m(1\le m\le 10^9)$$$.

The second line contains $$$n$$$ numbers $$$a_1,a_2,\ldots,a_n(1\le a_i\le m)$$$.

The third line contains $$$n$$$ numbers $$$b_1,b_2,\ldots,b_n(1\le b_i\le m)$$$.

The fourth line contains $$$n$$$ numbers $$$c_1,c_2,\ldots,c_n(1\le c_i\le m)$$$.

Output

Print the answer.

Examples
Input
3 3
1 2 3
1 1 3
2 3 3
Output
4
Input
4 2
1 1 1 1
1 1 1 1
1 1 1 1
Output
0
Input
6 18
2 4 3 5 7 1
18 6 2 3 5 9
1 1 3 2 7 5
Output
11
Note

In the first example, there are four triples satisfy the condition: $$$(1,1,2),(1,2,2),(1,1,3),(1,2,3)$$$.

In the second example, it can be shown that there's no triple satisfy the condition.

D. Tree Construction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two integers $$$n,x$$$.Your task is to construct a tree of size $$$n$$$ which's score is $$$x$$$.

The score of a tree is defined as the sum of the distances from all leaf nodes to the root node,where node $$$1$$$ is the root node.

If no solution,output $$$-1$$$ instead.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

The only line of each test case contains two integers $$$n,x(1 \leq n \leq 2*10^5,1 \leq x \leq 10^{18})$$$.

The sum of $$$n$$$ will not exceed $$$2*10^5$$$.

Output

If no solution,output $$$-1$$$ .

Otherwise,for each test case,output $$$n-1$$$ lines.Each line contains two integers $$$u,v$$$,denoting there's an edge connecting node $$$u$$$ and $$$v$$$.

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

E. Max Mobius Sum
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You're given a number circle $$$a$$$ of size $$$2n$$$($$$a_1$$$ is adjecent to $$$a_{2n}$$$).

You can perform the following operation exactly once:

  • Choose an integer $$$k(1\leq k \leq n)$$$,then swap $$$a_1$$$ and $$$a_{n+1}$$$,$$$a_2$$$ and $$$a_{n+2}$$$,...,$$$a_k$$$ and $$$a_{n+k}$$$.

After that,you can choose the sum of some consecutive numbers in $$$a$$$ as your score.Find your maximum score.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of two lines of input.

The first line contains an integer $$$n(1 \leq n \leq 1.5*10^6)$$$.

The second line contains $$$2n$$$ integers $$$a_1,a_2,...,a_{2n}(-10^9\leq a_i \leq 10^9)$$$.

The sum of $$$n$$$ will not exceed $$$1.5*10^6$$$.

Output

For each test case,output on a new line —your maximum score.

Example
Input
4
3
-1 2 -3 -4 -5 6
3
-3 5 -2 6 4 -1
3
-2 -2 -2 -1 -2 -2
3
1 2 3 4 5 6
Output
8
14
-1
21
Note

Test case $$$1$$$:

Choose $$$k=2$$$,you'll get $$$a=\{-4,-5,-3,-1,2,6\}$$$.Then choose $$$a_5+a_6=2+6=8$$$ as you score.

Test case $$$2$$$:

Choose $$$k=1$$$,you'll get $$$a=\{6,5,-2,-3,4,-1\}$$$.Then choose $$$a_5+a_6+a_1+a_2=4-1+6+5=14$$$ as you score(note $$$a_1$$$ is adjecent to $$$a_{6}$$$).

F. Stack Sort
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ stacks.Initially,there's an integer $$$a_i$$$ in the $$$i_{th}$$$ stack.

Your task is to sort it.Formally,the final arrangement should have $$$n$$$ stacks with each stack having precisely one number, such that they are in non-decreasing order.To do so, following move can be done any number of times:

  • Move a number from top of one stack to the top of some other stack.

Print the minimum number of moves required to sort the array, or $$$-1$$$ if it is not possible.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 2*10^5)$$$, denoting the number of test cases.

Each test case consists of two lines of input.

The first line contains an integer $$$n(1 \leq n \leq 2*10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(1\leq a_i \leq n)$$$.

The sum of $$$n$$$ will not exceed $$$2*10^5$$$.

Output

For each test case,output on a new line — the minimum number of moves required to sort the array, or $$$-1$$$ if it is not possible.

Example
Input
6
3
2 3 1
3
2 2 1
1
1
2
2 1
4
2 1 4 3
6
2 3 1 3 1 2
Output
5
3
0
-1
6
8
Note

Test case $$$1$$$:

The minimum number of moves required is $$$5$$$.The following picture shows the specific process of the movement.