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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's denote a function 



You are given an array *a* consisting of *n* integers. You have to calculate the sum of *d*(*a**i*,<=*a**j*) over all pairs (*i*,<=*j*) such that 1<=≤<=*i*<=≤<=*j*<=≤<=*n*.

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=200000) — the number of elements in *a*.

The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=109) — elements of the array.

Output Specification:
Print one integer — the sum of *d*(*a**i*,<=*a**j*) over all pairs (*i*,<=*j*) such that 1<=≤<=*i*<=≤<=*j*<=≤<=*n*.

Demo Input:
['5\n1 2 3 1 3\n', '4\n6 6 5 5\n', '4\n6 6 4 4\n']

Demo Output:
['4\n', '0\n', '-8\n']

Note:
In the first example:
 1.  *d*(*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>) = 0; 1.  *d*(*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">3</sub>) = 2; 1.  *d*(*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">4</sub>) = 0; 1.  *d*(*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">5</sub>) = 2; 1.  *d*(*a*<sub class="lower-index">2</sub>, *a*<sub class="lower-index">3</sub>) = 0; 1.  *d*(*a*<sub class="lower-index">2</sub>, *a*<sub class="lower-index">4</sub>) = 0; 1.  *d*(*a*<sub class="lower-index">2</sub>, *a*<sub class="lower-index">5</sub>) = 0; 1.  *d*(*a*<sub class="lower-index">3</sub>, *a*<sub class="lower-index">4</sub>) =  - 2; 1.  *d*(*a*<sub class="lower-index">3</sub>, *a*<sub class="lower-index">5</sub>) = 0; 1.  *d*(*a*<sub class="lower-index">4</sub>, *a*<sub class="lower-index">5</sub>) = 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fox Ciel has a robot on a 2D plane. Initially it is located in (0, 0). Fox Ciel code a command to it. The command was represented by string s. Each character of s is one move operation. There are four move operations at all:  'U': go up, (x, y)  →  (x, y+1);  'D': go down, (x, y)  →  (x, y-1);  'L': go left, (x, y)  →  (x-1, y);  'R': go right, (x, y)  →  (x+1, y). 

The robot will do the operations in s from left to right, and repeat it infinite times. Help Fox Ciel to determine if after some steps the robot will located in (a, b).


-----Input-----

The first line contains two integers a and b, ( - 10^9 ≤ a, b ≤ 10^9). The second line contains a string s (1 ≤ |s| ≤ 100, s only contains characters 'U', 'D', 'L', 'R') — the command.


-----Output-----

Print "Yes" if the robot will be located at (a, b), and "No" otherwise.


-----Examples-----
Input
2 2
RU

Output
Yes

Input
1 2
RU

Output
No

Input
-1 1000000000
LRRLU

Output
Yes

Input
0 0
D

Output
Yes



-----Note-----

In the first and second test case, command string is "RU", so the robot will go right, then go up, then right, and then up and so on.

The locations of its moves are (0, 0)  →  (1, 0)  →  (1, 1)  →  (2, 1)  →  (2, 2)  →  ...

So it can reach (2, 2) but not (1, 2).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya has an array $a$ consisting of $n$ integers. He has learned partial sums recently, and now he can calculate the sum of elements on any segment of the array really fast. The segment is a non-empty sequence of elements standing one next to another in the array.

Now he wonders what is the number of segments in his array with the sum less than $t$. Help Petya to calculate this number.

More formally, you are required to calculate the number of pairs $l, r$ ($l \le r$) such that $a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$.


-----Input-----

The first line contains two integers $n$ and $t$ ($1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$).

The second line contains a sequence of integers $a_1, a_2, \dots, a_n$ ($|a_{i}| \le 10^{9}$) — the description of Petya's array. Note that there might be negative, zero and positive elements.


-----Output-----

Print the number of segments in Petya's array with the sum of elements less than $t$.


-----Examples-----
Input
5 4
5 -1 3 4 -1

Output
5

Input
3 0
-1 2 -3

Output
4

Input
4 -1
-2 1 -2 3

Output
3



-----Note-----

In the first example the following segments have sum less than $4$:  $[2, 2]$, sum of elements is $-1$  $[2, 3]$, sum of elements is $2$  $[3, 3]$, sum of elements is $3$  $[4, 5]$, sum of elements is $3$  $[5, 5]$, sum of elements is $-1$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of $n$ digits $d_1d_2 \dots d_{n}$. You need to paint all the digits in two colors so that:  each digit is painted either in the color $1$ or in the color $2$;  if you write in a row from left to right all the digits painted in the color $1$, and then after them all the digits painted in the color $2$, then the resulting sequence of $n$ digits will be non-decreasing (that is, each next digit will be greater than or equal to the previous digit). 

For example, for the sequence $d=914$ the only valid coloring is $211$ (paint in the color $1$ two last digits, paint in the color $2$ the first digit). But $122$ is not a valid coloring ($9$ concatenated with $14$ is not a non-decreasing sequence).

It is allowed that either of the two colors is not used at all. Digits painted in the same color are not required to have consecutive positions.

Find any of the valid ways to paint the given sequence of digits or determine that it is impossible to do.


-----Input-----

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

The first line of each test case contains an integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of a given sequence of digits.

The next line contains a sequence of $n$ digits $d_1d_2 \dots d_{n}$ ($0 \le d_i \le 9$). The digits are written in a row without spaces or any other separators. The sequence can start with 0.

It is guaranteed that the sum of the values ​​of $n$ for all test cases in the input does not exceed $2\cdot10^5$.


-----Output-----

Print $t$ lines — the answers to each of the test cases in the input.

If there is a solution for a test case, the corresponding output line should contain any of the valid colorings written as a string of $n$ digits $t_1t_2 \dots t_n$ ($1 \le t_i \le 2$), where $t_i$ is the color the $i$-th digit is painted in. If there are several feasible solutions, print any of them.

If there is no solution, then the corresponding output line should contain a single character '-' (the minus sign).


-----Example-----
Input
5
12
040425524644
1
0
9
123456789
2
98
3
987

Output
121212211211
1
222222222
21
-



-----Note-----

In the first test case, $d=040425524644$. The output $t=121212211211$ is correct because $0022444$ (painted in $1$) concatenated with $44556$ (painted in $2$) is $002244444556$ which is a sorted sequence of $n$ given digits.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S of length N consisting of lowercase English letters.
We will cut this string at one position into two strings X and Y.
Here, we would like to maximize the number of different letters contained in both X and Y.
Find the largest possible number of different letters contained in both X and Y when we cut the string at the optimal position.

-----Constraints-----
 - 2 \leq N \leq 100
 - |S| = N
 - S consists of lowercase English letters.

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

-----Output-----
Print the largest possible number of different letters contained in both X and Y.

-----Sample Input-----
6
aabbca

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

If we cut the string between the third and fourth letters into X = aab and Y = bca, the letters contained in both X and Y are a and b.
There will never be three or more different letters contained in both X and Y, so the answer is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let {\rm comb}(n,r) be the number of ways to choose r objects from among n objects, disregarding order.
From n non-negative integers a_1, a_2, ..., a_n, select two numbers a_i > a_j so that {\rm comb}(a_i,a_j) is maximized.
If there are multiple pairs that maximize the value, any of them is accepted.

-----Constraints-----
 - 2 \leq n \leq 10^5
 - 0 \leq a_i \leq 10^9
 - a_1,a_2,...,a_n are pairwise distinct.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
n
a_1 a_2 ... a_n

-----Output-----
Print a_i and a_j that you selected, with a space in between.

-----Sample Input-----
5
6 9 4 2 11

-----Sample Output-----
11 6

\rm{comb}(a_i,a_j) for each possible selection is as follows:
 - \rm{comb}(4,2)=6 
 - \rm{comb}(6,2)=15 
 - \rm{comb}(6,4)=15 
 - \rm{comb}(9,2)=36 
 - \rm{comb}(9,4)=126 
 - \rm{comb}(9,6)=84 
 - \rm{comb}(11,2)=55 
 - \rm{comb}(11,4)=330 
 - \rm{comb}(11,6)=462 
 - \rm{comb}(11,9)=55
Thus, we should print 11 and 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little X and Little Z are good friends. They always chat online. But both of them have schedules.

Little Z has fixed schedule. He always online at any moment of time between a_1 and b_1, between a_2 and b_2, ..., between a_{p} and b_{p} (all borders inclusive). But the schedule of Little X is quite strange, it depends on the time when he gets up. If he gets up at time 0, he will be online at any moment of time between c_1 and d_1, between c_2 and d_2, ..., between c_{q} and d_{q} (all borders inclusive). But if he gets up at time t, these segments will be shifted by t. They become [c_{i} + t, d_{i} + t] (for all i).

If at a moment of time, both Little X and Little Z are online simultaneosly, they can chat online happily. You know that Little X can get up at an integer moment of time between l and r (both borders inclusive). Also you know that Little X wants to get up at the moment of time, that is suitable for chatting with Little Z (they must have at least one common moment of time in schedules). How many integer moments of time from the segment [l, r] suit for that?


-----Input-----

The first line contains four space-separated integers p, q, l, r (1 ≤  p, q ≤ 50; 0 ≤ l ≤ r ≤ 1000).

Each of the next p lines contains two space-separated integers a_{i}, b_{i} (0 ≤ a_{i} < b_{i} ≤ 1000). Each of the next q lines contains two space-separated integers c_{j}, d_{j} (0 ≤ c_{j} < d_{j} ≤ 1000).

It's guaranteed that b_{i} < a_{i} + 1 and d_{j} < c_{j} + 1 for all valid i and j.


-----Output-----

Output a single integer — the number of moments of time from the segment [l, r] which suit for online conversation.


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

Output
3

Input
2 3 0 20
15 17
23 26
1 4
7 11
15 17

Output
20

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a tree T (that is, a connected graph without cycles) with n vertices labelled 1 through n. We start the following process with T: while T has more than one vertex, do the following:

  * choose a random edge of T equiprobably;
  * shrink the chosen edge: if the edge was connecting vertices v and u, erase both v and u and create a new vertex adjacent to all vertices previously adjacent to either v or u. The new vertex is labelled either v or u equiprobably.



At the end of the process, T consists of a single vertex labelled with one of the numbers 1, …, n. For each of the numbers, what is the probability of this number becoming the label of the final vertex?

Input

The first line contains a single integer n (1 ≤ n ≤ 50).

The following n - 1 lines describe the tree edges. Each of these lines contains two integers u_i, v_i — labels of vertices connected by the respective edge (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i). It is guaranteed that the given graph is a tree.

Output

Print n floating numbers — the desired probabilities for labels 1, …, n respectively. All numbers should be correct up to 10^{-6} relative or absolute precision.

Examples

Input

4
1 2
1 3
1 4


Output

0.1250000000
0.2916666667
0.2916666667
0.2916666667


Input

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


Output

0.0850694444
0.0664062500
0.0664062500
0.1955295139
0.1955295139
0.1955295139
0.1955295139

Note

In the first sample, the resulting vertex has label 1 if and only if for all three edges the label 1 survives, hence the probability is 1/2^3 = 1/8. All other labels have equal probability due to symmetry, hence each of them has probability (1 - 1/8) / 3 = 7/24.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a consisting of n integers.

Let min(l, r) be the minimum value among a_l, a_{l + 1}, …, a_r and max(l, r) be the maximum value among a_l, a_{l + 1}, …, a_r.

Your task is to choose three positive (greater than 0) integers x, y and z such that:

  * x + y + z = n; 
  * max(1, x) = min(x + 1, x + y) = max(x + y + 1, n). 



In other words, you have to split the array a into three consecutive non-empty parts that cover the whole array and the maximum in the first part equals the minimum in the second part and equals the maximum in the third part (or determine it is impossible to find such a partition).

Among all such triples (partitions), you can choose any.

You have to answer t independent test cases.

Input

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

The first line of the test case contains one integer n (3 ≤ n ≤ 2 ⋅ 10^5) — the length of a.

The second line of the test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9), where a_i is the i-th element of a.

It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

For each test case, print the answer: NO in the only line if there is no such partition of a that satisfies the conditions from the problem statement. Otherwise, print YES in the first line and three integers x, y and z (x + y + z = n) in the second line.

If there are several answers, you can print any.

Example

Input


6
11
1 2 3 3 3 4 4 3 4 2 1
8
2 9 1 7 3 9 4 1
9
2 1 4 2 4 3 3 1 2
7
4 2 1 1 4 1 4
5
1 1 1 1 1
7
4 3 4 3 3 3 4


Output


YES
6 1 4
NO
YES
2 5 2
YES
4 1 2
YES
1 1 3
YES
2 1 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've got an undirected graph, consisting of n vertices and m edges. We will consider the graph's vertices numbered with integers from 1 to n. Each vertex of the graph has a color. The color of the i-th vertex is an integer c_{i}.

Let's consider all vertices of the graph, that are painted some color k. Let's denote a set of such as V(k). Let's denote the value of the neighbouring color diversity for color k as the cardinality of the set Q(k) = {c_{u} :  c_{u} ≠ k and there is vertex v belonging to set V(k) such that nodes v and u are connected by an edge of the graph}.

Your task is to find such color k, which makes the cardinality of set Q(k) maximum. In other words, you want to find the color that has the most diverse neighbours. Please note, that you want to find such color k, that the graph has at least one vertex with such color.


-----Input-----

The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 10^5) — the number of vertices end edges of the graph, correspondingly. The second line contains a sequence of integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^5) — the colors of the graph vertices. The numbers on the line are separated by spaces.

Next m lines contain the description of the edges: the i-th line contains two space-separated integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}) — the numbers of the vertices, connected by the i-th edge. 

It is guaranteed that the given graph has no self-loops or multiple edges.


-----Output-----

Print the number of the color which has the set of neighbours with the maximum cardinality. It there are multiple optimal colors, print the color with the minimum number. Please note, that you want to find such color, that the graph has at least one vertex with such color.


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

Output
3

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

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One unknown hacker wants to get the admin's password of AtForces testing system, to get problems from the next contest. To achieve that, he sneaked into the administrator's office and stole a piece of paper with a list of $n$ passwords — strings, consists of small Latin letters.

Hacker went home and started preparing to hack AtForces. He found that the system contains only passwords from the stolen list and that the system determines the equivalence of the passwords $a$ and $b$ as follows:  two passwords $a$ and $b$ are equivalent if there is a letter, that exists in both $a$ and $b$;  two passwords $a$ and $b$ are equivalent if there is a password $c$ from the list, which is equivalent to both $a$ and $b$. 

If a password is set in the system and an equivalent one is applied to access the system, then the user is accessed into the system.

For example, if the list contain passwords "a", "b", "ab", "d", then passwords "a", "b", "ab" are equivalent to each other, but the password "d" is not equivalent to any other password from list. In other words, if:  admin's password is "b", then you can access to system by using any of this passwords: "a", "b", "ab";  admin's password is "d", then you can access to system by using only "d". 

Only one password from the list is the admin's password from the testing system. Help hacker to calculate the minimal number of passwords, required to guaranteed access to the system. Keep in mind that the hacker does not know which password is set in the system.


-----Input-----

The first line contain integer $n$ ($1 \le n \le 2 \cdot 10^5$) — number of passwords in the list. Next $n$ lines contains passwords from the list – non-empty strings $s_i$, with length at most $50$ letters. Some of the passwords may be equal.

It is guaranteed that the total length of all passwords does not exceed $10^6$ letters. All of them consist only of lowercase Latin letters.


-----Output-----

In a single line print the minimal number of passwords, the use of which will allow guaranteed to access the system.


-----Examples-----
Input
4
a
b
ab
d

Output
2
Input
3
ab
bc
abc

Output
1
Input
1
codeforces

Output
1


-----Note-----

In the second example hacker need to use any of the passwords to access the system.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.
We repeatedly make duplicate removals on S until we no longer can.
Return the final string after all such duplicate removals have been made.  It is guaranteed the answer is unique.
 
Example 1:
Input: "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

 
Note:

1 <= S.length <= 20000
S consists only of English lowercase letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We always hope things in our lives will run smoothly, and having smooth arrays may help. An array $A$ of $N$ non-negative integers is $K_ S$-smooth if the sum of every set of $K$ consecutive integers is exactly $S$. Unfortunately, not all arrays are $K_ S$-smooth. In fact, all $K_ S$-smooth arrays must contain a repeating pattern of length $K$. The image to the right shows an array of smoothies, and is totally unrelated to this problem, but may help you relax. 

Any array can be made $K_ S$-smooth by changing its elements. In each change one element may be modified to any integer between $0$ and $S$, inclusive. You want to make all of your arrays smooth, but you don’t want to make any more changes than necessary. So the question is: What is the minimum number of changes you have to make so that a given array would become $K_ S$-smooth?

-----Input-----
The first line of input will consist of three integers of the form:\[ N\; \; K\; \; S \]

where $N$ is the size of the array, The remainder of the file will consist of $N$ integers, $a_ n\in A$, separated by white space. All input will be within the following constraints:\[ 1 \le K \le N \le 5000 \]\[ \forall a_ n \in A,\; 0 \le a_ n \le S \le 5000 \]

-----Output-----
Your program must output a single integer specifying the minimum number of changes that must be made in order to make the array $K_ S$ smooth.

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

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gleb ordered pizza home. When the courier delivered the pizza, he was very upset, because several pieces of sausage lay on the crust, and he does not really like the crust.

The pizza is a circle of radius r and center at the origin. Pizza consists of the main part — circle of radius r - d with center at the origin, and crust around the main part of the width d. Pieces of sausage are also circles. The radius of the i -th piece of the sausage is r_{i}, and the center is given as a pair (x_{i}, y_{i}).

Gleb asks you to help determine the number of pieces of sausage caught on the crust. A piece of sausage got on the crust, if it completely lies on the crust.


-----Input-----

First string contains two integer numbers r and d (0 ≤ d < r ≤ 500) — the radius of pizza and the width of crust.

Next line contains one integer number n — the number of pieces of sausage (1 ≤ n ≤ 10^5).

Each of next n lines contains three integer numbers x_{i}, y_{i} and r_{i} ( - 500 ≤ x_{i}, y_{i} ≤ 500, 0 ≤ r_{i} ≤ 500), where x_{i} and y_{i} are coordinates of the center of i-th peace of sausage, r_{i} — radius of i-th peace of sausage.


-----Output-----

Output the number of pieces of sausage that lay on the crust.


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

Output
2

Input
10 8
4
0 0 9
0 0 10
1 0 1
1 0 2

Output
0



-----Note-----

Below is a picture explaining the first example. Circles of green color denote pieces of sausage lying on the crust.

 [Image]

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