meetforever/GRPO_CL huggingface dataset:
user: There is a robot in a warehouse and $n$ packages he wants to collect. The warehouse can be represented as a coordinate grid. Initially, the robot stays at the point $(0, 0)$. The $i$-th package is at the point $(x_i, y_i)$. It is guaranteed that there are no two packages at the same point. It is also guaranteed that the point $(0, 0)$ doesn't contain a package.

The robot is semi-broken and only can move up ('U') and right ('R'). In other words, in one move the robot can go from the point $(x, y)$ to the point ($x + 1, y$) or to the point $(x, y + 1)$.

As we say above, the robot wants to collect all $n$ packages (in arbitrary order). He wants to do it with the minimum possible number of moves. If there are several possible traversals, the robot wants to choose the lexicographically smallest path.

The string $s$ of length $n$ is lexicographically less than the string $t$ of length $n$ if there is some index $1 \le j \le n$ that for all $i$ from $1$ to $j-1$ $s_i = t_i$ and $s_j < t_j$. It is the standard comparison of string, like in a dictionary. Most programming languages compare strings in this way.


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 100$) — the number of test cases. Then test cases follow.

The first line of a test case contains one integer $n$ ($1 \le n \le 1000$) — the number of packages.

The next $n$ lines contain descriptions of packages. The $i$-th package is given as two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 1000$) — the $x$-coordinate of the package and the $y$-coordinate of the package.

It is guaranteed that there are no two packages at the same point. It is also guaranteed that the point $(0, 0)$ doesn't contain a package.

The sum of all values $n$ over test cases in the test doesn't exceed $1000$.


-----Output-----

Print the answer for each test case.

If it is impossible to collect all $n$ packages in some order starting from ($0,0$), print "NO" on the first line.

Otherwise, print "YES" in the first line. Then print the shortest path — a string consisting of characters 'R' and 'U'. Among all such paths choose the lexicographically smallest path.

Note that in this problem "YES" and "NO" can be only uppercase words, i.e. "Yes", "no" and "YeS" are not acceptable.


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

Output
YES
RUUURRRRUU
NO
YES
RRRRUUU



-----Note-----

For the first test case in the example the optimal path RUUURRRRUU is shown below:  [Image]
user: You are given a positive integer $n$. In one move, you can increase $n$ by one (i.e. make $n := n + 1$). Your task is to find the minimum number of moves you need to perform in order to make the sum of digits of $n$ be less than or equal to $s$.

You have to answer $t$ independent test cases.


-----Input-----

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

The only line of the test case contains two integers $n$ and $s$ ($1 \le n \le 10^{18}$; $1 \le s \le 162$).


-----Output-----

For each test case, print the answer: the minimum number of moves you need to perform in order to make the sum of digits of $n$ be less than or equal to $s$.


-----Example-----
Input
5
2 1
1 1
500 4
217871987498122 10
100000000000000001 1

Output
8
0
500
2128012501878
899999999999999999
user: There is a bookshelf which can fit $n$ books. The $i$-th position of bookshelf is $a_i = 1$ if there is a book on this position and $a_i = 0$ otherwise. It is guaranteed that there is at least one book on the bookshelf.

In one move, you can choose some contiguous segment $[l; r]$ consisting of books (i.e. for each $i$ from $l$ to $r$ the condition $a_i = 1$ holds) and:  Shift it to the right by $1$: move the book at index $i$ to $i + 1$ for all $l \le i \le r$. This move can be done only if $r+1 \le n$ and there is no book at the position $r+1$.  Shift it to the left by $1$: move the book at index $i$ to $i-1$ for all $l \le i \le r$. This move can be done only if $l-1 \ge 1$ and there is no book at the position $l-1$. 

Your task is to find the minimum number of moves required to collect all the books on the shelf as a contiguous (consecutive) segment (i.e. the segment without any gaps).

For example, for $a = [0, 0, 1, 0, 1]$ there is a gap between books ($a_4 = 0$ when $a_3 = 1$ and $a_5 = 1$), for $a = [1, 1, 0]$ there are no gaps between books and for $a = [0, 0,0]$ there are also no gaps between books.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 200$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 50$) — the number of places on a bookshelf. The second line of the test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 1$), where $a_i$ is $1$ if there is a book at this position and $0$ otherwise. It is guaranteed that there is at least one book on the bookshelf.


-----Output-----

For each test case, print one integer: the minimum number of moves required to collect all the books on the shelf as a contiguous (consecutive) segment (i.e. the segment without gaps).


-----Example-----
Input
5
7
0 0 1 0 1 0 1
3
1 0 0
5
1 1 0 0 1
6
1 0 0 0 0 1
5
1 1 0 1 1

Output
2
0
2
4
1



-----Note-----

In the first test case of the example, you can shift the segment $[3; 3]$ to the right and the segment $[4; 5]$ to the right. After all moves, the books form the contiguous segment $[5; 7]$. So the answer is $2$.

In the second test case of the example, you have nothing to do, all the books on the bookshelf form the contiguous segment already.

In the third test case of the example, you can shift the segment $[5; 5]$ to the left and then the segment $[4; 4]$ to the left again. After all moves, the books form the contiguous segment $[1; 3]$. So the answer is $2$.

In the fourth test case of the example, you can shift the segment $[1; 1]$ to the right, the segment $[2; 2]$ to the right, the segment $[6; 6]$ to the left and then the segment $[5; 5]$ to the left. After all moves, the books form the contiguous segment $[3; 4]$. So the answer is $4$.

In the fifth test case of the example, you can shift the segment $[1; 2]$ to the right. After all moves, the books form the contiguous segment $[2; 5]$. So the answer is $1$.
user: You are given two integers $n$ and $k$.

Your task is to construct such a string $s$ of length $n$ that for each $i$ from $1$ to $k$ there is at least one $i$-th letter of the Latin alphabet in this string (the first letter is 'a', the second is 'b' and so on) and there are no other letters except these. You have to maximize the minimal frequency of some letter (the frequency of a letter is the number of occurrences of this letter in a string). If there are several possible answers, you can print any.

You have to answer $t$ independent queries.


-----Input-----

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

The next $t$ lines are contain queries, one per line. The $i$-th line contains two integers $n_i$ and $k_i$ ($1 \le n_i \le 100, 1 \le k_i \le min(n_i, 26)$) — the length of the string in the $i$-th query and the number of characters in the $i$-th query.


-----Output-----

Print $t$ lines. In the $i$-th line print the answer to the $i$-th query: any string $s_i$ satisfying the conditions in the problem statement with constraints from the $i$-th query.


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

Output
cbcacab
abcd
baabab



-----Note-----

In the first example query the maximum possible minimal frequency is $2$, it can be easily seen that the better answer doesn't exist. Other examples of correct answers: "cbcabba", "ccbbaaa" (any permutation of given answers is also correct).

In the second example query any permutation of first four letters is acceptable (the maximum minimal frequency is $1$).

In the third example query any permutation of the given answer is acceptable (the maximum minimal frequency is $3$).
user: You are given two arrays $a$ and $b$ both consisting of $n$ positive (greater than zero) integers. You are also given an integer $k$.

In one move, you can choose two indices $i$ and $j$ ($1 \le i, j \le n$) and swap $a_i$ and $b_j$ (i.e. $a_i$ becomes $b_j$ and vice versa). Note that $i$ and $j$ can be equal or different (in particular, swap $a_2$ with $b_2$ or swap $a_3$ and $b_9$ both are acceptable moves).

Your task is to find the maximum possible sum you can obtain in the array $a$ if you can do no more than (i.e. at most) $k$ such moves (swaps).

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 200$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $k$ ($1 \le n \le 30; 0 \le k \le n$) — the number of elements in $a$ and $b$ and the maximum number of moves you can do. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 30$), where $a_i$ is the $i$-th element of $a$. The third line of the test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 30$), where $b_i$ is the $i$-th element of $b$.


-----Output-----

For each test case, print the answer — the maximum possible sum you can obtain in the array $a$ if you can do no more than (i.e. at most) $k$ swaps.


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

Output
6
27
39
11
17



-----Note-----

In the first test case of the example, you can swap $a_1 = 1$ and $b_2 = 4$, so $a=[4, 2]$ and $b=[3, 1]$.

In the second test case of the example, you don't need to swap anything.

In the third test case of the example, you can swap $a_1 = 1$ and $b_1 = 10$, $a_3 = 3$ and $b_3 = 10$ and $a_2 = 2$ and $b_4 = 10$, so $a=[10, 10, 10, 4, 5]$ and $b=[1, 9, 3, 2, 9]$.

In the fourth test case of the example, you cannot swap anything.

In the fifth test case of the example, you can swap arrays $a$ and $b$, so $a=[4, 4, 5, 4]$ and $b=[1, 2, 2, 1]$.
user: You are planning to buy an apartment in a $n$-floor building. The floors are numbered from $1$ to $n$ from the bottom to the top. At first for each floor you want to know the minimum total time to reach it from the first (the bottom) floor.

Let:  $a_i$ for all $i$ from $1$ to $n-1$ be the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the stairs;  $b_i$ for all $i$ from $1$ to $n-1$ be the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the elevator, also there is a value $c$ — time overhead for elevator usage (you need to wait for it, the elevator doors are too slow!). 

In one move, you can go from the floor you are staying at $x$ to any floor $y$ ($x \ne y$) in two different ways:  If you are using the stairs, just sum up the corresponding values of $a_i$. Formally, it will take $\sum\limits_{i=min(x, y)}^{max(x, y) - 1} a_i$ time units.  If you are using the elevator, just sum up $c$ and the corresponding values of $b_i$. Formally, it will take $c + \sum\limits_{i=min(x, y)}^{max(x, y) - 1} b_i$ time units. 

You can perform as many moves as you want (possibly zero).

So your task is for each $i$ to determine the minimum total time it takes to reach the $i$-th floor from the $1$-st (bottom) floor.


-----Input-----

The first line of the input contains two integers $n$ and $c$ ($2 \le n \le 2 \cdot 10^5, 1 \le c \le 1000$) — the number of floors in the building and the time overhead for the elevator rides.

The second line of the input contains $n - 1$ integers $a_1, a_2, \dots, a_{n-1}$ ($1 \le a_i \le 1000$), where $a_i$ is the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the stairs.

The third line of the input contains $n - 1$ integers $b_1, b_2, \dots, b_{n-1}$ ($1 \le b_i \le 1000$), where $b_i$ is the time required to go from the $i$-th floor to the $(i+1)$-th one (and from the $(i+1)$-th to the $i$-th as well) using the elevator.


-----Output-----

Print $n$ integers $t_1, t_2, \dots, t_n$, where $t_i$ is the minimum total time to reach the $i$-th floor from the first floor if you can perform as many moves as you want.


-----Examples-----
Input
10 2
7 6 18 6 16 18 1 17 17
6 9 3 10 9 1 10 1 5

Output
0 7 13 18 24 35 36 37 40 45 

Input
10 1
3 2 3 1 3 3 1 4 1
1 2 3 4 4 1 2 1 3

Output
0 2 4 7 8 11 13 14 16 17
user: For the given integer $n$ ($n > 2$) let's write down all the strings of length $n$ which contain $n-2$ letters 'a' and two letters 'b' in lexicographical (alphabetical) order.

Recall that the string $s$ of length $n$ is lexicographically less than string $t$ of length $n$, if there exists such $i$ ($1 \le i \le n$), that $s_i < t_i$, and for any $j$ ($1 \le j < i$) $s_j = t_j$. The lexicographic comparison of strings is implemented by the operator < in modern programming languages.

For example, if $n=5$ the strings are (the order does matter):  aaabb  aabab  aabba  abaab  ababa  abbaa  baaab  baaba  babaa  bbaaa 

It is easy to show that such a list of strings will contain exactly $\frac{n \cdot (n-1)}{2}$ strings.

You are given $n$ ($n > 2$) and $k$ ($1 \le k \le \frac{n \cdot (n-1)}{2}$). Print the $k$-th string from the list.


-----Input-----

The input contains one or more test cases.

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

Each test case is written on the the separate line containing two integers $n$ and $k$ ($3 \le n \le 10^5, 1 \le k \le \min(2\cdot10^9, \frac{n \cdot (n-1)}{2})$.

The sum of values $n$ over all test cases in the test doesn't exceed $10^5$.


-----Output-----

For each test case print the $k$-th string from the list of all described above strings of length $n$. Strings in the list are sorted lexicographically (alphabetically).


-----Example-----
Input
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

Output
aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa
user: There are $n$ points on a plane. The $i$-th point has coordinates $(x_i, y_i)$. You have two horizontal platforms, both of length $k$. Each platform can be placed anywhere on a plane but it should be placed horizontally (on the same $y$-coordinate) and have integer borders. If the left border of the platform is $(x, y)$ then the right border is $(x + k, y)$ and all points between borders (including borders) belong to the platform.

Note that platforms can share common points (overlap) and it is not necessary to place both platforms on the same $y$-coordinate.

When you place both platforms on a plane, all points start falling down decreasing their $y$-coordinate. If a point collides with some platform at some moment, the point stops and is saved. Points which never collide with any platform are lost.

Your task is to find the maximum number of points you can save if you place both platforms optimally.

You have to answer $t$ independent test cases.

For better understanding, please read the Note section below to see a picture for the first test case.


-----Input-----

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

The first line of the test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 10^9$) — the number of points and the length of each platform, respectively. The second line of the test case contains $n$ integers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$), where $x_i$ is $x$-coordinate of the $i$-th point. The third line of the input contains $n$ integers $y_1, y_2, \dots, y_n$ ($1 \le y_i \le 10^9$), where $y_i$ is $y$-coordinate of the $i$-th point. All points are distinct (there is no pair $1 \le i < j \le n$ such that $x_i = x_j$ and $y_i = y_j$).

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer: the maximum number of points you can save if you place both platforms optimally.


-----Example-----
Input
4
7 1
1 5 2 3 1 5 4
1 3 6 7 2 5 4
1 1
1000000000
1000000000
5 10
10 7 5 15 8
20 199 192 219 1904
10 10
15 19 8 17 20 10 9 2 10 19
12 13 6 17 1 14 7 9 19 3

Output
6
1
5
10



-----Note-----

The picture corresponding to the first test case of the example:

[Image]

Blue dots represent the points, red segments represent the platforms. One of the possible ways is to place the first platform between points $(1, -1)$ and $(2, -1)$ and the second one between points $(4, 3)$ and $(5, 3)$. Vectors represent how the points will fall down. As you can see, the only point we can't save is the point $(3, 7)$ so it falls down infinitely and will be lost. It can be proven that we can't achieve better answer here. Also note that the point $(5, 3)$ doesn't fall at all because it is already on the platform.
user: We have a secret array. You don't know this array and you have to restore it. However, you know some facts about this array:

  The array consists of $n$ distinct positive (greater than $0$) integers.  The array contains two elements $x$ and $y$ (these elements are known for you) such that $x < y$.  If you sort the array in increasing order (such that $a_1 < a_2 < \ldots < a_n$), differences between all adjacent (consecutive) elements are equal (i.e. $a_2 - a_1 = a_3 - a_2 = \ldots = a_n - a_{n-1})$. 

It can be proven that such an array always exists under the constraints given below.

Among all possible arrays that satisfy the given conditions, we ask you to restore one which has the minimum possible maximum element. In other words, you have to minimize $\max(a_1, a_2, \dots, a_n)$.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains three integers $n$, $x$ and $y$ ($2 \le n \le 50$; $1 \le x < y \le 50$) — the length of the array and two elements that are present in the array, respectively.


-----Output-----

For each test case, print the answer: $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of the required array. If there are several answers, you can print any (it also means that the order of elements doesn't matter).

It can be proven that such an array always exists under the given constraints.


-----Example-----
Input
5
2 1 49
5 20 50
6 20 50
5 3 8
9 13 22

Output
1 49 
20 40 30 50 10
26 32 20 38 44 50 
8 23 18 13 3 
1 10 13 4 19 22 25 16 7
user: You are developing a new feature for the website which sells airline tickets: being able to sort tickets by price! You have already extracted the tickets' prices, so there's just the last step to be done...

You are given an array of integers. Sort it in non-descending order.


-----Input-----

The input consists of a single line of space-separated integers. The first number is n (1 ≤ n ≤ 10) — the size of the array. The following n numbers are the elements of the array (1 ≤ a_{i} ≤ 100).


-----Output-----

Output space-separated elements of the sorted array.


-----Example-----
Input
3 3 1 2

Output
1 2 3 



-----Note-----

Remember, this is a very important feature, and you have to make sure the customers appreciate it!
user: You are given an array $a$ consisting of $n$ integers.

In one move, you can choose two indices $1 \le i, j \le n$ such that $i \ne j$ and set $a_i := a_j$. You can perform such moves any number of times (possibly, zero). You can choose different indices in different operations. The operation := is the operation of assignment (i.e. you choose $i$ and $j$ and replace $a_i$ with $a_j$).

Your task is to say if it is possible to obtain an array with an odd (not divisible by $2$) sum of elements.

You have to answer $t$ independent test cases.


-----Input-----

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

The next $2t$ lines describe test cases. The first line of the test case contains one integer $n$ ($1 \le n \le 2000$) — the number of elements in $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2000$), where $a_i$ is the $i$-th element of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$ ($\sum n \le 2000$).


-----Output-----

For each test case, print the answer on it — "YES" (without quotes) if it is possible to obtain the array with an odd sum of elements, and "NO" otherwise.


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

Output
YES
NO
YES
NO
NO
user: A permutation of length $n$ is an array $p=[p_1,p_2,\dots,p_n]$, which contains every integer from $1$ to $n$ (inclusive) and, moreover, each number appears exactly once. For example, $p=[3,1,4,2,5]$ is a permutation of length $5$.

For a given number $n$ ($n \ge 2$), find a permutation $p$ in which absolute difference (that is, the absolute value of difference) of any two neighboring (adjacent) elements is between $2$ and $4$, inclusive. Formally, find such permutation $p$ that $2 \le |p_i - p_{i+1}| \le 4$ for each $i$ ($1 \le i < n$).

Print any such permutation for the given integer $n$ or determine that it does not exist.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases in the input. Then $t$ test cases follow.

Each test case is described by a single line containing an integer $n$ ($2 \le n \le 1000$).


-----Output-----

Print $t$ lines. Print a permutation that meets the given requirements. If there are several such permutations, then print any of them. If no such permutation exists, print -1.


-----Example-----
Input
6
10
2
4
6
7
13

Output
9 6 10 8 4 7 3 1 5 2 
-1
3 1 4 2 
5 3 6 2 4 1 
5 1 3 6 2 4 7 
13 9 7 11 8 4 1 3 5 2 6 10 12
user: You are given an array $a[0 \ldots n-1]$ of length $n$ which consists of non-negative integers. Note that array indices start from zero.

An array is called good if the parity of each index matches the parity of the element at that index. More formally, an array is good if for all $i$ ($0 \le i \le n - 1$) the equality $i \bmod 2 = a[i] \bmod 2$ holds, where $x \bmod 2$ is the remainder of dividing $x$ by 2.

For example, the arrays [$0, 5, 2, 1$] and [$0, 17, 0, 3$] are good, and the array [$2, 4, 6, 7$] is bad, because for $i=1$, the parities of $i$ and $a[i]$ are different: $i \bmod 2 = 1 \bmod 2 = 1$, but $a[i] \bmod 2 = 4 \bmod 2 = 0$.

In one move, you can take any two elements of the array and swap them (these elements are not necessarily adjacent).

Find the minimum number of moves in which you can make the array $a$ good, or say that this is not possible.


-----Input-----

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

Each test case starts with a line containing an integer $n$ ($1 \le n \le 40$) — the length of the array $a$.

The next line contains $n$ integers $a_0, a_1, \ldots, a_{n-1}$ ($0 \le a_i \le 1000$) — the initial array.


-----Output-----

For each test case, output a single integer — the minimum number of moves to make the given array $a$ good, or -1 if this is not possible.


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

Output
2
1
-1
0



-----Note-----

In the first test case, in the first move, you can swap the elements with indices $0$ and $1$, and in the second move, you can swap the elements with indices $2$ and $3$.

In the second test case, in the first move, you need to swap the elements with indices $0$ and $1$.

In the third test case, you cannot make the array good.