vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Consider sequences \{A_1,...,A_N\} of length N consisting of integers between 1 and K (inclusive).
There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.
Since this sum can be enormous, print the value modulo (10^9+7).
Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.

-----Constraints-----
 - 2 \leq N \leq 10^5
 - 1 \leq K \leq 10^5
 - All values in input are integers.

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

-----Output-----
Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).

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

-----Sample Output-----
9

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)+\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)=1+1+1+1+1+1+1+2=9
Thus, the answer is 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected unweighted connected graph consisting of n vertices and m edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to find any spanning tree of this graph such that the degree of the first vertex (vertex with label 1 on it) is equal to D (or say that there are no such spanning trees). Recall that the degree of a vertex is the number of edges incident to it.

Input

The first line contains three integers n, m and D (2 ≤ n ≤ 2 ⋅ 10^5, n - 1 ≤ m ≤ min(2 ⋅ 10^5, (n(n-1))/(2)), 1 ≤ D < n) — the number of vertices, the number of edges and required degree of the first vertex, respectively.

The following m lines denote edges: edge i is represented by a pair of integers v_i, u_i (1 ≤ v_i, u_i ≤ n, u_i ≠ v_i), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair (v_i, u_i) there are no other pairs (v_i, u_i) or (u_i, v_i) in the list of edges, and for each pair (v_i, u_i) the condition v_i ≠ u_i is satisfied.

Output

If there is no spanning tree satisfying the condition from the problem statement, print "NO" in the first line.

Otherwise print "YES" in the first line and then print n-1 lines describing the edges of a spanning tree such that the degree of the first vertex (vertex with label 1 on it) is equal to D. Make sure that the edges of the printed spanning tree form some subset of the input edges (order doesn't matter and edge (v, u) is considered the same as the edge (u, v)).

If there are multiple possible answers, print any of them.

Examples

Input


4 5 1
1 2
1 3
1 4
2 3
3 4


Output


YES
2 1
2 3
3 4


Input


4 5 3
1 2
1 3
1 4
2 3
3 4


Output


YES
1 2
1 3
4 1


Input


4 4 3
1 2
1 4
2 3
3 4


Output


NO

Note

The picture corresponding to the first and second examples: <image>

The picture corresponding to the third example: <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As lockdown is going on so no is allowed to go outside , so Chef has come with an innovative idea for food home delivery using drone.  But there is an issue with it , the drone can move forward or backward a fix number of steps $x$ . 
All the houses and chef restaurant are all in a straight line . Homes which need delivery are located at $H[i]$ and chef is located at $y$ coordinate . 
If Drone is at a location $R$, then it can move to $R-x$ or $R+x$ . 
Help chef find maximum value of $x$ to complete all the deliveries as he is busy managing the orders.

-----Input:-----
- First line will contain $n$ and $R$, number of houses that need delivery and the correct coordinate of chef (Drone).
- Second line contains $n$ integers , the coordinate of all homes that need delivery. 

-----Output:-----
- The maximum value of $x$ , so that drone delivers to all houses.

-----Constraints-----
- $1 \leq n \leq 1000$
- $1 \leq R \leq 10^9$
- $1 \leq hi \leq 10^9$
- $1 \leq x  \leq 10^9$

-----Sample Input:-----
3 1
3 5 11

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

-----EXPLANATION:-----
Chef's drone is at 1 initially and he needs to visit 3,5,11 , so optimal solution will be (maximum value of x ) equal to 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bachgold problem is very easy to formulate. Given a positive integer n represent it as a sum of maximum possible number of prime numbers. One can prove that such representation exists for any integer greater than 1.

Recall that integer k is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and k. 


-----Input-----

The only line of the input contains a single integer n (2 ≤ n ≤ 100 000).


-----Output-----

The first line of the output contains a single integer k — maximum possible number of primes in representation.

The second line should contain k primes with their sum equal to n. You can print them in any order. If there are several optimal solution, print any of them.


-----Examples-----
Input
5

Output
2
2 3

Input
6

Output
3
2 2 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an D-dimension array, where each axis is of length N, your goal is to find the sum of every index in the array starting from 0.

For Example if D=1 and N=10 then the answer would be 45 ([0,1,2,3,4,5,6,7,8,9])
If D=2 and N = 3 the answer is 18 which would be the sum of every number in the following:
```python
[
[(0,0), (0,1), (0,2)],
[(1,0), (1,1), (1,2)],
[(2,0), (2,1), (2,2)]
]
```

A naive solution could be to loop over every index in every dimension and add to a global sum. This won't work as the number of dimension is expected to be quite large.

Hint: A formulaic approach would be best
Hint 2: Gauss could solve the one dimensional case in his earliest of years, This is just a generalization.

~~~if:javascript
Note for JS version: Because the results will exceed the maximum safe integer easily, for such values you're only required to have a precision of at least `1 in 1e-9` to the actual answer.
~~~

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Friends are going to play console. They have two joysticks and only one charger for them. Initially first joystick is charged at *a*1 percent and second one is charged at *a*2 percent. You can connect charger to a joystick only at the beginning of each minute. In one minute joystick either discharges by 2 percent (if not connected to a charger) or charges by 1 percent (if connected to a charger).

Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joystick is charged by 1 percent, it has to be connected to a charger, otherwise the game stops. If some joystick completely discharges (its charge turns to 0), the game also stops.

Determine the maximum number of minutes that game can last. It is prohibited to pause the game, i. e. at each moment both joysticks should be enabled. It is allowed for joystick to be charged by more than 100 percent.

Input Specification:
The first line of the input contains two positive integers *a*1 and *a*2 (1<=≤<=*a*1,<=*a*2<=≤<=100), the initial charge level of first and second joystick respectively.

Output Specification:
Output the only integer, the maximum number of minutes that the game can last. Game continues until some joystick is discharged.

Demo Input:
['3 5\n', '4 4\n']

Demo Output:
['6\n', '5\n']

Note:
In the first sample game lasts for 6 minute by using the following algorithm:
 -  at the beginning of the first minute connect first joystick to the charger, by the end of this minute first joystick is at 4%, second is at 3%; -  continue the game without changing charger, by the end of the second minute the first joystick is at 5%, second is at 1%; -  at the beginning of the third minute connect second joystick to the charger, after this minute the first joystick is at 3%, the second one is at 2%; -  continue the game without changing charger, by the end of the fourth minute first joystick is at 1%, second one is at 3%; -  at the beginning of the fifth minute connect first joystick to the charger, after this minute the first joystick is at 2%, the second one is at 1%; -  at the beginning of the sixth minute connect second joystick to the charger, after this minute the first joystick is at 0%, the second one is at 2%. 
After that the first joystick is completely discharged and the game is stopped.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The University of Lagado is organising events for the upcoming Fresher’s week and has been told — much to the surprise of its staff — that some of the undergraduates may enjoy a beer tasting. While sourcing a wide variety of drinks for the students to taste, the university realised that in the interests of safety there should be a limit on the alcohol consumption of any student, enforced by a strict limit on the amount any individual is allowed to spend.

In common with many popular establishments, the drinks with varying strengths are served in varying amounts: Either a litre, a half litre or a third of a litre to limit possible intoxication. $1\% $ of a litre at $100\% $ strength equals one unit of alcohol.

The students are looking forward to the event, but in order to make the most of their money and still be bright-eyed and bushy tailed for the first week of morning lectures, they don’t wish to get too drunk. How can the students spend all their money and consume in full their self-imposed alcohol limit for the night?

-----Input-----
 - One line containing three numbers:
 - $m$ ($0.00 \le m \le 10.00$), the amount of money they can spend to two decimal places;
 - $u$ ($0.0 \le u \le 20.0$), the number of units they aim to drink to one decimal place;
 - $d$ ($1 \le d \le 8$), the number of different drinks available.
 - Another $d$ lines, each containing:
 - up to $20$ lowercase latin letters (the name of the drink);
 - an integer between $0$ and $100$ (its strength as a percentage);
 - its size (either ‘$1/1$’ for a litre, ‘$1/2$’ for a half or ‘$1/3$’ for a third);
 - a real number to two decimal places; its cost.

Name, strength, price and cost will be separated by spaces.

-----Output-----
If the students’ aims are possible, write one or more lines, each listing the name of the drink purchased followed by the positive integer count of how many drinks of that type were bought. If there are several solutions, output any.

Otherwise, output a single line containing the word IMPOSSIBLE.

-----Examples-----
Sample Input:
10.00 9.0 2
fire 2 1/1 4.00
water 10 1/2 2.00
Sample Output:
fire 2
water 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a_1, a_2, ..., a_n and an array b_1, b_2, ..., b_n.

For one operation you can sort in non-decreasing order any subarray a[l ... r] of the array a.

For example, if a = [4, 2, 2, 1, 3, 1] and you choose subbarray a[2 ... 5], then the array turns into [4, 1, 2, 2, 3, 1]. 

You are asked to determine whether it is possible to obtain the array b by applying this operation any number of times (possibly zero) to the array a.

Input

The first line contains one integer t (1 ≤ t ≤ 3 ⋅ 10^5) — the number of queries.

The first line of each query contains one integer n (1 ≤ n ≤ 3 ⋅ 10^5).

The second line of each query contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

The third line of each query contains n integers b_1, b_2, ..., b_n (1 ≤ b_i ≤ n).

It is guaranteed that ∑ n ≤ 3 ⋅ 10^5 over all queries in a test.

Output

For each query print YES (in any letter case) if it is possible to obtain an array b and NO (in any letter case) otherwise.

Example

Input


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


Output


YES
YES
NO
NO

Note

In first test case the can sort subarray a_1 ... a_5, then a will turn into [1, 1, 4, 4, 7, 5, 6], and then sort subarray a_5 ... a_6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $n$ and $m$ ($m < n$). Consider a convex regular polygon of $n$ vertices. Recall that a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length). [Image] Examples of convex regular polygons 

Your task is to say if it is possible to build another convex regular polygon with $m$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon.

You have to answer $t$ independent test cases.


-----Input-----

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

The next $t$ lines describe test cases. Each test case is given as two space-separated integers $n$ and $m$ ($3 \le m < n \le 100$) — the number of vertices in the initial polygon and the number of vertices in the polygon you want to build.


-----Output-----

For each test case, print the answer — "YES" (without quotes), if it is possible to build another convex regular polygon with $m$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon and "NO" otherwise.


-----Example-----
Input
2
6 3
7 3

Output
YES
NO



-----Note----- $0$ The first test case of the example 

It can be shown that the answer for the second test case of the example is "NO".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Eight Point Sets

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Gerald is very particular to eight point sets. He thinks that any decent eight point set must consist of all pairwise intersections of three distinct integer vertical straight lines and three distinct integer horizontal straight lines, except for the average of these nine points. In other words, there must be three integers *x*1,<=*x*2,<=*x*3 and three more integers *y*1,<=*y*2,<=*y*3, such that *x*1<=&lt;<=*x*2<=&lt;<=*x*3, *y*1<=&lt;<=*y*2<=&lt;<=*y*3 and the eight point set consists of all points (*x**i*,<=*y**j*) (1<=≤<=*i*,<=*j*<=≤<=3), except for point (*x*2,<=*y*2).

You have a set of eight points. Find out if Gerald can use this set?

Input Specification:
The input consists of eight lines, the *i*-th line contains two space-separated integers *x**i* and *y**i* (0<=≤<=*x**i*,<=*y**i*<=≤<=106). You do not have any other conditions for these points.

Output Specification:
In a single line print word "respectable", if the given set of points corresponds to Gerald's decency rules, and "ugly" otherwise.

Demo Input:
['0 0\n0 1\n0 2\n1 0\n1 2\n2 0\n2 1\n2 2\n', '0 0\n1 0\n2 0\n3 0\n4 0\n5 0\n6 0\n7 0\n', '1 1\n1 2\n1 3\n2 1\n2 2\n2 3\n3 1\n3 2\n']

Demo Output:
['respectable\n', 'ugly\n', 'ugly\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
— This is not playing but duty as allies of justice, Nii-chan!

— Not allies but justice itself, Onii-chan!

With hands joined, go everywhere at a speed faster than our thoughts! This time, the Fire Sisters — Karen and Tsukihi — is heading for somewhere they've never reached — water-surrounded islands!

There are three clusters of islands, conveniently coloured red, blue and purple. The clusters consist of a, b and c distinct islands respectively.

Bridges have been built between some (possibly all or none) of the islands. A bridge bidirectionally connects two different islands and has length 1. For any two islands of the same colour, either they shouldn't be reached from each other through bridges, or the shortest distance between them is at least 3, apparently in order to prevent oddities from spreading quickly inside a cluster.

The Fire Sisters are ready for the unknown, but they'd also like to test your courage. And you're here to figure out the number of different ways to build all bridges under the constraints, and give the answer modulo 998 244 353. Two ways are considered different if a pair of islands exist, such that there's a bridge between them in one of them, but not in the other.


-----Input-----

The first and only line of input contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 5 000) — the number of islands in the red, blue and purple clusters, respectively.


-----Output-----

Output one line containing an integer — the number of different ways to build bridges, modulo 998 244 353.


-----Examples-----
Input
1 1 1

Output
8

Input
1 2 2

Output
63

Input
1 3 5

Output
3264

Input
6 2 9

Output
813023575



-----Note-----

In the first example, there are 3 bridges that can possibly be built, and no setup of bridges violates the restrictions. Thus the answer is 2^3 = 8.

In the second example, the upper two structures in the figure below are instances of valid ones, while the lower two are invalid due to the blue and purple clusters, respectively. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Drazil likes heap very much. So he created a problem with heap:

There is a max heap with a height h implemented on the array. The details of this heap are the following:

This heap contains exactly 2^h - 1 distinct positive non-zero integers. All integers are distinct. These numbers are stored in the array a indexed from 1 to 2^h-1. For any 1 < i < 2^h, a[i] < a[\left ⌊{i/2}\right ⌋].

Now we want to reduce the height of this heap such that the height becomes g with exactly 2^g-1 numbers in heap. To reduce the height, we should perform the following action 2^h-2^g times:

Choose an index i, which contains an element and call the following function f in index i:

<image>

Note that we suppose that if a[i]=0, then index i don't contain an element.

After all operations, the remaining 2^g-1 element must be located in indices from 1 to 2^g-1. Now Drazil wonders what's the minimum possible sum of the remaining 2^g-1 elements. Please find this sum and find a sequence of the function calls to achieve this value.

Input

The first line of the input contains an integer t (1 ≤ t ≤ 70 000): the number of test cases.

Each test case contain two lines. The first line contains two integers h and g (1 ≤ g < h ≤ 20). The second line contains n = 2^h-1 distinct positive integers a[1], a[2], …, a[n] (1 ≤ a[i] < 2^{20}). For all i from 2 to 2^h - 1, a[i] < a[\left ⌊{i/2}\right ⌋].

The total sum of n is less than 2^{20}.

Output

For each test case, print two lines.

The first line should contain one integer denoting the minimum sum after reducing the height of heap to g. The second line should contain 2^h - 2^g integers v_1, v_2, …, v_{2^h-2^g}. In i-th operation f(v_i) should be called.

Example

Input


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


Output


10
3 2 3 1
8
2 1 3 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Stuart is a smart guy, and he loves mathematics. Today his math teacher taught his class about common factors.  After finishing the class his teacher asked them a question: For a given number  "N" calculate the number of unordered pairs (A,B) which have at least one common factor where  1 ≤ A < B ≤ N .

Note: 1 is not considered as common factor.

Input :
First line contain the number of test cases "T"
Next  "T" lines  contain a number  "N"

Input Constraints:

1 ≤ T ≤ 100000

1 ≤ N ≤ 1000000

Output:
For each case print total number of pairs.

SAMPLE INPUT
3
1
2
5

SAMPLE OUTPUT
0
0
1

Explanation

For testcase - 3 ,   

N = 5  

Some possible pairs = [(1, 2), (2, 3), (2, 4), (3, 4), (4, 5)]   

The only pair which has common factor is (2, 4). So the answer is 1 for N = 5.   

Note: 1 is not considered as common factor.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
### Task
The __dot product__ is usually encountered in linear algebra or scientific computing. It's also called __scalar product__ or __inner product__ sometimes:

> In mathematics, the __dot product__, or __scalar product__ (or sometimes __inner product__ in the context of Euclidean space), is an algebraic operation that takes two equal-length sequences of numbers (usually coordinate vectors) and returns a single number. [Wikipedia](https://en.wikipedia.org/w/index.php?title=Dot_product&oldid=629717691)

In our case, we define the dot product algebraically for two vectors `a = [a1, a2, …, an]`, `b = [b1, b2, …, bn]` as 
    
    dot a b = a1 * b1 + a2 * b2 + … + an * bn.
Your task is to find permutations of `a` and `b`, such that `dot a b` is minimal, and return that value. For example, the dot product of `[1,2,3]` and `[4,0,1]` is minimal if we switch `0` and `1` in the second vector.

### Examples
```python
min_dot([1,2,3,4,5], [0,1,1,1,0] ) = 6
min_dot([1,2,3,4,5], [0,0,1,1,-4]) = -17
min_dot([1,3,5]    , [4,-2,1]    ) = -3
```

### Remarks
If the list or array is empty, `minDot` should return 0. All arrays or lists will have the same length. Also, for the dynamically typed languages, all inputs will be valid lists or arrays, you don't need to check for `undefined`, `null` etc.

Note: This kata is inspired by [GCJ 2008](https://code.google.com/codejam/contest/32016/dashboard#s=p0).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a new mobile game that starts with consecutively numbered clouds.  Some of the clouds are thunderheads and others are cumulus.  The player can jump on any cumulus cloud having a number that is equal to the number of the current cloud plus $\mbox{1}$ or $2$.  The player must avoid the thunderheads.  Determine the minimum number of jumps it will take to jump from the starting postion to the last cloud.  It is always possible to win the game.  

For each game, you will get an array of clouds numbered $\mbox{0}$ if they are safe or $\mbox{1}$ if they must be avoided.  

Example 

$c=[0,1,0,0,0,1,0]$  

Index the array from $\boldsymbol{0\ldots6}$.  The number on each cloud is its index in the list so the player must avoid the clouds at indices $\mbox{I}$ and $5$.  They could follow these two paths: $0\rightarrow2\rightarrow4\rightarrow6$ or $0\to2\to3\to4\to6$.  The first path takes $3$ jumps while the second takes $\begin{array}{c}4\end{array}$.  Return $3$.

Function Description  

Complete the jumpingOnClouds function in the editor below.  

jumpingOnClouds has the following parameter(s):  

int c[n]: an array of binary integers  

Returns  

int: the minimum number of jumps required

Input Format

The first line contains an integer $n$, the total number of clouds. 
The second line contains $n$ space-separated binary integers describing clouds $c[i]$ where $0\leq i<n$.

Constraints

$2\leq n\leq100$
$c[i]\in\{0,1\}$
$c[0]=c[n-1]=0$

Output Format

Print the minimum number of jumps needed to win the game.

Sample Input 0

7
0 0 1 0 0 1 0

Sample Output 0

4

Explanation 0: 

The player must avoid $c[2]$ and $c\left[5\right]$. The game can be won with a minimum of $\begin{array}{c}4\end{array}$ jumps:

Sample Input 1

6
0 0 0 0 1 0

Sample Output 1

3

Explanation 1: 

The only thundercloud to avoid is $c\left[4\right]$. The game can be won in $3$ jumps:

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