meetforever/GRPO_CL huggingface dataset:
user: Monocarp had a tree which consisted of $n$ vertices and was rooted at vertex $1$. He decided to study BFS (Breadth-first search), so he ran BFS on his tree, starting from the root. BFS can be described by the following pseudocode:a = [] # the order in which vertices were processed

q = Queue()

q.put(1) # place the root at the end of the queue

while not q.empty():

    k = q.pop() # retrieve the first vertex from the queue

    a.append(k) # append k to the end of the sequence in which vertices were visited

    for y in g[k]: # g[k] is the list of all children of vertex k, sorted in ascending order

        q.put(y)



Monocarp was fascinated by BFS so much that, in the end, he lost his tree. Fortunately, he still has a sequence of vertices, in which order vertices were visited by the BFS algorithm (the array a from the pseudocode). Monocarp knows that each vertex was visited exactly once (since they were put and taken from the queue exactly once). Also, he knows that all children of each vertex were viewed in ascending order.

Monocarp knows that there are many trees (in the general case) with the same visiting order $a$, so he doesn't hope to restore his tree. Monocarp is okay with any tree that has minimum height.

The height of a tree is the maximum depth of the tree's vertices, and the depth of a vertex is the number of edges in the path from the root to it. For example, the depth of vertex $1$ is $0$, since it's the root, and the depth of all root's children are $1$.

Help Monocarp to find any tree with given visiting order $a$ and minimum height.


-----Input-----

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

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$; $a_i \neq a_j$; $a_1 = 1$) — the order in which the vertices were visited by the BFS algorithm.

It's guaranteed that the total sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case print the minimum possible height of a tree with the given visiting order $a$.


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

Output
3
1
1



-----Note-----

In the first test case, there is only one tree with the given visiting order:  [Image] 

In the second test case, there is only one tree with the given visiting order as well:  [Image] 

In the third test case, an optimal tree with the given visiting order is shown below:  [Image]
user: Permutation $p$ is a sequence of integers $p=[p_1, p_2, \dots, p_n]$, consisting of $n$ distinct (unique) positive integers between $1$ and $n$, inclusive. For example, the following sequences are permutations: $[3, 4, 1, 2]$, $[1]$, $[1, 2]$. The following sequences are not permutations: $[0]$, $[1, 2, 1]$, $[2, 3]$, $[0, 1, 2]$.

The important key is in the locked box that you need to open. To open the box you need to enter secret code. Secret code is a permutation $p$ of length $n$. 

You don't know this permutation, you only know the array $q$ of prefix maximums of this permutation. Formally:  $q_1=p_1$,  $q_2=\max(p_1, p_2)$,  $q_3=\max(p_1, p_2,p_3)$,  ...  $q_n=\max(p_1, p_2,\dots,p_n)$. 

You want to construct any possible suitable permutation (i.e. any such permutation, that calculated $q$ for this permutation is equal to the given array).


-----Input-----

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

The first line of a test case contains one integer $n$ $(1 \le n \le 10^{5})$ — the number of elements in the secret code permutation $p$.

The second line of a test case contains $n$ integers $q_1, q_2, \dots, q_n$ $(1 \le q_i \le n)$ — elements of the array $q$ for secret permutation. It is guaranteed that $q_i \le q_{i+1}$ for all $i$ ($1 \le i < n$).

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


-----Output-----

For each test case, print:  If it's impossible to find such a permutation $p$, print "-1" (without quotes).  Otherwise, print $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). If there are multiple possible answers, you can print any of them. 


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

Output
1 3 4 5 2 
-1
2 1 
1 



-----Note-----

In the first test case of the example answer $[1,3,4,5,2]$ is the only possible answer:  $q_{1} = p_{1} = 1$;  $q_{2} = \max(p_{1}, p_{2}) = 3$;  $q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4$;  $q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5$;  $q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5$. 

It can be proved that there are no answers for the second test case of the example.
user: You are given two strings of equal length $s$ and $t$ consisting of lowercase Latin letters. You may perform any number (possibly, zero) operations on these strings.

During each operation you choose two adjacent characters in any string and assign the value of the first character to the value of the second or vice versa.

For example, if $s$ is "acbc" you can get the following strings in one operation:   "aabc" (if you perform $s_2 = s_1$);  "ccbc" (if you perform $s_1 = s_2$);  "accc" (if you perform $s_3 = s_2$ or $s_3 = s_4$);  "abbc" (if you perform $s_2 = s_3$);  "acbb" (if you perform $s_4 = s_3$); 

Note that you can also apply this operation to the string $t$.

Please determine whether it is possible to transform $s$ into $t$, applying the operation above any number of times.

Note that you have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 100$) — the number of queries. Each query is represented by two consecutive lines.

The first line of each query contains the string $s$ ($1 \le |s| \le 100$) consisting of lowercase Latin letters.

The second line of each query contains the string $t$ ($1 \le |t| \leq 100$, $|t| = |s|$) consisting of lowercase Latin letters.


-----Output-----

For each query, print "YES" if it is possible to make $s$ equal to $t$, 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
3
xabb
aabx
technocup
technocup
a
z

Output
YES
YES
NO



-----Note-----

In the first query, you can perform two operations $s_1 = s_2$ (after it $s$ turns into "aabb") and $t_4 = t_3$ (after it $t$ turns into "aabb"). 

In the second query, the strings are equal initially, so the answer is "YES".

In the third query, you can not make strings $s$ and $t$ equal. Therefore, the answer is "NO".
user: Santa has to send presents to the kids. He has a large stack of $n$ presents, numbered from $1$ to $n$; the topmost present has number $a_1$, the next present is $a_2$, and so on; the bottom present has number $a_n$. All numbers are distinct.

Santa has a list of $m$ distinct presents he has to send: $b_1$, $b_2$, ..., $b_m$. He will send them in the order they appear in the list.

To send a present, Santa has to find it in the stack by removing all presents above it, taking this present and returning all removed presents on top of the stack. So, if there are $k$ presents above the present Santa wants to send, it takes him $2k + 1$ seconds to do it. Fortunately, Santa can speed the whole process up — when he returns the presents to the stack, he may reorder them as he wishes (only those which were above the present he wanted to take; the presents below cannot be affected in any way).

What is the minimum time required to send all of the presents, provided that Santa knows the whole list of presents he has to send and reorders the presents optimally? Santa cannot change the order of presents or interact with the stack of presents in any other way.

Your program has to answer $t$ different test cases.


-----Input-----

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

Then the test cases follow, each represented by three lines.

The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 10^5$) — the number of presents in the stack and the number of presents Santa wants to send, respectively.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le n$, all $a_i$ are unique) — the order of presents in the stack.

The third line contains $m$ integers $b_1$, $b_2$, ..., $b_m$ ($1 \le b_i \le n$, all $b_i$ are unique) — the ordered list of presents Santa has to send.

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


-----Output-----

For each test case print one integer — the minimum number of seconds which Santa has to spend sending presents, if he reorders the presents optimally each time he returns them into the stack.


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

Output
5
8
user: RedDreamer has an array $a$ consisting of $n$ non-negative integers, and an unlucky integer $T$.

Let's denote the misfortune of array $b$ having length $m$ as $f(b)$ — the number of pairs of integers $(i, j)$ such that $1 \le i < j \le m$ and $b_i + b_j = T$. RedDreamer has to paint each element of $a$ into one of two colors, white and black (for each element, the color is chosen independently), and then create two arrays $c$ and $d$ so that all white elements belong to $c$, and all black elements belong to $d$ (it is possible that one of these two arrays becomes empty). RedDreamer wants to paint the elements in such a way that $f(c) + f(d)$ is minimum possible.

For example:

  if $n = 6$, $T = 7$ and $a = [1, 2, 3, 4, 5, 6]$, it is possible to paint the $1$-st, the $4$-th and the $5$-th elements white, and all other elements black. So $c = [1, 4, 5]$, $d = [2, 3, 6]$, and $f(c) + f(d) = 0 + 0 = 0$;  if $n = 3$, $T = 6$ and $a = [3, 3, 3]$, it is possible to paint the $1$-st element white, and all other elements black. So $c = [3]$, $d = [3, 3]$, and $f(c) + f(d) = 0 + 1 = 1$. 

Help RedDreamer to paint the array optimally!


-----Input-----

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

The first line of each test case contains two integers $n$ and $T$ ($1 \le n \le 10^5$, $0 \le T \le 10^9$) — the number of elements in the array and the unlucky integer, respectively. 

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

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


-----Output-----

For each test case print $n$ integers: $p_1$, $p_2$, ..., $p_n$ (each $p_i$ is either $0$ or $1$) denoting the colors. If $p_i$ is $0$, then $a_i$ is white and belongs to the array $c$, otherwise it is black and belongs to the array $d$.

If there are multiple answers that minimize the value of $f(c) + f(d)$, print any of them.


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

Output
1 0 0 1 1 0 
1 0 0
user: You are given a integer $n$ ($n > 0$). Find any integer $s$ which satisfies these conditions, or report that there are no such numbers:

In the decimal representation of $s$:   $s > 0$,  $s$ consists of $n$ digits,  no digit in $s$ equals $0$,  $s$ is not divisible by any of it's digits. 


-----Input-----

The input consists of multiple test cases. The first line of the input contains a single integer $t$ ($1 \leq t \leq 400$), the number of test cases. The next $t$ lines each describe a test case.

Each test case contains one positive integer $n$ ($1 \leq n \leq 10^5$).

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


-----Output-----

For each test case, print an integer $s$ which satisfies the conditions described above, or "-1" (without quotes), if no such number exists. If there are multiple possible solutions for $s$, print any solution.


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

Output
-1
57
239
6789



-----Note-----

In the first test case, there are no possible solutions for $s$ consisting of one digit, because any such solution is divisible by itself.

For the second test case, the possible solutions are: $23$, $27$, $29$, $34$, $37$, $38$, $43$, $46$, $47$, $49$, $53$, $54$, $56$, $57$, $58$, $59$, $67$, $68$, $69$, $73$, $74$, $76$, $78$, $79$, $83$, $86$, $87$, $89$, $94$, $97$, and $98$.

For the third test case, one possible solution is $239$ because $239$ is not divisible by $2$, $3$ or $9$ and has three digits (none of which equals zero).
user: Your friend Jeff Zebos has been trying to run his new online company, but it's not going very well. He's not getting a lot of sales on his website which he decided to call Azamon. His big problem, you think, is that he's not ranking high enough on the search engines. If only he could rename his products to have better names than his competitors, then he'll be at the top of the search results and will be a millionaire.

After doing some research, you find out that search engines only sort their results lexicographically. If your friend could rename his products to lexicographically smaller strings than his competitor's, then he'll be at the top of the rankings!

To make your strategy less obvious to his competitors, you decide to swap no more than two letters of the product names.

Please help Jeff to find improved names for his products that are lexicographically smaller than his competitor's!

Given the string $s$ representing Jeff's product name and the string $c$ representing his competitor's product name, find a way to swap at most one pair of characters in $s$ (that is, find two distinct indices $i$ and $j$ and swap $s_i$ and $s_j$) such that the resulting new name becomes strictly lexicographically smaller than $c$, or determine that it is impossible.

Note: String $a$ is strictly lexicographically smaller than string $b$ if and only if one of the following holds:  $a$ is a proper prefix of $b$, that is, $a$ is a prefix of $b$ such that $a \neq b$;  There exists an integer $1 \le i \le \min{(|a|, |b|)}$ such that $a_i < b_i$ and $a_j = b_j$ for $1 \le j < i$. 


-----Input-----

The first line of input contains a single integer $t$ ($1 \le t \le 1500$) denoting the number of test cases. The next lines contain descriptions of the test cases.

Each test case consists of a single line containing two space-separated strings $s$ and $c$ ($2 \le |s| \le 5000, 1 \le |c| \le 5000$). The strings $s$ and $c$ consists of uppercase English letters.

It is guaranteed that the sum of $|s|$ in the input is at most $5000$ and the sum of the $|c|$ in the input is at most $5000$.


-----Output-----

For each test case, output a single line containing a single string, which is either  the new name which is obtained after swapping no more than one pair of characters that is strictly lexicographically smaller than $c$. In case there are many possible such strings, you can output any of them;  three dashes (the string "---" without quotes) if it is impossible. 


-----Example-----
Input
3
AZAMON APPLE
AZAMON AAAAAAAAAAALIBABA
APPLE BANANA

Output
AMAZON
---
APPLE



-----Note-----

In the first test case, it is possible to swap the second and the fourth letters of the string and the resulting string "AMAZON" is lexicographically smaller than "APPLE".

It is impossible to improve the product's name in the second test case and satisfy all conditions.

In the third test case, it is possible not to swap a pair of characters. The name "APPLE" is lexicographically smaller than "BANANA". Note that there are other valid answers, e.g., "APPEL".
user: You may have already known that a standard ICPC team consists of exactly three members. The perfect team however has more restrictions. A student can have some specialization: coder or mathematician. She/he can have no specialization, but can't have both at the same time.

So the team is considered perfect if it includes at least one coder, at least one mathematician and it consists of exactly three members.

You are a coach at a very large university and you know that $c$ of your students are coders, $m$ are mathematicians and $x$ have no specialization.

What is the maximum number of full perfect teams you can distribute them into? 

Note that some students can be left without a team and each student can be a part of no more than one team.

You are also asked to answer $q$ independent queries.


-----Input-----

The first line contains a single integer $q$ ($1 \le q \le 10^4$) — the number of queries. 

Each of the next $q$ lines contains three integers $c$, $m$ and $x$ ($0 \le c, m, x \le 10^8$) — the number of coders, mathematicians and students without any specialization in the university, respectively.

Note that the no student is both coder and mathematician at the same time. 


-----Output-----

Print $q$ integers — the $i$-th of them should be the answer to the $i$ query in the order they are given in the input. The answer is the maximum number of full perfect teams you can distribute your students into. 


-----Example-----
Input
6
1 1 1
3 6 0
0 0 0
0 1 1
10 1 10
4 4 1

Output
1
3
0
0
1
3



-----Note-----

In the first example here are how teams are formed:  the only team of 1 coder, 1 mathematician and 1 without specialization;  all three teams consist of 1 coder and 2 mathematicians;  no teams can be formed;  no teams can be formed;  one team consists of 1 coder, 1 mathematician and 1 without specialization, the rest aren't able to form any team;  one team consists of 1 coder, 1 mathematician and 1 without specialization, one consists of 2 coders and 1 mathematician and one consists of 1 coder and 2 mathematicians.
user: Lee was cleaning his house for the party when he found a messy string under the carpets. Now he'd like to make it clean accurately and in a stylish way...

The string $s$ he found is a binary string of length $n$ (i. e. string consists only of 0-s and 1-s).

In one move he can choose two consecutive characters $s_i$ and $s_{i+1}$, and if $s_i$ is 1 and $s_{i + 1}$ is 0, he can erase exactly one of them (he can choose which one to erase but he can't erase both characters simultaneously). The string shrinks after erasing.

Lee can make an arbitrary number of moves (possibly zero) and he'd like to make the string $s$ as clean as possible. He thinks for two different strings $x$ and $y$, the shorter string is cleaner, and if they are the same length, then the lexicographically smaller string is cleaner.

Now you should answer $t$ test cases: for the $i$-th test case, print the cleanest possible string that Lee can get by doing some number of moves.

Small reminder: if we have two strings $x$ and $y$ of the same length then $x$ is lexicographically smaller than $y$ if there is a position $i$ such that $x_1 = y_1$, $x_2 = y_2$,..., $x_{i - 1} = y_{i - 1}$ and $x_i < y_i$.


-----Input-----

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

Next $2t$ lines contain test cases — one per two lines.

The first line of each test case contains the integer $n$ ($1 \le n \le 10^5$) — the length of the string $s$.

The second line contains the binary string $s$. The string $s$ is a string of length $n$ which consists only of zeroes and ones.

It's guaranteed that sum of $n$ over test cases doesn't exceed $10^5$.


-----Output-----

Print $t$ answers — one per test case.

The answer to the $i$-th test case is the cleanest string Lee can get after doing some number of moves (possibly zero).


-----Example-----
Input
5
10
0001111111
4
0101
8
11001101
10
1110000000
1
1

Output
0001111111
001
01
0
1



-----Note-----

In the first test case, Lee can't perform any moves.

In the second test case, Lee should erase $s_2$.

In the third test case, Lee can make moves, for example, in the following order: 11001101 $\rightarrow$ 1100101 $\rightarrow$ 110101 $\rightarrow$ 10101 $\rightarrow$ 1101 $\rightarrow$ 101 $\rightarrow$ 01.
user: You have three piles of candies: red, green and blue candies:  the first pile contains only red candies and there are $r$ candies in it,  the second pile contains only green candies and there are $g$ candies in it,  the third pile contains only blue candies and there are $b$ candies in it. 

Each day Tanya eats exactly two candies of different colors. She is free to choose the colors of eaten candies: the only restriction that she can't eat two candies of the same color in a day.

Find the maximal number of days Tanya can eat candies? Each day she needs to eat exactly two candies.


-----Input-----

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

Each test case is given as a separate line of the input. It contains three integers $r$, $g$ and $b$ ($1 \le r, g, b \le 10^8$) — the number of red, green and blue candies, respectively.


-----Output-----

Print $t$ integers: the $i$-th printed integer is the answer on the $i$-th test case in the input.


-----Example-----
Input
6
1 1 1
1 2 1
4 1 1
7 4 10
8 1 4
8 2 8

Output
1
2
2
10
5
9



-----Note-----

In the first example, Tanya can eat candies for one day only. She can eat any pair of candies this day because all of them have different colors.

In the second example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and green and blue candies on the second day.

In the third example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and red and blue candies on the second day. Note, that two red candies will remain uneaten.
user: Polycarp lives on the coordinate axis $Ox$ and travels from the point $x=a$ to $x=b$. It moves uniformly rectilinearly at a speed of one unit of distance per minute.

On the axis $Ox$ at the point $x=c$ the base station of the mobile operator is placed. It is known that the radius of its coverage is $r$. Thus, if Polycarp is at a distance less than or equal to $r$ from the point $x=c$, then he is in the network coverage area, otherwise — no. The base station can be located both on the route of Polycarp and outside it.

Print the time in minutes during which Polycarp will not be in the coverage area of the network, with a rectilinear uniform movement from $x=a$ to $x=b$. His speed — one unit of distance per minute.


-----Input-----

The first line contains a positive integer $t$ ($1 \le t \le 1000$) — the number of test cases. In the following lines are written $t$ test cases.

The description of each test case is one line, which contains four integers $a$, $b$, $c$ and $r$ ($-10^8 \le a,b,c \le 10^8$, $0 \le r \le 10^8$) — the coordinates of the starting and ending points of the path, the base station, and its coverage radius, respectively.

Any of the numbers $a$, $b$ and $c$ can be equal (either any pair or all three numbers). The base station can be located both on the route of Polycarp and outside it.


-----Output-----

Print $t$ numbers — answers to given test cases in the order they are written in the test. Each answer is an integer — the number of minutes during which Polycarp will be unavailable during his movement.


-----Example-----
Input
9
1 10 7 1
3 3 3 0
8 2 10 4
8 2 10 100
-10 20 -17 2
-3 2 2 0
-3 1 2 0
2 3 2 3
-1 3 -2 2

Output
7
0
4
0
30
5
4
0
3



-----Note-----

The following picture illustrates the first test case.  [Image] Polycarp goes from $1$ to $10$. The yellow area shows the coverage area of the station with a radius of coverage of $1$, which is located at the point of $7$. The green area shows a part of the path when Polycarp is out of coverage area.