meetforever/GRPO_CL huggingface dataset:
user: Let's suppose you have an array a, a stack s (initially empty) and an array b (also initially empty).

You may perform the following operations until both a and s are empty:

  Take the first element of a, push it into s and remove it from a (if a is not empty);  Take the top element from s, append it to the end of array b and remove it from s (if s is not empty). 

You can perform these operations in arbitrary order.

If there exists a way to perform the operations such that array b is sorted in non-descending order in the end, then array a is called stack-sortable.

For example, [3, 1, 2] is stack-sortable, because b will be sorted if we perform the following operations:

  Remove 3 from a and push it into s;  Remove 1 from a and push it into s;  Remove 1 from s and append it to the end of b;  Remove 2 from a and push it into s;  Remove 2 from s and append it to the end of b;  Remove 3 from s and append it to the end of b. 

After all these operations b = [1, 2, 3], so [3, 1, 2] is stack-sortable. [2, 3, 1] is not stack-sortable.

You are given k first elements of some permutation p of size n (recall that a permutation of size n is an array of size n where each integer from 1 to n occurs exactly once). You have to restore the remaining n - k elements of this permutation so it is stack-sortable. If there are multiple answers, choose the answer such that p is lexicographically maximal (an array q is lexicographically greater than an array p iff there exists some integer k such that for every i < k q_{i} = p_{i}, and q_{k} > p_{k}). You may not swap or change any of first k elements of the permutation.

Print the lexicographically maximal permutation p you can obtain.

If there exists no answer then output -1.


-----Input-----

The first line contains two integers n and k (2 ≤ n ≤ 200000, 1 ≤ k < n) — the size of a desired permutation, and the number of elements you are given, respectively.

The second line contains k integers p_1, p_2, ..., p_{k} (1 ≤ p_{i} ≤ n) — the first k elements of p. These integers are pairwise distinct.


-----Output-----

If it is possible to restore a stack-sortable permutation p of size n such that the first k elements of p are equal to elements given in the input, print lexicographically maximal such permutation.

Otherwise print -1.


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

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

Output
-1

Input
5 1
3

Output
3 2 1 5 4 
Input
5 2
3 4

Output
-1
user: Vasya likes everything infinite. Now he is studying the properties of a sequence s, such that its first element is equal to a (s_1 = a), and the difference between any two neighbouring elements is equal to c (s_{i} - s_{i} - 1 = c). In particular, Vasya wonders if his favourite integer b appears in this sequence, that is, there exists a positive integer i, such that s_{i} = b. Of course, you are the person he asks for a help.


-----Input-----

The first line of the input contain three integers a, b and c ( - 10^9 ≤ a, b, c ≤ 10^9) — the first element of the sequence, Vasya's favorite number and the difference between any two neighbouring elements of the sequence, respectively.


-----Output-----

If b appears in the sequence s print "YES" (without quotes), otherwise print "NO" (without quotes).


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

Output
YES

Input
10 10 0

Output
YES

Input
1 -4 5

Output
NO

Input
0 60 50

Output
NO



-----Note-----

In the first sample, the sequence starts from integers 1, 4, 7, so 7 is its element.

In the second sample, the favorite integer of Vasya is equal to the first element of the sequence.

In the third sample all elements of the sequence are greater than Vasya's favorite integer.

In the fourth sample, the sequence starts from 0, 50, 100, and all the following elements are greater than Vasya's favorite integer.
user: A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular if it it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are regular bracket sequences; "))" and ")((" are bracket sequences (but not regular ones), and "(a)" and "(1)+(1)" are not bracket sequences at all.

You have a number of strings; each string is a bracket sequence of length $2$. So, overall you have $cnt_1$ strings "((", $cnt_2$ strings "()", $cnt_3$ strings ")(" and $cnt_4$ strings "))". You want to write all these strings in some order, one after another; after that, you will get a long bracket sequence of length $2(cnt_1 + cnt_2 + cnt_3 + cnt_4)$. You wonder: is it possible to choose some order of the strings you have such that you will get a regular bracket sequence? Note that you may not remove any characters or strings, and you may not add anything either.


-----Input-----

The input consists of four lines, $i$-th of them contains one integer $cnt_i$ ($0 \le cnt_i \le 10^9$).


-----Output-----

Print one integer: $1$ if it is possible to form a regular bracket sequence by choosing the correct order of the given strings, $0$ otherwise.


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

Output
1

Input
0
0
0
0

Output
1

Input
1
2
3
4

Output
0



-----Note-----

In the first example it is possible to construct a string "(())()(()((()()()())))", which is a regular bracket sequence.

In the second example it is possible to construct a string "", which is a regular bracket sequence.
user: Arpa is researching the Mexican wave.

There are n spectators in the stadium, labeled from 1 to n. They start the Mexican wave at time 0. 

  At time 1, the first spectator stands.  At time 2, the second spectator stands.  ...  At time k, the k-th spectator stands.  At time k + 1, the (k + 1)-th spectator stands and the first spectator sits.  At time k + 2, the (k + 2)-th spectator stands and the second spectator sits.  ...  At time n, the n-th spectator stands and the (n - k)-th spectator sits.  At time n + 1, the (n + 1 - k)-th spectator sits.  ...  At time n + k, the n-th spectator sits. 

Arpa wants to know how many spectators are standing at time t.


-----Input-----

The first line contains three integers n, k, t (1 ≤ n ≤ 10^9, 1 ≤ k ≤ n, 1 ≤ t < n + k).


-----Output-----

Print single integer: how many spectators are standing at time t.


-----Examples-----
Input
10 5 3

Output
3

Input
10 5 7

Output
5

Input
10 5 12

Output
3



-----Note-----

In the following a sitting spectator is represented as -, a standing spectator is represented as ^.

  At t = 0  ---------- $\Rightarrow$ number of standing spectators = 0.  At t = 1  ^--------- $\Rightarrow$ number of standing spectators = 1.  At t = 2  ^^-------- $\Rightarrow$ number of standing spectators = 2.  At t = 3  ^^^------- $\Rightarrow$ number of standing spectators = 3.  At t = 4  ^^^^------ $\Rightarrow$ number of standing spectators = 4.  At t = 5  ^^^^^----- $\Rightarrow$ number of standing spectators = 5.  At t = 6  -^^^^^---- $\Rightarrow$ number of standing spectators = 5.  At t = 7  --^^^^^--- $\Rightarrow$ number of standing spectators = 5.  At t = 8  ---^^^^^-- $\Rightarrow$ number of standing spectators = 5.  At t = 9  ----^^^^^- $\Rightarrow$ number of standing spectators = 5.  At t = 10 -----^^^^^ $\Rightarrow$ number of standing spectators = 5.  At t = 11 ------^^^^ $\Rightarrow$ number of standing spectators = 4.  At t = 12 -------^^^ $\Rightarrow$ number of standing spectators = 3.  At t = 13 --------^^ $\Rightarrow$ number of standing spectators = 2.  At t = 14 ---------^ $\Rightarrow$ number of standing spectators = 1.  At t = 15 ---------- $\Rightarrow$ number of standing spectators = 0.
user: Petya recieved a gift of a string s with length up to 10^5 characters for his birthday. He took two more empty strings t and u and decided to play a game. This game has two possible moves:  Extract the first character of s and append t with this character.  Extract the last character of t and append u with this character. 

Petya wants to get strings s and t empty and string u lexicographically minimal.

You should write a program that will help Petya win the game.


-----Input-----

First line contains non-empty string s (1 ≤ |s| ≤ 10^5), consisting of lowercase English letters.


-----Output-----

Print resulting string u.


-----Examples-----
Input
cab

Output
abc

Input
acdb

Output
abdc
user: Polycarp has recently created a new level in this cool new game Berlio Maker 85 and uploaded it online. Now players from all over the world can try his level.

All levels in this game have two stats to them: the number of plays and the number of clears. So when a player attempts the level, the number of plays increases by $1$. If he manages to finish the level successfully then the number of clears increases by $1$ as well. Note that both of the statistics update at the same time (so if the player finishes the level successfully then the number of plays will increase at the same time as the number of clears).

Polycarp is very excited about his level, so he keeps peeking at the stats to know how hard his level turns out to be.

So he peeked at the stats $n$ times and wrote down $n$ pairs of integers — $(p_1, c_1), (p_2, c_2), \dots, (p_n, c_n)$, where $p_i$ is the number of plays at the $i$-th moment of time and $c_i$ is the number of clears at the same moment of time. The stats are given in chronological order (i.e. the order of given pairs is exactly the same as Polycarp has written down).

Between two consecutive moments of time Polycarp peeked at the stats many players (but possibly zero) could attempt the level.

Finally, Polycarp wonders if he hasn't messed up any records and all the pairs are correct. If there could exist such a sequence of plays (and clears, respectively) that the stats were exactly as Polycarp has written down, then he considers his records correct.

Help him to check the correctness of his records.

For your convenience you have to answer multiple independent test cases.


-----Input-----

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

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the number of moments of time Polycarp peeked at the stats.

Each of the next $n$ lines contains two integers $p_i$ and $c_i$ ($0 \le p_i, c_i \le 1000$) — the number of plays and the number of clears of the level at the $i$-th moment of time.

Note that the stats are given in chronological order.


-----Output-----

For each test case print a single line.

If there could exist such a sequence of plays (and clears, respectively) that the stats were exactly as Polycarp has written down, then print "YES".

Otherwise, print "NO".

You can print each letter in any case (upper or lower).


-----Example-----
Input
6
3
0 0
1 1
1 2
2
1 0
1000 3
4
10 1
15 2
10 2
15 2
1
765 432
2
4 4
4 3
5
0 0
1 0
1 0
1 0
1 0

Output
NO
YES
NO
YES
NO
YES



-----Note-----

In the first test case at the third moment of time the number of clears increased but the number of plays did not, that couldn't have happened.

The second test case is a nice example of a Super Expert level.

In the third test case the number of plays decreased, which is impossible.

The fourth test case is probably an auto level with a single jump over the spike.

In the fifth test case the number of clears decreased, which is also impossible.

Nobody wanted to play the sixth test case; Polycarp's mom attempted it to make him feel better, however, she couldn't clear it.
user: Karen is getting ready for a new school day!

 [Image] 

It is currently hh:mm, given in a 24-hour format. As you know, Karen loves palindromes, and she believes that it is good luck to wake up when the time is a palindrome.

What is the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome?

Remember that a palindrome is a string that reads the same forwards and backwards. For instance, 05:39 is not a palindrome, because 05:39 backwards is 93:50. On the other hand, 05:50 is a palindrome, because 05:50 backwards is 05:50.


-----Input-----

The first and only line of input contains a single string in the format hh:mm (00 ≤  hh  ≤ 23, 00 ≤  mm  ≤ 59).


-----Output-----

Output a single integer on a line by itself, the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome.


-----Examples-----
Input
05:39

Output
11

Input
13:31

Output
0

Input
23:59

Output
1



-----Note-----

In the first test case, the minimum number of minutes Karen should sleep for is 11. She can wake up at 05:50, when the time is a palindrome.

In the second test case, Karen can wake up immediately, as the current time, 13:31, is already a palindrome.

In the third test case, the minimum number of minutes Karen should sleep for is 1 minute. She can wake up at 00:00, when the time is a palindrome.
user: Nicholas has an array a that contains n distinct integers from 1 to n. In other words, Nicholas has a permutation of size n.

Nicholas want the minimum element (integer 1) and the maximum element (integer n) to be as far as possible from each other. He wants to perform exactly one swap in order to maximize the distance between the minimum and the maximum elements. The distance between two elements is considered to be equal to the absolute difference between their positions.


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 100) — the size of the permutation.

The second line of the input contains n distinct integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n), where a_{i} is equal to the element at the i-th position.


-----Output-----

Print a single integer — the maximum possible distance between the minimum and the maximum elements Nicholas can achieve by performing exactly one swap.


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

Output
3

Input
7
1 6 5 3 4 7 2

Output
6

Input
6
6 5 4 3 2 1

Output
5



-----Note-----

In the first sample, one may obtain the optimal answer by swapping elements 1 and 2.

In the second sample, the minimum and the maximum elements will be located in the opposite ends of the array if we swap 7 and 2.

In the third sample, the distance between the minimum and the maximum elements is already maximum possible, so we just perform some unnecessary swap, for example, one can swap 5 and 2.
user: Let's call a string "s-palindrome" if it is symmetric about the middle of the string. For example, the string "oHo" is "s-palindrome", but the string "aa" is not. The string "aa" is not "s-palindrome", because the second half of it is not a mirror reflection of the first half.

 [Image] English alphabet 

You are given a string s. Check if the string is "s-palindrome".


-----Input-----

The only line contains the string s (1 ≤ |s| ≤ 1000) which consists of only English letters.


-----Output-----

Print "TAK" if the string s is "s-palindrome" and "NIE" otherwise.


-----Examples-----
Input
oXoxoXo

Output
TAK

Input
bod

Output
TAK

Input
ER

Output
NIE
user: You are given two positive integer numbers a and b. Permute (change order) of the digits of a to construct maximal number not exceeding b. No number in input and/or output can start with the digit 0.

It is allowed to leave a as it is.


-----Input-----

The first line contains integer a (1 ≤ a ≤ 10^18). The second line contains integer b (1 ≤ b ≤ 10^18). Numbers don't have leading zeroes. It is guaranteed that answer exists.


-----Output-----

Print the maximum possible number that is a permutation of digits of a and is not greater than b. The answer can't have any leading zeroes. It is guaranteed that the answer exists.

The number in the output should have exactly the same length as number a. It should be a permutation of digits of a.


-----Examples-----
Input
123
222

Output
213

Input
3921
10000

Output
9321

Input
4940
5000

Output
4940
user: Alice and Bob play 5-in-a-row game. They have a playing field of size 10 × 10. In turns they put either crosses or noughts, one at a time. Alice puts crosses and Bob puts noughts.

In current match they have made some turns and now it's Alice's turn. She wonders if she can put cross in such empty cell that she wins immediately.

Alice wins if some crosses in the field form line of length not smaller than 5. This line can be horizontal, vertical and diagonal.


-----Input-----

You are given matrix 10 × 10 (10 lines of 10 characters each) with capital Latin letters 'X' being a cross, letters 'O' being a nought and '.' being an empty cell. The number of 'X' cells is equal to the number of 'O' cells and there is at least one of each type. There is at least one empty cell.

It is guaranteed that in the current arrangement nobody has still won.


-----Output-----

Print 'YES' if it's possible for Alice to win in one turn by putting cross in some empty cell. Otherwise print 'NO'.


-----Examples-----
Input
XX.XX.....
.....OOOO.
..........
..........
..........
..........
..........
..........
..........
..........

Output
YES

Input
XXOXX.....
OO.O......
..........
..........
..........
..........
..........
..........
..........
..........

Output
NO
user: You are given matrix with n rows and n columns filled with zeroes. You should put k ones in it in such a way that the resulting matrix is symmetrical with respect to the main diagonal (the diagonal that goes from the top left to the bottom right corner) and is lexicographically maximal.

One matrix is lexicographically greater than the other if the first different number in the first different row from the top in the first matrix is greater than the corresponding number in the second one.

If there exists no such matrix then output -1.


-----Input-----

The first line consists of two numbers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 10^6).


-----Output-----

If the answer exists then output resulting matrix. Otherwise output -1.


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

Output
1 0 
0 0 

Input
3 2

Output
1 0 0 
0 1 0 
0 0 0 

Input
2 5

Output
-1
user: Wet Shark asked Rat Kwesh to generate three positive real numbers x, y and z, from 0.1 to 200.0, inclusive. Wet Krash wants to impress Wet Shark, so all generated numbers will have exactly one digit after the decimal point.

Wet Shark knows Rat Kwesh will want a lot of cheese. So he will give the Rat an opportunity to earn a lot of cheese. He will hand the three numbers x, y and z to Rat Kwesh, and Rat Kwesh will pick one of the these twelve options:  a_1 = x^{y}^{z};  a_2 = x^{z}^{y};  a_3 = (x^{y})^{z};  a_4 = (x^{z})^{y};  a_5 = y^{x}^{z};  a_6 = y^{z}^{x};  a_7 = (y^{x})^{z};  a_8 = (y^{z})^{x};  a_9 = z^{x}^{y};  a_10 = z^{y}^{x};  a_11 = (z^{x})^{y};  a_12 = (z^{y})^{x}. 

Let m be the maximum of all the a_{i}, and c be the smallest index (from 1 to 12) such that a_{c} = m. Rat's goal is to find that c, and he asks you to help him. Rat Kwesh wants to see how much cheese he gets, so he you will have to print the expression corresponding to that a_{c}.

 


-----Input-----

The only line of the input contains three space-separated real numbers x, y and z (0.1 ≤ x, y, z ≤ 200.0). Each of x, y and z is given with exactly one digit after the decimal point.


-----Output-----

Find the maximum value of expression among x^{y}^{z}, x^{z}^{y}, (x^{y})^{z}, (x^{z})^{y}, y^{x}^{z}, y^{z}^{x}, (y^{x})^{z}, (y^{z})^{x}, z^{x}^{y}, z^{y}^{x}, (z^{x})^{y}, (z^{y})^{x} and print the corresponding expression. If there are many maximums, print the one that comes first in the list. 

x^{y}^{z} should be outputted as x^y^z (without brackets), and (x^{y})^{z} should be outputted as (x^y)^z (quotes for clarity). 


-----Examples-----
Input
1.1 3.4 2.5

Output
z^y^x

Input
2.0 2.0 2.0

Output
x^y^z

Input
1.9 1.8 1.7

Output
(x^y)^z
user: You are given a string s consisting of n lowercase Latin letters. You have to type this string using your keyboard.

Initially, you have an empty string. Until you type the whole string, you may perform the following operation:  add a character to the end of the string. 

Besides, at most once you may perform one additional operation: copy the string and append it to itself.

For example, if you have to type string abcabca, you can type it in 7 operations if you type all the characters one by one. However, you can type it in 5 operations if you type the string abc first and then copy it and type the last character.

If you have to type string aaaaaaaaa, the best option is to type 4 characters one by one, then copy the string, and then type the remaining character.

Print the minimum number of operations you need to type the given string.


-----Input-----

The first line of the input containing only one integer number n (1 ≤ n ≤ 100) — the length of the string you have to type. The second line containing the string s consisting of n lowercase Latin letters.


-----Output-----

Print one integer number — the minimum number of operations you need to type the given string.


-----Examples-----
Input
7
abcabca

Output
5

Input
8
abcdefgh

Output
8



-----Note-----

The first test described in the problem statement.

In the second test you can only type all the characters one by one.
user: The All-Berland National Olympiad in Informatics has just ended! Now Vladimir wants to upload the contest from the Olympiad as a gym to a popular Codehorses website.

Unfortunately, the archive with Olympiad's data is a mess. For example, the files with tests are named arbitrary without any logic.

Vladimir wants to rename the files with tests so that their names are distinct integers starting from 1 without any gaps, namely, "1", "2", ..., "n', where n is the total number of tests.

Some of the files contain tests from statements (examples), while others contain regular tests. It is possible that there are no examples, and it is possible that all tests are examples. Vladimir wants to rename the files so that the examples are the first several tests, all all the next files contain regular tests only.

The only operation Vladimir can perform is the "move" command. Vladimir wants to write a script file, each of the lines in which is "move file_1 file_2", that means that the file "file_1" is to be renamed to "file_2". If there is a file "file_2" at the moment of this line being run, then this file is to be rewritten. After the line "move file_1 file_2" the file "file_1" doesn't exist, but there is a file "file_2" with content equal to the content of "file_1" before the "move" command.

Help Vladimir to write the script file with the minimum possible number of lines so that after this script is run:  all examples are the first several tests having filenames "1", "2", ..., "e", where e is the total number of examples;  all other files contain regular tests with filenames "e + 1", "e + 2", ..., "n", where n is the total number of all tests. 


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 10^5) — the number of files with tests.

n lines follow, each describing a file with test. Each line has a form of "name_i type_i", where "name_i" is the filename, and "type_i" equals "1", if the i-th file contains an example test, and "0" if it contains a regular test. Filenames of each file are strings of digits and small English letters with length from 1 to 6 characters. The filenames are guaranteed to be distinct.


-----Output-----

In the first line print the minimum number of lines in Vladimir's script file.

After that print the script file, each line should be "move file_1 file_2", where "file_1" is an existing at the moment of this line being run filename, and "file_2" — is a string of digits and small English letters with length from 1 to 6.


-----Examples-----
Input
5
01 0
2 1
2extra 0
3 1
99 0

Output
4
move 3 1
move 01 5
move 2extra 4
move 99 3

Input
2
1 0
2 1

Output
3
move 1 3
move 2 1
move 3 2
Input
5
1 0
11 1
111 0
1111 1
11111 0

Output
5
move 1 5
move 11 1
move 1111 2
move 111 4
move 11111 3