meetforever/GRPO_CL huggingface dataset:
user: You are given two arrays of integers $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$.

Your task is to find a non-empty array $c_1,\ldots,c_k$ that is a subsequence of $a_1,\ldots,a_n$, and also a subsequence of $b_1,\ldots,b_m$. If there are multiple answers, find one of the smallest possible length. If there are still multiple of the smallest possible length, find any. If there are no such arrays, you should report about it.

A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero) elements. For example, $[3,1]$ is a subsequence of $[3,2,1]$ and $[4,3,1]$, but not a subsequence of $[1,3,3,7]$ and $[3,10,4]$.


-----Input-----

The first line contains a single integer $t$ ($1\le t\le 1000$)  — the number of test cases. Next $3t$ lines contain descriptions of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1\le n,m\le 1000$)  — the lengths of the two arrays.

The second line of each test case contains $n$ integers $a_1,\ldots,a_n$ ($1\le a_i\le 1000$)  — the elements of the first array.

The third line of each test case contains $m$ integers $b_1,\ldots,b_m$ ($1\le b_i\le 1000$)  — the elements of the second array.

It is guaranteed that the sum of $n$ and the sum of $m$ across all test cases does not exceed $1000$ ($\sum\limits_{i=1}^t n_i, \sum\limits_{i=1}^t m_i\le 1000$).


-----Output-----

For each test case, output "YES" if a solution exists, or "NO" otherwise.

If the answer is "YES", on the next line output an integer $k$ ($1\le k\le 1000$)  — the length of the array, followed by $k$ integers $c_1,\ldots,c_k$ ($1\le c_i\le 1000$)  — the elements of the array.

If there are multiple solutions with the smallest possible $k$, output any.


-----Example-----
Input
5
4 5
10 8 6 4
1 2 3 4 5
1 1
3
3
1 1
3
2
5 3
1000 2 2 2 3
3 1 5
5 5
1 2 3 4 5
1 2 3 4 5

Output
YES
1 4
YES
1 3
NO
YES
1 3
YES
1 2



-----Note-----

In the first test case, $[4]$ is a subsequence of $[10, 8, 6, 4]$ and $[1, 2, 3, 4, 5]$. This array has length $1$, it is the smallest possible length of a subsequence of both $a$ and $b$.

In the third test case, no non-empty subsequences of both $[3]$ and $[2]$ exist, so the answer is "NO".
user: Mike decided to teach programming to children in an elementary school. He knows that it is not an easy task to interest children in that age to code. That is why he decided to give each child two sweets.

Mike has $n$ sweets with sizes $a_1, a_2, \ldots, a_n$. All his sweets have different sizes. That is, there is no such pair $(i, j)$ ($1 \leq i, j \leq n$) such that $i \ne j$ and $a_i = a_j$.

Since Mike has taught for many years, he knows that if he gives two sweets with sizes $a_i$ and $a_j$ to one child and $a_k$ and $a_p$ to another, where $(a_i + a_j) \neq (a_k + a_p)$, then a child who has a smaller sum of sizes will be upset. That is, if there are two children who have different sums of sweets, then one of them will be upset. Apparently, Mike does not want somebody to be upset. 

Mike wants to invite children giving each of them two sweets. Obviously, he can't give one sweet to two or more children. His goal is to invite as many children as he can. 

Since Mike is busy preparing to his first lecture in the elementary school, he is asking you to find the maximum number of children he can invite giving each of them two sweets in such way that nobody will be upset.


-----Input-----

The first line contains one integer $n$ ($2 \leq n \leq 1\,000$) — the number of sweets Mike has.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^5$) — the sizes of the sweets. It is guaranteed that all integers are distinct.


-----Output-----

Print one integer — the maximum number of children Mike can invite giving each of them two sweets in such way that nobody will be upset.


-----Examples-----
Input
8
1 8 3 11 4 9 2 7

Output
3

Input
7
3 1 7 11 9 2 12

Output
2



-----Note-----

In the first example, Mike can give $9+2=11$ to one child, $8+3=11$ to another one, and $7+4=11$ to the third child. Therefore, Mike can invite three children. Note that it is not the only solution.

In the second example, Mike can give $3+9=12$ to one child and $1+11$ to another one. Therefore, Mike can invite two children. Note that it is not the only solution.
user: You are given two integers $a$ and $m$. Calculate the number of integers $x$ such that $0 \le x < m$ and $\gcd(a, m) = \gcd(a + x, m)$.

Note: $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$.


-----Input-----

The first line contains the single integer $T$ ($1 \le T \le 50$) — the number of test cases.

Next $T$ lines contain test cases — one per line. Each line contains two integers $a$ and $m$ ($1 \le a < m \le 10^{10}$).


-----Output-----

Print $T$ integers — one per test case. For each test case print the number of appropriate $x$-s.


-----Example-----
Input
3
4 9
5 10
42 9999999967

Output
6
1
9999999966



-----Note-----

In the first test case appropriate $x$-s are $[0, 1, 3, 4, 6, 7]$.

In the second test case the only appropriate $x$ is $0$.
user: Recently Petya walked in the forest and found a magic stick.

Since Petya really likes numbers, the first thing he learned was spells for changing numbers. So far, he knows only two spells that can be applied to a positive integer:   If the chosen number $a$ is even, then the spell will turn it into $\frac{3a}{2}$;  If the chosen number $a$ is greater than one, then the spell will turn it into $a-1$. 

Note that if the number is even and greater than one, then Petya can choose which spell to apply.

Petya now has only one number $x$. He wants to know if his favorite number $y$ can be obtained from $x$ using the spells he knows. The spells can be used any number of times in any order. It is not required to use spells, Petya can leave $x$ as it is.


-----Input-----

The first line contains single integer $T$ ($1 \le T \le 10^4$) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains two integers $x$ and $y$ ($1 \le x, y \le 10^9$) — the current number and the number that Petya wants to get.


-----Output-----

For the $i$-th test case print the answer on it — YES if Petya can get the number $y$ from the number $x$ using known spells, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).


-----Example-----
Input
7
2 3
1 1
3 6
6 8
1 2
4 1
31235 6578234

Output
YES
YES
NO
YES
NO
YES
YES
user: Recently, Mike was very busy with studying for exams and contests. Now he is going to chill a bit by doing some sight seeing in the city.

City consists of n intersections numbered from 1 to n. Mike starts walking from his house located at the intersection number 1 and goes along some sequence of intersections. Walking from intersection number i to intersection j requires |i - j| units of energy. The total energy spent by Mike to visit a sequence of intersections p_1 = 1, p_2, ..., p_{k} is equal to $\sum_{i = 1}^{k - 1}|p_{i} - p_{i + 1}$ units of energy.

Of course, walking would be boring if there were no shortcuts. A shortcut is a special path that allows Mike walking from one intersection to another requiring only 1 unit of energy. There are exactly n shortcuts in Mike's city, the i^{th} of them allows walking from intersection i to intersection a_{i} (i ≤ a_{i} ≤ a_{i} + 1) (but not in the opposite direction), thus there is exactly one shortcut starting at each intersection. Formally, if Mike chooses a sequence p_1 = 1, p_2, ..., p_{k} then for each 1 ≤ i < k satisfying p_{i} + 1 = a_{p}_{i} and a_{p}_{i} ≠ p_{i} Mike will spend only 1 unit of energy instead of |p_{i} - p_{i} + 1| walking from the intersection p_{i} to intersection p_{i} + 1. For example, if Mike chooses a sequence p_1 = 1, p_2 = a_{p}_1, p_3 = a_{p}_2, ..., p_{k} = a_{p}_{k} - 1, he spends exactly k - 1 units of total energy walking around them.

Before going on his adventure, Mike asks you to find the minimum amount of energy required to reach each of the intersections from his home. Formally, for each 1 ≤ i ≤ n Mike is interested in finding minimum possible total energy of some sequence p_1 = 1, p_2, ..., p_{k} = i.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 200 000) — the number of Mike's city intersection.

The second line contains n integers a_1, a_2, ..., a_{n} (i ≤ a_{i} ≤ n , $a_{i} \leq a_{i + 1} \forall i < n)$, describing shortcuts of Mike's city, allowing to walk from intersection i to intersection a_{i} using only 1 unit of energy. Please note that the shortcuts don't allow walking in opposite directions (from a_{i} to i).


-----Output-----

In the only line print n integers m_1, m_2, ..., m_{n}, where m_{i} denotes the least amount of total energy required to walk from intersection 1 to intersection i.


-----Examples-----
Input
3
2 2 3

Output
0 1 2 

Input
5
1 2 3 4 5

Output
0 1 2 3 4 

Input
7
4 4 4 4 7 7 7

Output
0 1 2 1 2 3 3 



-----Note-----

In the first sample case desired sequences are:

1: 1; m_1 = 0;

2: 1, 2; m_2 = 1;

3: 1, 3; m_3 = |3 - 1| = 2.

In the second sample case the sequence for any intersection 1 < i is always 1, i and m_{i} = |1 - i|.

In the third sample case — consider the following intersection sequences:

1: 1; m_1 = 0;

2: 1, 2; m_2 = |2 - 1| = 1;

3: 1, 4, 3; m_3 = 1 + |4 - 3| = 2;

4: 1, 4; m_4 = 1;

5: 1, 4, 5; m_5 = 1 + |4 - 5| = 2;

6: 1, 4, 6; m_6 = 1 + |4 - 6| = 3;

7: 1, 4, 5, 7; m_7 = 1 + |4 - 5| + 1 = 3.
user: Carol is currently curling.

She has n disks each with radius r on the 2D plane. 

Initially she has all these disks above the line y = 10^100.

She then will slide the disks towards the line y = 0 one by one in order from 1 to n. 

When she slides the i-th disk, she will place its center at the point (x_{i}, 10^100). She will then push it so the disk’s y coordinate continuously decreases, and x coordinate stays constant. The disk stops once it touches the line y = 0 or it touches any previous disk. Note that once a disk stops moving, it will not move again, even if hit by another disk. 

Compute the y-coordinates of centers of all the disks after all disks have been pushed.


-----Input-----

The first line will contain two integers n and r (1 ≤ n, r ≤ 1 000), the number of disks, and the radius of the disks, respectively.

The next line will contain n integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 1 000) — the x-coordinates of the disks.


-----Output-----

Print a single line with n numbers. The i-th number denotes the y-coordinate of the center of the i-th disk. The output will be accepted if it has absolute or relative error at most 10^{ - 6}.

Namely, let's assume that your answer for a particular value of a coordinate is a and the answer of the jury is b. The checker program will consider your answer correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$ for all coordinates.


-----Example-----
Input
6 2
5 5 6 8 3 12

Output
2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613



-----Note-----

The final positions of the disks will look as follows: [Image] 

In particular, note the position of the last disk.
user: Your program fails again. This time it gets "Wrong answer on test 233".

This is the easier version of the problem. In this version $1 \le n \le 2000$. You can hack this problem only if you solve and lock both problems.

The problem is about a test containing $n$ one-choice-questions. Each of the questions contains $k$ options, and only one of them is correct. The answer to the $i$-th question is $h_{i}$, and if your answer of the question $i$ is $h_{i}$, you earn $1$ point, otherwise, you earn $0$ points for this question. The values $h_1, h_2, \dots, h_n$ are known to you in this problem.

However, you have a mistake in your program. It moves the answer clockwise! Consider all the $n$ answers are written in a circle. Due to the mistake in your program, they are shifted by one cyclically.

Formally, the mistake moves the answer for the question $i$ to the question $i \bmod n + 1$. So it moves the answer for the question $1$ to question $2$, the answer for the question $2$ to the question $3$, ..., the answer for the question $n$ to the question $1$.

We call all the $n$ answers together an answer suit. There are $k^n$ possible answer suits in total.

You're wondering, how many answer suits satisfy the following condition: after moving clockwise by $1$, the total number of points of the new answer suit is strictly larger than the number of points of the old one. You need to find the answer modulo $998\,244\,353$.

For example, if $n = 5$, and your answer suit is $a=[1,2,3,4,5]$, it will submitted as $a'=[5,1,2,3,4]$ because of a mistake. If the correct answer suit is $h=[5,2,2,3,4]$, the answer suit $a$ earns $1$ point and the answer suite $a'$ earns $4$ points. Since $4 > 1$, the answer suit $a=[1,2,3,4,5]$ should be counted.


-----Input-----

The first line contains two integers $n$, $k$ ($1 \le n \le 2000$, $1 \le k \le 10^9$) — the number of questions and the number of possible answers to each question.

The following line contains $n$ integers $h_1, h_2, \dots, h_n$, ($1 \le h_{i} \le k)$ — answers to the questions.


-----Output-----

Output one integer: the number of answers suits satisfying the given condition, modulo $998\,244\,353$.


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

Output
9

Input
5 5
1 1 4 2 2

Output
1000



-----Note-----

For the first example, valid answer suits are $[2,1,1], [2,1,2], [2,1,3], [3,1,1], [3,1,2], [3,1,3], [3,2,1], [3,2,2], [3,2,3]$.
user: Alicia has an array, $a_1, a_2, \ldots, a_n$, of non-negative integers. For each $1 \leq i \leq n$, she has found a non-negative integer $x_i = max(0, a_1, \ldots, a_{i-1})$. Note that for $i=1$, $x_i = 0$.

For example, if Alicia had the array $a = \{0, 1, 2, 0, 3\}$, then $x = \{0, 0, 1, 2, 2\}$.

Then, she calculated an array, $b_1, b_2, \ldots, b_n$: $b_i = a_i - x_i$.

For example, if Alicia had the array $a = \{0, 1, 2, 0, 3\}$, $b = \{0-0, 1-0, 2-1, 0-2, 3-2\} = \{0, 1, 1, -2, 1\}$.

Alicia gives you the values $b_1, b_2, \ldots, b_n$ and asks you to restore the values $a_1, a_2, \ldots, a_n$. Can you help her solve the problem?


-----Input-----

The first line contains one integer $n$ ($3 \leq n \leq 200\,000$) – the number of elements in Alicia's array.

The next line contains $n$ integers, $b_1, b_2, \ldots, b_n$ ($-10^9 \leq b_i \leq 10^9$).

It is guaranteed that for the given array $b$ there is a solution $a_1, a_2, \ldots, a_n$, for all elements of which the following is true: $0 \leq a_i \leq 10^9$.


-----Output-----

Print $n$ integers, $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$), such that if you calculate $x$ according to the statement, $b_1$ will be equal to $a_1 - x_1$, $b_2$ will be equal to $a_2 - x_2$, ..., and $b_n$ will be equal to $a_n - x_n$.

It is guaranteed that there exists at least one solution for the given tests. It can be shown that the solution is unique.


-----Examples-----
Input
5
0 1 1 -2 1

Output
0 1 2 0 3 
Input
3
1000 999999000 -1000000000

Output
1000 1000000000 0 
Input
5
2 1 2 2 3

Output
2 3 5 7 10 


-----Note-----

The first test was described in the problem statement.

In the second test, if Alicia had an array $a = \{1000, 1000000000, 0\}$, then $x = \{0, 1000, 1000000000\}$ and $b = \{1000-0, 1000000000-1000, 0-1000000000\} = \{1000, 999999000, -1000000000\}$.
user: You are given a sequence $s$ consisting of $n$ digits from $1$ to $9$.

You have to divide it into at least two segments (segment — is a consecutive sequence of elements) (in other words, you have to place separators between some digits of the sequence) in such a way that each element belongs to exactly one segment and if the resulting division will be represented as an integer numbers sequence then each next element of this sequence will be strictly greater than the previous one.

More formally: if the resulting division of the sequence is $t_1, t_2, \dots, t_k$, where $k$ is the number of element in a division, then for each $i$ from $1$ to $k-1$ the condition $t_{i} < t_{i + 1}$ (using numerical comparing, it means that the integer representations of strings are compared) should be satisfied.

For example, if $s=654$ then you can divide it into parts $[6, 54]$ and it will be suitable division. But if you will divide it into parts $[65, 4]$ then it will be bad division because $65 > 4$. If $s=123$ then you can divide it into parts $[1, 23]$, $[1, 2, 3]$ but not into parts $[12, 3]$.

Your task is to find any suitable division for each of the $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 300$) — the number of queries.

The first line of the $i$-th query contains one integer number $n_i$ ($2 \le n_i \le 300$) — the number of digits in the $i$-th query.

The second line of the $i$-th query contains one string $s_i$ of length $n_i$ consisting only of digits from $1$ to $9$.


-----Output-----

If the sequence of digits in the $i$-th query cannot be divided into at least two parts in a way described in the problem statement, print the single line "NO" for this query.

Otherwise in the first line of the answer to this query print "YES", on the second line print $k_i$ — the number of parts in your division of the $i$-th query sequence and in the third line print $k_i$ strings $t_{i, 1}, t_{i, 2}, \dots, t_{i, k_i}$ — your division. Parts should be printed in order of the initial string digits. It means that if you write the parts one after another without changing their order then you'll get the string $s_i$.

See examples for better understanding.


-----Example-----
Input
4
6
654321
4
1337
2
33
4
2122

Output
YES
3
6 54 321
YES
3
1 3 37
NO
YES
2
21 22
user: Duff is addicted to meat! Malek wants to keep her happy for n days. In order to be happy in i-th day, she needs to eat exactly a_{i} kilograms of meat. [Image] 

There is a big shop uptown and Malek wants to buy meat for her from there. In i-th day, they sell meat for p_{i} dollars per kilogram. Malek knows all numbers a_1, ..., a_{n} and p_1, ..., p_{n}. In each day, he can buy arbitrary amount of meat, also he can keep some meat he has for the future.

Malek is a little tired from cooking meat, so he asked for your help. Help him to minimize the total money he spends to keep Duff happy for n days. 


-----Input-----

The first line of input contains integer n (1 ≤ n ≤ 10^5), the number of days.

In the next n lines, i-th line contains two integers a_{i} and p_{i} (1 ≤ a_{i}, p_{i} ≤ 100), the amount of meat Duff needs and the cost of meat in that day.


-----Output-----

Print the minimum money needed to keep Duff happy for n days, in one line.


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

Output
10

Input
3
1 3
2 1
3 2

Output
8



-----Note-----

In the first sample case: An optimal way would be to buy 1 kg on the first day, 2 kg on the second day and 3 kg on the third day.

In the second sample case: An optimal way would be to buy 1 kg on the first day and 5 kg (needed meat for the second and third day) on the second day.
user: There are $n$ beautiful skyscrapers in New York, the height of the $i$-th one is $h_i$. Today some villains have set on fire first $n - 1$ of them, and now the only safety building is $n$-th skyscraper.

Let's call a jump from $i$-th skyscraper to $j$-th ($i < j$) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if $i < j$ and one of the following conditions satisfied:   $i + 1 = j$  $\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$  $\max(h_i, h_j) < \min(h_{i + 1}, \ldots, h_{j - 1})$. 

At the moment, Vasya is staying on the first skyscraper and wants to live a little longer, so his goal is to reach $n$-th skyscraper with minimal count of discrete jumps. Help him with calcualting this number.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — total amount of skyscrapers.

The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$) — heights of skyscrapers.


-----Output-----

Print single number $k$ — minimal amount of discrete jumps. We can show that an answer always exists.


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

Output
3
Input
4
4 2 2 4

Output
1
Input
2
1 1

Output
1
Input
5
100 1 100 1 100

Output
2


-----Note-----

In the first testcase, Vasya can jump in the following way: $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$.

In the second and third testcases, we can reach last skyscraper in one jump.

Sequence of jumps in the fourth testcase: $1 \rightarrow 3 \rightarrow 5$.
user: You can perfectly predict the price of a certain stock for the next N days. You would like to profit on this knowledge, but only want to transact one share of stock per day. That is, each day you will either buy one share, sell one share, or do nothing. Initially you own zero shares, and you cannot sell shares when you don't own any. At the end of the N days you would like to again own zero shares, but want to have as much money as possible.


-----Input-----

Input begins with an integer N (2 ≤ N ≤ 3·10^5), the number of days.

Following this is a line with exactly N integers p_1, p_2, ..., p_{N} (1 ≤ p_{i} ≤ 10^6). The price of one share of stock on the i-th day is given by p_{i}.


-----Output-----

Print the maximum amount of money you can end up with at the end of N days.


-----Examples-----
Input
9
10 5 4 7 9 12 6 2 10

Output
20

Input
20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

Output
41



-----Note-----

In the first example, buy a share at 5, buy another at 4, sell one at 9 and another at 12. Then buy at 2 and sell at 10. The total profit is  - 5 - 4 + 9 + 12 - 2 + 10 = 20.
user: Since Sonya has just learned the basics of matrices, she decided to play with them a little bit.

Sonya imagined a new type of matrices that she called rhombic matrices. These matrices have exactly one zero, while all other cells have the Manhattan distance to the cell containing the zero. The cells with equal numbers have the form of a rhombus, that is why Sonya called this type so.

The Manhattan distance between two cells ($x_1$, $y_1$) and ($x_2$, $y_2$) is defined as $|x_1 - x_2| + |y_1 - y_2|$. For example, the Manhattan distance between the cells $(5, 2)$ and $(7, 1)$ equals to $|5-7|+|2-1|=3$. [Image] Example of a rhombic matrix. 

Note that rhombic matrices are uniquely defined by $n$, $m$, and the coordinates of the cell containing the zero.

She drew a $n\times m$ rhombic matrix. She believes that you can not recreate the matrix if she gives you only the elements of this matrix in some arbitrary order (i.e., the sequence of $n\cdot m$ numbers). Note that Sonya will not give you $n$ and $m$, so only the sequence of numbers in this matrix will be at your disposal.

Write a program that finds such an $n\times m$ rhombic matrix whose elements are the same as the elements in the sequence in some order.


-----Input-----

The first line contains a single integer $t$ ($1\leq t\leq 10^6$) — the number of cells in the matrix.

The second line contains $t$ integers $a_1, a_2, \ldots, a_t$ ($0\leq a_i< t$) — the values in the cells in arbitrary order.


-----Output-----

In the first line, print two positive integers $n$ and $m$ ($n \times m = t$) — the size of the matrix.

In the second line, print two integers $x$ and $y$ ($1\leq x\leq n$, $1\leq y\leq m$) — the row number and the column number where the cell with $0$ is located.

If there are multiple possible answers, print any of them. If there is no solution, print the single integer $-1$.


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

Output
4 5
2 2

Input
18
2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1

Output
3 6
2 3

Input
6
2 1 0 2 1 2

Output
-1



-----Note-----

You can see the solution to the first example in the legend. You also can choose the cell $(2, 2)$ for the cell where $0$ is located. You also can choose a $5\times 4$ matrix with zero at $(4, 2)$.

In the second example, there is a $3\times 6$ matrix, where the zero is located at $(2, 3)$ there.

In the third example, a solution does not exist.