vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Difference Row

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You want to arrange *n* integers *a*1,<=*a*2,<=...,<=*a**n* in some order in a row. Let's define the value of an arrangement as the sum of differences between all pairs of adjacent integers.

More formally, let's denote some arrangement as a sequence of integers *x*1,<=*x*2,<=...,<=*x**n*, where sequence *x* is a permutation of sequence *a*. The value of such an arrangement is (*x*1<=-<=*x*2)<=+<=(*x*2<=-<=*x*3)<=+<=...<=+<=(*x**n*<=-<=1<=-<=*x**n*).

Find the largest possible value of an arrangement. Then, output the lexicographically smallest sequence *x* that corresponds to an arrangement of the largest possible value.

Input Specification:
The first line of the input contains integer *n* (2<=≤<=*n*<=≤<=100). The second line contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (|*a**i*|<=≤<=1000).

Output Specification:
Print the required sequence *x*1,<=*x*2,<=...,<=*x**n*. Sequence *x* should be the lexicographically smallest permutation of *a* that corresponds to an arrangement of the largest possible value.

Demo Input:
['5\n100 -100 50 0 -50\n']

Demo Output:
['100 -50 0 50 -100 \n']

Note:
In the sample test case, the value of the output arrangement is (100 - ( - 50)) + (( - 50) - 0) + (0 - 50) + (50 - ( - 100)) = 200. No other arrangement has a larger value, and among all arrangements with the value of 200, the output arrangement is the lexicographically smallest one.

Sequence *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ... , *x*<sub class="lower-index">*p*</sub> is lexicographically smaller than sequence *y*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">2</sub>, ... , *y*<sub class="lower-index">*p*</sub> if there exists an integer *r* (0 ≤ *r* &lt; *p*) such that *x*<sub class="lower-index">1</sub> = *y*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub> = *y*<sub class="lower-index">2</sub>, ... , *x*<sub class="lower-index">*r*</sub> = *y*<sub class="lower-index">*r*</sub> and *x*<sub class="lower-index">*r* + 1</sub> &lt; *y*<sub class="lower-index">*r* + 1</sub>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tapan and Divya have a rectangular shaped chocolate bar with chocolates labeled T, D and U. They want to split the bar into exactly two pieces such that:

Tarun's piece can not contain any chocolate labeled D and similarly, Divya's piece can not contain any chocolate labeled T. All chocolates in each piece must be connected (two chocolates are connected if they share an edge), i.e. the chocolates should form one connected component.

The absolute difference between the number of chocolates in pieces should be at most K.

In any piece, there should not be 4 adjacent chocolates that form a square, i.e. there should not be a fragment like this:

XX
XX

Input Format

The first line of the input contains 3 integers M, N and K separated by a single space.
M lines follow, each of which contains N characters. Each character is 'T','D' or 'U'.

Constraints

0≤ M, N ≤8
0≤ K ≤ M * N

Output Format

A single line containing the number of ways to divide the chocolate bar.

SAMPLE INPUT
2 2 4
UU
UU

SAMPLE OUTPUT
12

Explanation

There are 24 = 16 possible separations. The 4 invalid are:

TT

TT
DD

DD
DT

TD
TD

DT

Some of the valid ones are:

TD

TD
TT

DD
DD

TT
DT

DT

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given array $a_1, a_2, \dots, a_n$. Find the subsegment $a_l, a_{l+1}, \dots, a_r$ ($1 \le l \le r \le n$) with maximum arithmetic mean $\frac{1}{r - l + 1}\sum\limits_{i=l}^{r}{a_i}$ (in floating-point numbers, i.e. without any rounding).

If there are many such subsegments find the longest one.


-----Input-----

The first line contains single integer $n$ ($1 \le n \le 10^5$) — length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the array $a$.


-----Output-----

Print the single integer — the length of the longest subsegment with maximum possible arithmetic mean.


-----Example-----
Input
5
6 1 6 6 0

Output
2



-----Note-----

The subsegment $[3, 4]$ is the longest among all subsegments with maximum arithmetic mean.

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
A teacher decides to give toffees to his students. He asks *n* students to stand in a queue. Since the teacher is very partial, he follows the following rule to distribute toffees.

He looks at the first two students and gives more toffees to the student having higher marks than the other one. If they have the same marks they get the same number of toffees. The same procedure is followed for each pair of adjacent students starting from the first one to the last one.

It is given that each student receives at least one toffee. You have to find the number of toffees given to each student by the teacher such that the total number of toffees is minimum.

Input Specification:
The first line of input contains the number of students *n* (2<=≤<=*n*<=≤<=1000). The second line gives (*n*<=-<=1) characters consisting of "L", "R" and "=". For each pair of adjacent students "L" means that the left student has higher marks, "R" means that the right student has higher marks and "=" means that both have equal marks.

Output Specification:
Output consists of *n* integers separated by a space representing the number of toffees each student receives in the queue starting from the first one to the last one.

Demo Input:
['5\nLRLR\n', '5\n=RRR\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every person likes prime numbers. Alice is a person, thus she also shares the love for them. Bob wanted to give her an affectionate gift but couldn't think of anything inventive. Hence, he will be giving her a graph. How original, Bob! Alice will surely be thrilled!

When building the graph, he needs four conditions to be satisfied:   It must be a simple undirected graph, i.e. without multiple (parallel) edges and self-loops.  The number of vertices must be exactly $n$ — a number he selected. This number is not necessarily prime.  The total number of edges must be prime.  The degree (i.e. the number of edges connected to the vertex) of each vertex must be prime. 

Below is an example for $n = 4$. The first graph (left one) is invalid as the degree of vertex $2$ (and $4$) equals to $1$, which is not prime. The second graph (middle one) is invalid as the total number of edges is $4$, which is not a prime number. The third graph (right one) is a valid answer for $n = 4$.  [Image] 

Note that the graph can be disconnected.

Please help Bob to find any such graph!


-----Input-----

The input consists of a single integer $n$ ($3 \leq n \leq 1\,000$) — the number of vertices.


-----Output-----

If there is no graph satisfying the conditions, print a single line containing the integer $-1$.

Otherwise, first print a line containing a prime number $m$ ($2 \leq m \leq \frac{n(n-1)}{2}$) — the number of edges in the graph. Then, print $m$ lines, the $i$-th of which containing two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$) — meaning that there is an edge between vertices $u_i$ and $v_i$. The degree of each vertex must be prime. There must be no multiple (parallel) edges or self-loops.

If there are multiple solutions, you may print any of them.

Note that the graph can be disconnected.


-----Examples-----
Input
4

Output
5
1 2
1 3
2 3
2 4
3 4
Input
8

Output
13
1 2
1 3
2 3
1 4
2 4
1 5
2 5
1 6
2 6
1 7
1 8
5 8
7 8



-----Note-----

The first example was described in the statement.

In the second example, the degrees of vertices are $[7, 5, 2, 2, 3, 2, 2, 3]$. Each of these numbers is prime. Additionally, the number of edges, $13$, is also a prime number, hence both conditions are satisfied. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
$Gogi$, $Tapu$ and $Sonu$ are the elite members of $Tapu$ $Sena$. $Gogi$ is always stoned and asks absurd questions, But this time he asked a question which seems to be very serious and interesting. $Tapu$ wants to solve this question to impress $Sonu$. He  gave an array of length N to $Tapu$, $Tapu$ can perform the following operations exactly once:
- Remove any subarray from the given array given the resulting array formed after the removal is non-empty.    
- Reverse the whole array.
Remember you can’t shuffle the elements of the array.
Tapu needs to find out the maximum possible GCD of all the numbers in the array after applying the given operations exactly once. Tapu is very weak at programming, he wants you to solve this problem so that he can impress $Sonu$.

-----Input:-----
- The first line contains $T$, the number of test cases.
- For each test case
-FIrst line contains $N$.
- Last line contains $N$ numbers of the array. 

-----Output:-----
A single integer in a new line, maximum possible GCD. 

-----Constraints-----
- $1 \leq T \leq 10^2$
- $1 \leq N \leq 10^4$
- $1 \leq a[i] \leq 10^9$

Summation of N for all testcases is less than $10^6$ 

-----Sample Input 1:-----
1
1
2

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine that there is a group of three friends: A, B and С. A owes B 20 rubles and B owes C 20 rubles. The total sum of the debts is 40 rubles. You can see that the debts are not organized in a very optimal manner. Let's rearrange them like that: assume that A owes C 20 rubles and B doesn't owe anything to anybody. The debts still mean the same but the total sum of the debts now equals 20 rubles.

This task is a generalisation of a described example. Imagine that your group of friends has n people and you know the debts between the people. Optimize the given debts without changing their meaning. In other words, finally for each friend the difference between the total money he should give and the total money he should take must be the same. Print the minimum sum of all debts in the optimal rearrangement of the debts. See the notes to the test samples to better understand the problem.

Input

The first line contains two integers n and m (1 ≤ n ≤ 100; 0 ≤ m ≤ 104). The next m lines contain the debts. The i-th line contains three integers ai, bi, ci (1 ≤ ai, bi ≤ n; ai ≠ bi; 1 ≤ ci ≤ 100), which mean that person ai owes person bi ci rubles.

Assume that the people are numbered by integers from 1 to n.

It is guaranteed that the same pair of people occurs at most once in the input. The input doesn't simultaneously contain pair of people (x, y) and pair of people (y, x).

Output

Print a single integer — the minimum sum of debts in the optimal rearrangement.

Examples

Input

5 3
1 2 10
2 3 1
2 4 1


Output

10


Input

3 0


Output

0


Input

4 3
1 2 1
2 3 1
3 1 1


Output

0

Note

In the first sample, you can assume that person number 1 owes 8 rubles to person number 2, 1 ruble to person number 3 and 1 ruble to person number 4. He doesn't owe anybody else anything. In the end, the total debt equals 10.

In the second sample, there are no debts.

In the third sample, you can annul all the debts.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an grid with $N$ rows and $M$ columns, your task is to find a tour such that: 
 - The tour has length at least two
 - All squares in the grid are visited exactly once
 - Let $a_1, \dots , a_{NM}$ be the sequence of visited squares. Then $d(a_ k$, $a_{k+1}) = 2$ or $3$ for every $1 \leq k < NM$. Also, $d(a_{NM}, a_1) = 2$ or $3$.

Here, $d(p, q)$ denotes the Manhattan distance between $p$ and $q$. More precisely, if $p$ is the square on row $r_ p$ and column $c_ p$ and $q$ is the square on row $r_ q$ and column $c_ q$, then we write $p = (r_ p, c_ p), q = (r_ q, c_ q)$ and $d(p, q) = |r_ p - r_ q| + |c_ p - c_ q|$.

-----Input-----
The first and only line of input consists of two integers $N$ and $M$ ($1 \leq N, M \leq 200$).

-----Output-----
If there is no such tour, output -1. Otherwise, output $N \times M$ lines. The $i$th line contains two space-separated integers, denoting the row and column numbers of $a_ i$. If there is more than one such tour, any one will be accepted.

-----Examples-----
Sample Input:
2 3
Sample Output:
1 1
2 2
1 3
2 1
1 2
2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Rebel fleet is afraid that the Empire might want to strike back again. Princess Heidi needs to know if it is possible to assign R Rebel spaceships to guard B bases so that every base has exactly one guardian and each spaceship has exactly one assigned base (in other words, the assignment is a perfect matching). Since she knows how reckless her pilots are, she wants to be sure that any two (straight) paths – from a base to its assigned spaceship – do not intersect in the galaxy plane (that is, in 2D), and so there is no risk of collision.


-----Input-----

The first line contains two space-separated integers R, B(1 ≤ R, B ≤ 10). For 1 ≤ i ≤ R, the i + 1-th line contains two space-separated integers x_{i} and y_{i} (|x_{i}|, |y_{i}| ≤ 10000) denoting the coordinates of the i-th Rebel spaceship. The following B lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and that no three points are on the same line.


-----Output-----

If it is possible to connect Rebel spaceships and bases so as satisfy the constraint, output Yes, otherwise output No (without quote).


-----Examples-----
Input
3 3
0 0
2 0
3 1
-2 1
0 3
2 2

Output
Yes

Input
2 1
1 0
2 2
3 1

Output
No



-----Note-----

For the first example, one possible way is to connect the Rebels and bases in order.

For the second example, there is no perfect matching between Rebels and bases.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider X as the  aleatory  variable that count the number of letters in a word. Write a function that, give in input an array of words (strings), calculate the  variance  of X.
Max decimal of the variance : 4.

Some wiki: Variance ,
 Aleatory variable 

Example:

Consider "Hello" and "World":

X is { 5 } with P(X = 5) = 1 beacuse the two words has the same length.  
So E[X] = 5 x 1 = 5 and the standard formula for variance is E[(X - u)^2] so  1 x (5-5)^2 = 0
or you can calculate with the other formula E[X^2] - E[X]^2 = 5^2 x 1 - 5^2 = 0

Consider "Hi" and "World":

X is { 2, 5 } with P(X = 5) = 1/2 and P(X = 2) = 1/2.  
So E[X] = 5 x 1/2 + 2 x 1/2 = 3.5 and the standard formula for variance is E[(X - u)^2] so  1/2 x (2-3.5)^2 + 1/2 x (5 - 3.5)^2 = 2.25
or you can calculate with the other formula E[X^2] - E[X]^2 = (5^2 x 1/2 + 2^2 x 1/2) - 3.5^2 = 2.25

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ari the monster is not an ordinary monster. She is the hidden identity of Super M, the Byteforces’ superhero. Byteforces is a country that consists of n cities, connected by n - 1 bidirectional roads. Every road connects exactly two distinct cities, and the whole road system is designed in a way that one is able to go from any city to any other city using only the given roads. There are m cities being attacked by humans. So Ari... we meant Super M have to immediately go to each of the cities being attacked to scare those bad humans. Super M can pass from one city to another only using the given roads. Moreover, passing through one road takes her exactly one kron - the time unit used in Byteforces.  [Image] 

However, Super M is not on Byteforces now - she is attending a training camp located in a nearby country Codeforces. Fortunately, there is a special device in Codeforces that allows her to instantly teleport from Codeforces to any city of Byteforces. The way back is too long, so for the purpose of this problem teleportation is used exactly once.

You are to help Super M, by calculating the city in which she should teleport at the beginning in order to end her job in the minimum time (measured in krons). Also, provide her with this time so she can plan her way back to Codeforces.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 123456) - the number of cities in Byteforces, and the number of cities being attacked respectively.

Then follow n - 1 lines, describing the road system. Each line contains two city numbers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n) - the ends of the road i.

The last line contains m distinct integers - numbers of cities being attacked. These numbers are given in no particular order.


-----Output-----

First print the number of the city Super M should teleport to. If there are many possible optimal answers, print the one with the lowest city number.

Then print the minimum possible time needed to scare all humans in cities being attacked, measured in Krons.

Note that the correct answer is always unique.


-----Examples-----
Input
7 2
1 2
1 3
1 4
3 5
3 6
3 7
2 7

Output
2
3

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

Output
2
4



-----Note-----

In the first sample, there are two possibilities to finish the Super M's job in 3 krons. They are:

$2 \rightarrow 1 \rightarrow 3 \rightarrow 7$ and $7 \rightarrow 3 \rightarrow 1 \rightarrow 2$.

However, you should choose the first one as it starts in the city with the lower number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snackdown 2019 is coming! There are two rounds (round A and round B) after the qualification round. From both of them, teams can qualify to the pre-elimination round. According to the rules, in each of these two rounds, teams are sorted in descending order by their score and each team with a score greater or equal to the score of the team at the $K=1500$-th place advances to the pre-elimination round (this means it is possible to have more than $K$ qualified teams from each round in the case of one or more ties after the $K$-th place).
Today, the organizers ask you to count the number of teams which would qualify for the pre-elimination round from round A for a given value of $K$ (possibly different from $1500$). They provided the scores of all teams to you; you should ensure that all teams scoring at least as many points as the $K$-th team qualify.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $S_1, S_2, \dots, S_N$.

-----Output-----
For each test case, print a single line containing one integer — the number of qualified teams.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le K \le N \le 10^5$
- $1 \le S_i \le 10^9$ for each valid $i$
- the sum of $N$ for all test cases does not exceed $10^6$

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

-----Example Output-----
2
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fishing Prince loves trees, and he especially loves trees with only one centroid. The tree is a connected graph without cycles.

A vertex is a centroid of a tree only when you cut this vertex (remove it and remove all edges from this vertex), the size of the largest connected component of the remaining graph is the smallest possible.

For example, the centroid of the following tree is 2, because when you cut it, the size of the largest connected component of the remaining graph is 2 and it can't be smaller.

<image>

However, in some trees, there might be more than one centroid, for example:

<image>

Both vertex 1 and vertex 2 are centroids because the size of the largest connected component is 3 after cutting each of them.

Now Fishing Prince has a tree. He should cut one edge of the tree (it means to remove the edge). After that, he should add one edge. The resulting graph after these two operations should be a tree. He can add the edge that he cut.

He wants the centroid of the resulting tree to be unique. Help him and find any possible way to make the operations. It can be proved, that at least one such way always exists.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤ t≤ 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (3≤ n≤ 10^5) — the number of vertices.

Each of the next n-1 lines contains two integers x, y (1≤ x,y≤ n). It means, that there exists an edge connecting vertices x and y.

It's guaranteed that the given graph is a tree.

It's guaranteed that the sum of n for all test cases does not exceed 10^5.

Output

For each test case, print two lines.

In the first line print two integers x_1, y_1 (1 ≤ x_1, y_1 ≤ n), which means you cut the edge between vertices x_1 and y_1. There should exist edge connecting vertices x_1 and y_1.

In the second line print two integers x_2, y_2 (1 ≤ x_2, y_2 ≤ n), which means you add the edge between vertices x_2 and y_2.

The graph after these two operations should be a tree.

If there are multiple solutions you can print any.

Example

Input


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


Output


1 2
1 2
1 3
2 3

Note

Note that you can add the same edge that you cut.

In the first test case, after cutting and adding the same edge, the vertex 2 is still the only centroid.

In the second test case, the vertex 2 becomes the only centroid after cutting the edge between vertices 1 and 3 and adding the edge between vertices 2 and 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of integers $a_1,a_2,\ldots,a_n$. Find the maximum possible value of $a_ia_ja_ka_la_t$ among all five indices $(i, j, k, l, t)$ ($i<j<k<l<t$).


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1\le t\le 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($5\le n\le 10^5$) — the size of the array.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-3\times 10^3\le a_i\le 3\times 10^3$) — given array.

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


-----Output-----

For each test case, print one integer — the answer to the problem.


-----Example-----
Input
4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1

Output
-120
12
0
945



-----Note-----

In the first test case, choosing $a_1,a_2,a_3,a_4,a_5$ is a best choice: $(-1)\cdot (-2) \cdot (-3)\cdot (-4)\cdot (-5)=-120$.

In the second test case, choosing $a_1,a_2,a_3,a_5,a_6$ is a best choice: $(-1)\cdot (-2) \cdot (-3)\cdot 2\cdot (-1)=12$.

In the third test case, choosing $a_1,a_2,a_3,a_4,a_5$ is a best choice: $(-1)\cdot 0\cdot 0\cdot 0\cdot (-1)=0$.

In the fourth test case, choosing $a_1,a_2,a_3,a_4,a_6$ is a best choice: $(-9)\cdot (-7) \cdot (-5)\cdot (-3)\cdot 1=945$.

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