vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Table Tennis Game 2

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Misha and Vanya have played several table tennis sets. Each set consists of several serves, each serve is won by one of the players, he receives one point and the loser receives nothing. Once one of the players scores exactly *k* points, the score is reset and a new set begins.

Across all the sets Misha scored *a* points in total, and Vanya scored *b* points. Given this information, determine the maximum number of sets they could have played, or that the situation is impossible.

Note that the game consisted of several complete sets.

Input Specification:
The first line contains three space-separated integers *k*, *a* and *b* (1<=≤<=*k*<=≤<=109, 0<=≤<=*a*,<=*b*<=≤<=109, *a*<=+<=*b*<=&gt;<=0).

Output Specification:
If the situation is impossible, print a single number -1. Otherwise, print the maximum possible number of sets.

Demo Input:
['11 11 5\n', '11 2 3\n']

Demo Output:
['1\n', '-1\n']

Note:
Note that the rules of the game in this problem differ from the real table tennis game, for example, the rule of "balance" (the winning player has to be at least two points ahead to win a set) has no power within the present problem.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata you will create a function that takes a list of non-negative integers and strings and returns a new list with the strings filtered out.

### Example

```python
filter_list([1,2,'a','b']) == [1,2]
filter_list([1,'a','b',0,15]) == [1,0,15]
filter_list([1,2,'aasf','1','123',123]) == [1,2,123]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Test data generation is not an easy task! Often, generating big random test cases is not enough to ensure thorough testing of solutions for correctness.

For example, consider a problem from an old Codeforces round. Its input format looks roughly as follows:

The first line contains a single integer n (1 ≤ n ≤ maxn) — the size of the set. The second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ maxa) — the elements of the set in increasing order.

If you don't pay attention to the problem solution, it looks fairly easy to generate a good test case for this problem. Let n = maxn, take random distinct ai from 1 to maxa, sort them... Soon you understand that it's not that easy.

Here is the actual problem solution. Let g be the greatest common divisor of a1, a2, ..., an. Let x = an / g - n. Then the correct solution outputs "Alice" if x is odd, and "Bob" if x is even.

Consider two wrong solutions to this problem which differ from the correct one only in the formula for calculating x.

The first wrong solution calculates x as x = an / g (without subtracting n).

The second wrong solution calculates x as x = an - n (without dividing by g).

A test case is interesting if it makes both wrong solutions output an incorrect answer.

Given maxn, maxa and q, find the number of interesting test cases satisfying the constraints, and output it modulo q.

Input

The only line contains three integers maxn, maxa and q (1 ≤ maxn ≤ 30 000; maxn ≤ maxa ≤ 109; 104 ≤ q ≤ 105 + 129).

Output

Output a single integer — the number of test cases which satisfy the constraints and make both wrong solutions output an incorrect answer, modulo q.

Examples

Input

3 6 100000


Output

4


Input

6 21 100129


Output

154


Input

58 787788 50216


Output

46009

Note

In the first example, interesting test cases look as follows: 
    
    
      
    1              1              1              3  
    2              4              6              2 4 6  
    

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zombies have found out about the Zombie Contamination level checker and managed to damage it! Now detecting the shape of their main compound will be a real challenge for Heidi. As before, a lair can be represented as a strictly convex polygon on a lattice. Each vertex of the polygon occupies a point on the lattice. However, the damaged Zombie Contamination level checker can only tell, for each cell, whether the level of Zombie Contamination for that cell is in the set {1, 2, 3}. In other words, Heidi knows all the cells of the lattice for which the Contamination level is not 0 and not 4.

Given this information, Heidi still wants to know the exact shape of the lair to rain destruction on the zombies. Help her!

Input

The input contains multiple test cases.

The first line of each test case contains two space-separated integers N and M, where N is the size of the lattice grid (5 ≤ N ≤ 100000) and M is the number of lattice points for which the Zombie Contamination level is 1, 2, or 3 (8 ≤ M ≤ 200000).

The second line of each test case contains M pairs of integers x1, y1, ..., xM, yM – coordinates of the cells with Zombie Contamination level not equal to 0 nor 4. It is guaranteed that 1 ≤ xi, yi ≤ N. All pairs xi, yi are different.

Cells are enumerated based on the coordinates of their upper right corner. This means that the bottommost leftmost cell that touches the origin has coordinates (1, 1), and the uppermost leftmost cell is identified as (1, N).

The last line of the file contains two zeroes. This line should not be treated as a test case. The sum of the M values for all tests in one file will not exceed 200000.

Output

For each test case, the following output is expected:

The first line of the output should contain one integer V, the number of vertices of the polygon that is the secret lair. The next V lines each should contain two integers, denoting the vertices of the polygon in the clockwise order, starting from the lexicographically smallest vertex.

Example

Input

8 19
2 3 2 4 2 5 3 3 3 5 4 3 4 5 4 6 5 2 5 3 5 6 6 2 6 3 6 4 6 5 6 6 6 7 7 6 7 7
5 8
2 2 2 3 2 4 3 2 3 4 4 2 4 3 4 4
0 0


Output

4
2 3
2 4
6 6
5 2
4
2 2
2 3
3 3
3 2

Note

It is guaranteed that the solution always exists and is unique. It is guaranteed that in the correct solution the coordinates of the polygon vertices are between 1 and N - 1. A vertex (x1, y1) is lexicographically smaller than vertex (x2, y2) if x1 < x2 or <image>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an amount and the denominations of coins available, determine how many ways change can be made for amount.  There is a limitless supply of each coin type.  

Example 

$n=3$ 

$c=[8,3,1,2]$  

There are $3$ ways to make change for $n=3$: $\{1,1,1\}$, $\{1,2\}$, and $\{3\}$.

Function Description  

Complete the getWays function in the editor below.  

getWays has the following parameter(s):

int n: the amount to make change for  
int c[m]: the available coin denominations   

Returns   

int: the number of ways to make change  

Input Format

The first line contains two space-separated integers $n$ and $m$, where: 

$n$ is the amount to change 

$m$ is the number of coin types 

The second line contains $m$ space-separated integers that describe the values of each coin type.  

Constraints

$1\leq c[i]\leq50$
$1\leq n\leq250$
$1\leq m\leq50$
Each $c[i]$ is guaranteed to be distinct.

Hints

Solve overlapping subproblems using Dynamic Programming (DP): 

    You can solve this problem recursively but will not pass all the test cases without optimizing to eliminate the overlapping subproblems. Think of a way to store and reference previously computed solutions to avoid solving the same subproblem multiple times.
* Consider the degenerate cases: 

    - How many ways can you make change for $0$ cents? 
    - How many ways can you make change for $>0$ cents if you have no coins?
* If you're having trouble defining your solutions store, then think about it in terms of the base case $\left(n=0\right)$.
- The answer may be larger than a $32$-bit integer.

Sample Input 0
4 3
1 2 3

Sample Output 0
4

Explanation 0

There are four ways to make change for $n=4$ using coins with values given by $C=[1,2,3]$:

$\{1,1,1,1\}$
$\{1,1,2\}$
$\{2,2\}$
$\{1,3\}$ 

Sample Input 1
10 4
2 5 3 6

Sample Output 1
5

Explanation 1

There are five ways to make change for $n=10$ units using coins with values given by $C=[2,5,3,6]$:

$\{2,2,2,2,2\}$
$\{2,2,3,3\}$
$\{2,2,6\}$
$\{2,3,5\}$ 
$\{5,5\}$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is the hard version of the problem. The only difference is that in this version 3 ≤ k ≤ n.

You are given a positive integer n. Find k positive integers a_1, a_2, …, a_k, such that:

  * a_1 + a_2 + … + a_k = n 
  * LCM(a_1, a_2, …, a_k) ≤ n/2 



Here LCM is the [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple) of numbers a_1, a_2, …, a_k.

We can show that for given constraints the answer always exists.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The only line of each test case contains two integers n, k (3 ≤ n ≤ 10^9, 3 ≤ k ≤ n).

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

Output

For each test case print k positive integers a_1, a_2, …, a_k, for which all conditions are satisfied.

Example

Input


2
6 4
9 5


Output


1 2 2 1 
1 3 3 1 1 

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got a table of size *n*<=×<=*m*. We'll consider the table rows numbered from top to bottom 1 through *n*, and the columns numbered from left to right 1 through *m*. Then we'll denote the cell in row *x* and column *y* as (*x*,<=*y*).

Initially cell (1,<=1) contains two similar turtles. Both turtles want to get to cell (*n*,<=*m*). Some cells of the table have obstacles but it is guaranteed that there aren't any obstacles in the upper left and lower right corner. A turtle (one or the other) can go from cell (*x*,<=*y*) to one of two cells (*x*<=+<=1,<=*y*) and (*x*,<=*y*<=+<=1), as long as the required cell doesn't contain an obstacle. The turtles have had an argument so they don't want to have any chance of meeting each other along the way. Help them find the number of ways in which they can go from cell (1,<=1) to cell (*n*,<=*m*).

More formally, find the number of pairs of non-intersecting ways from cell (1,<=1) to cell (*n*,<=*m*) modulo 1000000007 (109<=+<=7). Two ways are called non-intersecting if they have exactly two common points — the starting point and the final point.

Input Specification:
The first line contains two integers *n*,<=*m* (2<=≤<=*n*,<=*m*<=≤<=3000). Each of the following *n* lines contains *m* characters describing the table. The empty cells are marked by characters ".", the cells with obstacles are marked by "#".

It is guaranteed that the upper left and the lower right cells are empty.

Output Specification:
In a single line print a single integer — the number of pairs of non-intersecting paths from cell (1,<=1) to cell (*n*,<=*m*) modulo 1000000007 (109<=+<=7).

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

Demo Output:
['1\n', '1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the word `"abode"`. We can see that the letter `a` is in position `1` and `b` is in position `2`. In the alphabet, `a` and `b` are also in positions `1` and `2`. Notice also that `d` and `e` in `abode` occupy the positions they would occupy in the alphabet, which are positions `4` and `5`. 

Given an array of words, return an array of the number of letters that occupy their positions in the alphabet for each word. For example,
```
solve(["abode","ABc","xyzD"]) = [4, 3, 1]
```
See test cases for more examples.

Input will consist of alphabet characters, both uppercase and lowercase. No spaces.

Good luck!

If you like this Kata, please try: 

[Last digit symmetry](https://www.codewars.com/kata/59a9466f589d2af4c50001d8)

[Alternate capitalization](https://www.codewars.com/kata/59cfc000aeb2844d16000075)

~~~if:fortran
## Fortran-Specific Notes

Due to how strings and arrays work in Fortran, some of the strings in the input array will inevitably contain trailing whitespace.  **For this reason, please [trim](https://gcc.gnu.org/onlinedocs/gcc-4.3.4/gfortran/TRIM.html) your input strings before processing them.**
~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n lanterns in a row. The lantern i is placed in position i and has power equal to p_i.

Each lantern can be directed to illuminate either some lanterns to the left or some lanterns to the right. If the i-th lantern is turned to the left, it illuminates all such lanterns j that j ∈ [i - p_i, i - 1]. Similarly, if it is turned to the right, it illuminates all such lanterns j that j ∈ [i + 1, i + p_i].

Your goal is to choose a direction for each lantern so each lantern is illuminated by at least one other lantern, or report that it is impossible.

Input

The first line contains one integer t (1 ≤ t ≤ 10000) — the number of test cases.

Each test case consists of two lines. The first line contains one integer n (2 ≤ n ≤ 3 ⋅ 10^5) — the number of lanterns.

The second line contains n integers p_1, p_2, ..., p_n (0 ≤ p_i ≤ n) — the power of the i-th lantern.

The sum of n over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case, print the answer as follows:

If it is possible to direct all lanterns so that each lantern is illuminated, print YES in the first line and a string of n characters L and/or R (the i-th character is L if the i-th lantern is turned to the left, otherwise this character is R) in the second line. If there are multiple answers, you may print any of them.

If there is no answer, simply print NO for that test case.

Example

Input


4
8
0 0 3 1 1 1 1 2
2
1 1
2
2 2
2
0 1


Output


YES
RRLLLLRL
YES
RL
YES
RL
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n railway stations in Berland. They are connected to each other by n-1 railway sections. The railway network is connected, i.e. can be represented as an undirected tree.

You have a map of that network, so for each railway section you know which stations it connects.

Each of the n-1 sections has some integer value of the scenery beauty. However, these values are not marked on the map and you don't know them. All these values are from 1 to 10^6 inclusive.

You asked m passengers some questions: the j-th one told you three values:

  * his departure station a_j; 
  * his arrival station b_j; 
  * minimum scenery beauty along the path from a_j to b_j (the train is moving along the shortest path from a_j to b_j). 



You are planning to update the map and set some value f_i on each railway section — the scenery beauty. The passengers' answers should be consistent with these values.

Print any valid set of values f_1, f_2, ..., f_{n-1}, which the passengers' answer is consistent with or report that it doesn't exist.

Input

The first line contains a single integer n (2 ≤ n ≤ 5000) — the number of railway stations in Berland.

The next n-1 lines contain descriptions of the railway sections: the i-th section description is two integers x_i and y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i), where x_i and y_i are the indices of the stations which are connected by the i-th railway section. All the railway sections are bidirected. Each station can be reached from any other station by the railway.

The next line contains a single integer m (1 ≤ m ≤ 5000) — the number of passengers which were asked questions. Then m lines follow, the j-th line contains three integers a_j, b_j and g_j (1 ≤ a_j, b_j ≤ n; a_j ≠ b_j; 1 ≤ g_j ≤ 10^6) — the departure station, the arrival station and the minimum scenery beauty along his path.

Output

If there is no answer then print a single integer -1.

Otherwise, print n-1 integers f_1, f_2, ..., f_{n-1} (1 ≤ f_i ≤ 10^6), where f_i is some valid scenery beauty along the i-th railway section.

If there are multiple answers, you can print any of them.

Examples

Input


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


Output


5 3 5


Input


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


Output


5 3 1 2 1 


Input


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


Output


-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Let $p$ be any permutation of length $n$. We define the fingerprint $F(p)$ of $p$ as the sorted array of sums of adjacent elements in $p$. More formally,

$$F(p)=\mathrm{sort}([p_1+p_2,p_2+p_3,\ldots,p_{n-1}+p_n]).$$

For example, if $n=4$ and $p=[1,4,2,3],$ then the fingerprint is given by $F(p)=\mathrm{sort}([1+4,4+2,2+3])=\mathrm{sort}([5,6,5])=[5,5,6]$.

You are given a permutation $p$ of length $n$. Your task is to find a different permutation $p'$ with the same fingerprint. Two permutations $p$ and $p'$ are considered different if there is some index $i$ such that $p_i \ne p'_i$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 668$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 100$)  — the length of the permutation.

The second line of each test case contains $n$ integers $p_1,\ldots,p_n$ ($1\le p_i\le n$). It is guaranteed that $p$ is a permutation.


-----Output-----

For each test case, output $n$ integers $p'_1,\ldots, p'_n$ — a permutation such that $p'\ne p$ and $F(p')=F(p)$.

We can prove that for every permutation satisfying the input constraints, a solution exists.

If there are multiple solutions, you may output any.


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

Output
2 1
1 2 5 6 3 4
3 1 5 2 4



-----Note-----

In the first test case, $F(p)=\mathrm{sort}([1+2])=[3]$.

And $F(p')=\mathrm{sort}([2+1])=[3]$.

In the second test case, $F(p)=\mathrm{sort}([2+1,1+6,6+5,5+4,4+3])=\mathrm{sort}([3,7,11,9,7])=[3,7,7,9,11]$.

And $F(p')=\mathrm{sort}([1+2,2+5,5+6,6+3,3+4])=\mathrm{sort}([3,7,11,9,7])=[3,7,7,9,11]$.

In the third test case, $F(p)=\mathrm{sort}([2+4,4+3,3+1,1+5])=\mathrm{sort}([6,7,4,6])=[4,6,6,7]$.

And $F(p')=\mathrm{sort}([3+1,1+5,5+2,2+4])=\mathrm{sort}([4,6,7,6])=[4,6,6,7]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.
You are given an integer n and a 2D integer array roads where roads[i] = [u_{i}, v_{i}, time_{i}] means that there is a road between intersections u_{i} and v_{i} that takes time_{i} minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.
Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 10^{9} + 7.
Example 1:
Input:
n=7, m=10
edges= [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output:
4
Explaination:
The four ways to get there in 7 minutes are:
- 0  6
- 0  4  6
- 0  1  2  5  6
- 0  1  3  5  6
 
Example 2:
Input:
n=6, m=8
edges= [[0,5,8],[0,2,2],[0,1,1],[1,3,3],[1,2,3],[2,5,6],[3,4,2],[4,5,2]]
Output:
3
Explaination:
The three ways to get there in 8 minutes are:
- 0  5
- 0  2  5
- 0  1  3  4  5
 
Constraints:
1 <= n <= 200
n - 1 <= roads.length <= n * (n - 1) / 2
roads[i].length == 3
0 <= u_{i}, v_{i} <= n - 1
1 <= time_{i} <= 10^{9}
u_{i }!= v_{i}
There is at most one road connecting any two intersections.
You can reach any intersection from any other intersection.
Expected Time Complexity: O(M * logN + N)
Expected Space Complexity: O(M+N)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The teacher has sent an e-mail to her students with the following task: “Write a program that will determine and output the value of $X$ if given the statement:\[ X = \mathit{number}_1^{\mathit{pow}_1} + \mathit{number}_2^{\mathit{pow}_2} + \ldots + \mathit{number}_ N^{\mathit{pow}_ N} \]

and it holds that $\mathit{number}_1$, $\mathit{number}_2$ to $\mathit{number}_ N$ are integers, and $\mathit{pow}_1$, $\mathit{pow_2}$ to $\mathit{pow}_ N$ are one-digit integers.” Unfortunately, when the teacher downloaded the task to her computer, the text formatting was lost so the task transformed into a sum of $N$ integers:\[ X = P_1 + P_2 + \ldots + P_ N \]

For example, without text formatting, the original task in the form of $X = 21^2 + 125^3$ became a task in the form of $X = 212 + 1253$. Help the teacher by writing a program that will, for given $N$ integers from $P_1$ to $P_ N$ determine and output the value of $X$ from the original task.

-----Input-----
The first line of input contains the integer $N$ ($1 \leq N \leq 10$), the number of the addends from the task. Each of the following $N$ lines contains the integer $P_ i$ ($10 \leq P_ i \leq 9999$, $i = 1, \ldots , N$) from the task.

-----Output-----
The first and only line of output must contain the value of $X$ ($X \leq 1000000000$) from the original task.

-----Examples-----
Sample Input 1:
2
212
1253
Sample Output 1:
1953566

Sample Input 2:
5
23
17
43
52
22
Sample Output 2:
102

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anu has created her own function $f$: $f(x, y) = (x | y) - y$ where $|$ denotes the bitwise OR operation. For example, $f(11, 6) = (11|6) - 6 = 15 - 6 = 9$. It can be proved that for any nonnegative numbers $x$ and $y$ value of $f(x, y)$ is also nonnegative. 

She would like to research more about this function and has created multiple problems for herself. But she isn't able to solve all of them and needs your help. Here is one of these problems.

A value of an array $[a_1, a_2, \dots, a_n]$ is defined as $f(f(\dots f(f(a_1, a_2), a_3), \dots a_{n-1}), a_n)$ (see notes). You are given an array with not necessarily distinct elements. How should you reorder its elements so that the value of the array is maximal possible?


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$). Elements of the array are not guaranteed to be different.


-----Output-----

Output $n$ integers, the reordering of the array with maximum value. If there are multiple answers, print any.


-----Examples-----
Input
4
4 0 11 6

Output
11 6 4 0
Input
1
13

Output
13 


-----Note-----

In the first testcase, value of the array $[11, 6, 4, 0]$ is $f(f(f(11, 6), 4), 0) = f(f(9, 4), 0) = f(9, 0) = 9$.

$[11, 4, 0, 6]$ is also a valid answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are standing on top of an amazing Himalayan mountain. The view is absolutely breathtaking! you want to take a picture on your phone, but... your memory is full again! ok, time to sort through your shuffled photos and make some space...

Given a gallery of photos, write a function to sort through your pictures.
You get a random hard disk drive full of pics, you must return an array with the 5 most recent ones PLUS the next one (same year and number following the one of the last).

You will always get at least a photo and all pics will be in the format `YYYY.imgN`

Examples:
```python
sort_photos["2016.img1","2016.img2","2015.img3","2016.img4","2013.img5"]) ==["2013.img5","2015.img3","2016.img1","2016.img2","2016.img4","2016.img5"]
sort_photos["2016.img1"]) ==["2016.img1","2016.img2"]
```

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