meetforever/GRPO_CL huggingface dataset:
user: Merge sort is a well-known sorting algorithm. The main function that sorts the elements of array a with indices from [l, r) can be implemented as follows:  If the segment [l, r) is already sorted in non-descending order (that is, for any i such that l ≤ i < r - 1 a[i] ≤ a[i + 1]), then end the function call;  Let $\operatorname{mid} = \lfloor \frac{l + r}{2} \rfloor$;  Call mergesort(a, l, mid);  Call mergesort(a, mid, r);  Merge segments [l, mid) and [mid, r), making the segment [l, r) sorted in non-descending order. The merge algorithm doesn't call any other functions. 

The array in this problem is 0-indexed, so to sort the whole array, you need to call mergesort(a, 0, n).

The number of calls of function mergesort is very important, so Ivan has decided to calculate it while sorting the array. For example, if a = {1, 2, 3, 4}, then there will be 1 call of mergesort — mergesort(0, 4), which will check that the array is sorted and then end. If a = {2, 1, 3}, then the number of calls is 3: first of all, you call mergesort(0, 3), which then sets mid = 1 and calls mergesort(0, 1) and mergesort(1, 3), which do not perform any recursive calls because segments (0, 1) and (1, 3) are sorted.

Ivan has implemented the program that counts the number of mergesort calls, but now he needs to test it. To do this, he needs to find an array a such that a is a permutation of size n (that is, the number of elements in a is n, and every integer number from [1, n] can be found in this array), and the number of mergesort calls when sorting the array is exactly k.

Help Ivan to find an array he wants!


-----Input-----

The first line contains two numbers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 200000) — the size of a desired permutation and the number of mergesort calls required to sort it.


-----Output-----

If a permutation of size n such that there will be exactly k calls of mergesort while sorting it doesn't exist, output  - 1. Otherwise output n integer numbers a[0], a[1], ..., a[n - 1] — the elements of a permutation that would meet the required conditions. If there are multiple answers, print any of them.


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

Output
2 1 3 
Input
4 1

Output
1 2 3 4 
Input
5 6

Output
-1
user: Vasya owns three big integers — $a, l, r$. Let's define a partition of $x$ such a sequence of strings $s_1, s_2, \dots, s_k$ that $s_1 + s_2 + \dots + s_k = x$, where $+$ is a concatanation of strings. $s_i$ is the $i$-th element of the partition. For example, number $12345$ has the following partitions: ["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"] and lots of others.

Let's call some partition of $a$ beautiful if each of its elements contains no leading zeros.

Vasya want to know the number of beautiful partitions of number $a$, which has each of $s_i$ satisfy the condition $l \le s_i \le r$. Note that the comparison is the integer comparison, not the string one.

Help Vasya to count the amount of partitions of number $a$ such that they match all the given requirements. The result can be rather big, so print it modulo $998244353$.


-----Input-----

The first line contains a single integer $a~(1 \le a \le 10^{1000000})$.

The second line contains a single integer $l~(0 \le l \le 10^{1000000})$.

The third line contains a single integer $r~(0 \le r \le 10^{1000000})$.

It is guaranteed that $l \le r$.

It is also guaranteed that numbers $a, l, r$ contain no leading zeros.


-----Output-----

Print a single integer — the amount of partitions of number $a$ such that they match all the given requirements modulo $998244353$.


-----Examples-----
Input
135
1
15

Output
2

Input
10000
0
9

Output
1



-----Note-----

In the first test case, there are two good partitions $13+5$ and $1+3+5$.

In the second test case, there is one good partition $1+0+0+0+0$.
user: On Children's Day, the child got a toy from Delayyy as a present. However, the child is so naughty that he can't wait to destroy the toy.

The toy consists of n parts and m ropes. Each rope links two parts, but every pair of parts is linked by at most one rope. To split the toy, the child must remove all its parts. The child can remove a single part at a time, and each remove consume an energy. Let's define an energy value of part i as v_{i}. The child spend v_{f}_1 + v_{f}_2 + ... + v_{f}_{k} energy for removing part i where f_1, f_2, ..., f_{k} are the parts that are directly connected to the i-th and haven't been removed.

Help the child to find out, what is the minimum total energy he should spend to remove all n parts.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 1000; 0 ≤ m ≤ 2000). The second line contains n integers: v_1, v_2, ..., v_{n} (0 ≤ v_{i} ≤ 10^5). Then followed m lines, each line contains two integers x_{i} and y_{i}, representing a rope from part x_{i} to part y_{i} (1 ≤ x_{i}, y_{i} ≤ n; x_{i} ≠ y_{i}).

Consider all the parts are numbered from 1 to n.


-----Output-----

Output the minimum total energy the child should spend to remove all n parts of the toy.


-----Examples-----
Input
4 3
10 20 30 40
1 4
1 2
2 3

Output
40

Input
4 4
100 100 100 100
1 2
2 3
2 4
3 4

Output
400

Input
7 10
40 10 20 10 20 80 40
1 5
4 7
4 5
5 2
5 7
6 4
1 6
1 3
4 3
1 4

Output
160



-----Note-----

One of the optimal sequence of actions in the first sample is:  First, remove part 3, cost of the action is 20.  Then, remove part 2, cost of the action is 10.  Next, remove part 4, cost of the action is 10.  At last, remove part 1, cost of the action is 0. 

So the total energy the child paid is 20 + 10 + 10 + 0 = 40, which is the minimum.

In the second sample, the child will spend 400 no matter in what order he will remove the parts.
user: For his computer science class, Jacob builds a model tree with sticks and balls containing n nodes in the shape of a tree. Jacob has spent a_{i} minutes building the i-th ball in the tree.

Jacob's teacher will evaluate his model and grade Jacob based on the effort he has put in. However, she does not have enough time to search his whole tree to determine this; Jacob knows that she will examine the first k nodes in a DFS-order traversal of the tree. She will then assign Jacob a grade equal to the minimum a_{i} she finds among those k nodes.

Though Jacob does not have enough time to rebuild his model, he can choose the root node that his teacher starts from. Furthermore, he can rearrange the list of neighbors of each node in any order he likes. Help Jacob find the best grade he can get on this assignment.

A DFS-order traversal is an ordering of the nodes of a rooted tree, built by a recursive DFS-procedure initially called on the root of the tree. When called on a given node v, the procedure does the following:   Print v.  Traverse the list of neighbors of the node v in order and iteratively call DFS-procedure on each one. Do not call DFS-procedure on node u if you came to node v directly from u. 


-----Input-----

The first line of the input contains two positive integers, n and k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ n) — the number of balls in Jacob's tree and the number of balls the teacher will inspect.

The second line contains n integers, a_{i} (1 ≤ a_{i} ≤ 1 000 000), the time Jacob used to build the i-th ball.

Each of the next n - 1 lines contains two integers u_{i}, v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) representing a connection in Jacob's tree between balls u_{i} and v_{i}.


-----Output-----

Print a single integer — the maximum grade Jacob can get by picking the right root of the tree and rearranging the list of neighbors.


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

Output
3

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

Output
1



-----Note-----

In the first sample, Jacob can root the tree at node 2 and order 2's neighbors in the order 4, 1, 5 (all other nodes have at most two neighbors). The resulting preorder traversal is 2, 4, 1, 3, 5, and the minimum a_{i} of the first 3 nodes is 3.

In the second sample, it is clear that any preorder traversal will contain node 1 as either its first or second node, so Jacob cannot do better than a grade of 1.
user: Whereas humans nowadays read fewer and fewer books on paper, book readership among marmots has surged. Heidi has expanded the library and is now serving longer request sequences.


-----Input-----

Same as the easy version, but the limits have changed: 1 ≤ n, k ≤ 400 000.


-----Output-----

Same as the easy version.


-----Examples-----
Input
4 100
1 2 2 1

Output
2

Input
4 1
1 2 2 1

Output
3

Input
4 2
1 2 3 1

Output
3
user: Caisa solved the problem with the sugar and now he is on the way back to home. 

Caisa is playing a mobile game during his path. There are (n + 1) pylons numbered from 0 to n in this game. The pylon with number 0 has zero height, the pylon with number i (i > 0) has height h_{i}. The goal of the game is to reach n-th pylon, and the only move the player can do is to jump from the current pylon (let's denote its number as k) to the next one (its number will be k + 1). When the player have made such a move, its energy increases by h_{k} - h_{k} + 1 (if this value is negative the player loses energy). The player must have non-negative amount of energy at any moment of the time. 

Initially Caisa stand at 0 pylon and has 0 energy. The game provides a special opportunity: one can pay a single dollar and increase the height of anyone pylon by one. Caisa may use that opportunity several times, but he doesn't want to spend too much money. What is the minimal amount of money he must paid to reach the goal of the game?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The next line contains n integers h_1, h_2, ..., h_{n} (1  ≤  h_{i}  ≤  10^5) representing the heights of the pylons.


-----Output-----

Print a single number representing the minimum number of dollars paid by Caisa.


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

Output
4

Input
3
4 4 4

Output
4



-----Note-----

In the first sample he can pay 4 dollars and increase the height of pylon with number 0 by 4 units. Then he can safely pass to the last pylon.
user: Innokenty works at a flea market and sells some random stuff rare items. Recently he found an old rectangular blanket. It turned out that the blanket is split in $n \cdot m$ colored pieces that form a rectangle with $n$ rows and $m$ columns. 

The colored pieces attracted Innokenty's attention so he immediately came up with the following business plan. If he cuts out a subrectangle consisting of three colored stripes, he can sell it as a flag of some country. Innokenty decided that a subrectangle is similar enough to a flag of some country if it consists of three stripes of equal heights placed one above another, where each stripe consists of cells of equal color. Of course, the color of the top stripe must be different from the color of the middle stripe; and the color of the middle stripe must be different from the color of the bottom stripe.

Innokenty has not yet decided what part he will cut out, but he is sure that the flag's boundaries should go along grid lines. Also, Innokenty won't rotate the blanket. Please help Innokenty and count the number of different subrectangles Innokenty can cut out and sell as a flag. Two subrectangles located in different places but forming the same flag are still considered different. [Image] [Image] [Image]

These subrectangles are flags.  [Image] [Image] [Image] [Image] [Image] [Image]

These subrectangles are not flags. 


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1\,000$) — the number of rows and the number of columns on the blanket.

Each of the next $n$ lines contains $m$ lowercase English letters from 'a' to 'z' and describes a row of the blanket. Equal letters correspond to equal colors, different letters correspond to different colors.


-----Output-----

In the only line print the number of subrectangles which form valid flags.


-----Examples-----
Input
4 3
aaa
bbb
ccb
ddd

Output
6

Input
6 1
a
a
b
b
c
c

Output
1



-----Note----- [Image] [Image]

The selected subrectangles are flags in the first example.
user: Luckily, Serval got onto the right bus, and he came to the kindergarten on time. After coming to kindergarten, he found the toy bricks very funny.

He has a special interest to create difficult problems for others to solve. This time, with many $1 \times 1 \times 1$ toy bricks, he builds up a 3-dimensional object. We can describe this object with a $n \times m$ matrix, such that in each cell $(i,j)$, there are $h_{i,j}$ bricks standing on the top of each other.

However, Serval doesn't give you any $h_{i,j}$, and just give you the front view, left view, and the top view of this object, and he is now asking you to restore the object. Note that in the front view, there are $m$ columns, and in the $i$-th of them, the height is the maximum of $h_{1,i},h_{2,i},\dots,h_{n,i}$. It is similar for the left view, where there are $n$ columns. And in the top view, there is an $n \times m$ matrix $t_{i,j}$, where $t_{i,j}$ is $0$ or $1$. If $t_{i,j}$ equals $1$, that means $h_{i,j}>0$, otherwise, $h_{i,j}=0$.

However, Serval is very lonely because others are bored about his unsolvable problems before, and refused to solve this one, although this time he promises there will be at least one object satisfying all the views. As his best friend, can you have a try?


-----Input-----

The first line contains three positive space-separated integers $n, m, h$ ($1\leq n, m, h \leq 100$) — the length, width and height.

The second line contains $m$ non-negative space-separated integers $a_1,a_2,\dots,a_m$, where $a_i$ is the height in the $i$-th column from left to right of the front view ($0\leq a_i \leq h$).

The third line contains $n$ non-negative space-separated integers $b_1,b_2,\dots,b_n$ ($0\leq b_j \leq h$), where $b_j$ is the height in the $j$-th column from left to right of the left view.

Each of the following $n$ lines contains $m$ numbers, each is $0$ or $1$, representing the top view, where $j$-th number of $i$-th row is $1$ if $h_{i, j}>0$, and $0$ otherwise.

It is guaranteed that there is at least one structure satisfying the input.


-----Output-----

Output $n$ lines, each of them contains $m$ integers, the $j$-th number in the $i$-th line should be equal to the height in the corresponding position of the top view. If there are several objects satisfying the views, output any one of them.


-----Examples-----
Input
3 7 3
2 3 0 0 2 0 1
2 1 3
1 0 0 0 1 0 0
0 0 0 0 0 0 1
1 1 0 0 0 0 0

Output
1 0 0 0 2 0 0
0 0 0 0 0 0 1
2 3 0 0 0 0 0

Input
4 5 5
3 5 2 0 4
4 2 5 4
0 0 0 0 1
1 0 1 0 0
0 1 0 0 0
1 1 1 0 0

Output
0 0 0 0 4
1 0 2 0 0
0 5 0 0 0
3 4 1 0 0



-----Note-----

 [Image] 

The graph above illustrates the object in the first example.

 [Image] 

 [Image] 

The first graph illustrates the object in the example output for the second example, and the second graph shows the three-view drawing of it.
user: Polycarp has recently got himself a new job. He now earns so much that his old wallet can't even store all the money he has.

Berland bills somehow come in lots of different sizes. However, all of them are shaped as rectangles (possibly squares). All wallets are also produced in form of rectangles (possibly squares).

A bill $x \times y$ fits into some wallet $h \times w$ if either $x \le h$ and $y \le w$ or $y \le h$ and $x \le w$. Bills can overlap with each other in a wallet and an infinite amount of bills can fit into a wallet. That implies that all the bills Polycarp currently have fit into a wallet if every single one of them fits into it independently of the others.

Now you are asked to perform the queries of two types:

  $+~x~y$ — Polycarp earns a bill of size $x \times y$;  $?~h~w$ — Polycarp wants to check if all the bills he has earned to this moment fit into a wallet of size $h \times w$. 

It is guaranteed that there is at least one query of type $1$ before the first query of type $2$ and that there is at least one query of type $2$ in the input data.

For each query of type $2$ print "YES" if all the bills he has earned to this moment fit into a wallet of given size. Print "NO" otherwise.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 5 \cdot 10^5$) — the number of queries.

Each of the next $n$ lines contains a query of one of these two types:

  $+~x~y$ ($1 \le x, y \le 10^9$) — Polycarp earns a bill of size $x \times y$;  $?~h~w$ ($1 \le h, w \le 10^9$) — Polycarp wants to check if all the bills he has earned to this moment fit into a wallet of size $h \times w$. 

It is guaranteed that there is at least one query of type $1$ before the first query of type $2$ and that there is at least one query of type $2$ in the input data.


-----Output-----

For each query of type $2$ print "YES" if all the bills he has earned to this moment fit into a wallet of given size. Print "NO" otherwise.


-----Example-----
Input
9
+ 3 2
+ 2 3
? 1 20
? 3 3
? 2 3
+ 1 5
? 10 10
? 1 5
+ 1 1

Output
NO
YES
YES
YES
NO



-----Note-----

The queries of type $2$ of the example:

  Neither bill fits;  Both bills fit (just checking that you got that bills can overlap);  Both bills fit (both bills are actually the same);  All bills fit (too much of free space in a wallet is not a problem);  Only bill $1 \times 5$ fit (all the others don't, thus it's "NO").
user: Creatnx has $n$ mirrors, numbered from $1$ to $n$. Every day, Creatnx asks exactly one mirror "Am I beautiful?". The $i$-th mirror will tell Creatnx that he is beautiful with probability $\frac{p_i}{100}$ for all $1 \le i \le n$.

Creatnx asks the mirrors one by one, starting from the $1$-st mirror. Every day, if he asks $i$-th mirror, there are two possibilities:  The $i$-th mirror tells Creatnx that he is beautiful. In this case, if $i = n$ Creatnx will stop and become happy, otherwise he will continue asking the $i+1$-th mirror next day;  In the other case, Creatnx will feel upset. The next day, Creatnx will start asking from the $1$-st mirror again. 

You need to calculate the expected number of days until Creatnx becomes happy.

This number should be found by modulo $998244353$. Formally, let $M = 998244353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.


-----Input-----

The first line contains one integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of mirrors.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq 100$).


-----Output-----

Print the answer modulo $998244353$ in a single line.


-----Examples-----
Input
1
50

Output
2

Input
3
10 20 50

Output
112



-----Note-----

In the first test, there is only one mirror and it tells, that Creatnx is beautiful with probability $\frac{1}{2}$. So, the expected number of days until Creatnx becomes happy is $2$.
user: There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads.

The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it.


-----Input-----

The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input.

Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland. 

The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities.

It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200.

Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one.


-----Output-----

For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it.

In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once. 


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

Output
3
1 3
3 5
5 4
3 2
2 1
3
2 4
3 7
user: Vitya has learned that the answer for The Ultimate Question of Life, the Universe, and Everything is not the integer 54 42, but an increasing integer sequence $a_1, \ldots, a_n$. In order to not reveal the secret earlier than needed, Vitya encrypted the answer and obtained the sequence $b_1, \ldots, b_n$ using the following rules:

  $b_1 = a_1$;

 $b_i = a_i \oplus a_{i - 1}$ for all $i$ from 2 to $n$, where $x \oplus y$ is the bitwise XOR of $x$ and $y$. 

It is easy to see that the original sequence can be obtained using the rule $a_i = b_1 \oplus \ldots \oplus b_i$.

However, some time later Vitya discovered that the integers $b_i$ in the cypher got shuffled, and it can happen that when decrypted using the rule mentioned above, it can produce a sequence that is not increasing. In order to save his reputation in the scientific community, Vasya decided to find some permutation of integers $b_i$ so that the sequence $a_i = b_1 \oplus \ldots \oplus b_i$ is strictly increasing. Help him find such a permutation or determine that it is impossible.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$).

The second line contains $n$ integers $b_1, \ldots, b_n$ ($1 \leq b_i < 2^{60}$).


-----Output-----

If there are no valid permutations, print a single line containing "No".

Otherwise in the first line print the word "Yes", and in the second line print integers $b'_1, \ldots, b'_n$ — a valid permutation of integers $b_i$. The unordered multisets $\{b_1, \ldots, b_n\}$ and $\{b'_1, \ldots, b'_n\}$ should be equal, i. e. for each integer $x$ the number of occurrences of $x$ in the first multiset should be equal to the number of occurrences of $x$ in the second multiset. Apart from this, the sequence $a_i = b'_1 \oplus \ldots \oplus b'_i$ should be strictly increasing.

If there are multiple answers, print any of them.


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

Output
No

Input
6
4 7 7 12 31 61

Output
Yes
4 12 7 31 7 61 



-----Note-----

In the first example no permutation is valid.

In the second example the given answer lead to the sequence $a_1 = 4$, $a_2 = 8$, $a_3 = 15$, $a_4 = 16$, $a_5 = 23$, $a_6 = 42$.