meetforever/GRPO_CL huggingface dataset:
user: There are n parliamentarians in Berland. They are numbered with integers from 1 to n. It happened that all parliamentarians with odd indices are Democrats and all parliamentarians with even indices are Republicans.

New parliament assembly hall is a rectangle consisting of a × b chairs — a rows of b chairs each. Two chairs are considered neighbouring if they share as side. For example, chair number 5 in row number 2 is neighbouring to chairs number 4 and 6 in this row and chairs with number 5 in rows 1 and 3. Thus, chairs have four neighbours in general, except for the chairs on the border of the hall

We know that if two parliamentarians from one political party (that is two Democrats or two Republicans) seat nearby they spent all time discussing internal party issues.

Write the program that given the number of parliamentarians and the sizes of the hall determine if there is a way to find a seat for any parliamentarian, such that no two members of the same party share neighbouring seats.


-----Input-----

The first line of the input contains three integers n, a and b (1 ≤ n ≤ 10 000, 1 ≤ a, b ≤ 100) — the number of parliamentarians, the number of rows in the assembly hall and the number of seats in each row, respectively.


-----Output-----

If there is no way to assigns seats to parliamentarians in a proper way print -1.

Otherwise print the solution in a lines, each containing b integers. The j-th integer of the i-th line should be equal to the index of parliamentarian occupying this seat, or 0 if this seat should remain empty. If there are multiple possible solution, you may print any of them.


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

Output
0 3
1 2

Input
8 4 3

Output
7 8 3
0 1 4
6 0 5
0 2 0

Input
10 2 2

Output
-1



-----Note-----

In the first sample there are many other possible solutions. For example, 3 2

0 1



and 2 1

3 0



The following assignment 3 2

1 0



is incorrect, because parliamentarians 1 and 3 are both from Democrats party but will occupy neighbouring seats.
user: Sakuzyo - Imprinting

A.R.C. Markland-N is a tall building with $n$ floors numbered from $1$ to $n$. Between each two adjacent floors in the building, there is a staircase connecting them.

It's lunchtime for our sensei Colin "ConneR" Neumann Jr, and he's planning for a location to enjoy his meal.

ConneR's office is at floor $s$ of the building. On each floor (including floor $s$, of course), there is a restaurant offering meals. However, due to renovations being in progress, $k$ of the restaurants are currently closed, and as a result, ConneR can't enjoy his lunch there.

CooneR wants to reach a restaurant as quickly as possible to save time. What is the minimum number of staircases he needs to walk to reach a closest currently open restaurant.

Please answer him quickly, and you might earn his praise and even enjoy the lunch with him in the elegant Neumanns' way!


-----Input-----

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

The first line of a test case contains three integers $n$, $s$ and $k$ ($2 \le n \le 10^9$, $1 \le s \le n$, $1 \le k \le \min(n-1, 1000)$) — respectively the number of floors of A.R.C. Markland-N, the floor where ConneR is in, and the number of closed restaurants.

The second line of a test case contains $k$ distinct integers $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$) — the floor numbers of the currently closed restaurants.

It is guaranteed that the sum of $k$ over all test cases does not exceed $1000$.


-----Output-----

For each test case print a single integer — the minimum number of staircases required for ConneR to walk from the floor $s$ to a floor with an open restaurant.


-----Example-----
Input
5
5 2 3
1 2 3
4 3 3
4 1 2
10 2 6
1 2 3 4 5 7
2 1 1
2
100 76 8
76 75 36 67 41 74 10 77

Output
2
0
4
0
2



-----Note-----

In the first example test case, the nearest floor with an open restaurant would be the floor $4$.

In the second example test case, the floor with ConneR's office still has an open restaurant, so Sensei won't have to go anywhere.

In the third example test case, the closest open restaurant is on the $6$-th floor.
user: Polycarp is preparing the first programming contest for robots. There are $n$ problems in it, and a lot of robots are going to participate in it. Each robot solving the problem $i$ gets $p_i$ points, and the score of each robot in the competition is calculated as the sum of $p_i$ over all problems $i$ solved by it. For each problem, $p_i$ is an integer not less than $1$.

Two corporations specializing in problem-solving robot manufacturing, "Robo-Coder Inc." and "BionicSolver Industries", are going to register two robots (one for each corporation) for participation as well. Polycarp knows the advantages and flaws of robots produced by these companies, so, for each problem, he knows precisely whether each robot will solve it during the competition. Knowing this, he can try predicting the results — or manipulating them. 

For some reason (which absolutely cannot involve bribing), Polycarp wants the "Robo-Coder Inc." robot to outperform the "BionicSolver Industries" robot in the competition. Polycarp wants to set the values of $p_i$ in such a way that the "Robo-Coder Inc." robot gets strictly more points than the "BionicSolver Industries" robot. However, if the values of $p_i$ will be large, it may look very suspicious — so Polycarp wants to minimize the maximum value of $p_i$ over all problems. Can you help Polycarp to determine the minimum possible upper bound on the number of points given for solving the problems?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 100$) — the number of problems.

The second line contains $n$ integers $r_1$, $r_2$, ..., $r_n$ ($0 \le r_i \le 1$). $r_i = 1$ means that the "Robo-Coder Inc." robot will solve the $i$-th problem, $r_i = 0$ means that it won't solve the $i$-th problem.

The third line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ ($0 \le b_i \le 1$). $b_i = 1$ means that the "BionicSolver Industries" robot will solve the $i$-th problem, $b_i = 0$ means that it won't solve the $i$-th problem.


-----Output-----

If "Robo-Coder Inc." robot cannot outperform the "BionicSolver Industries" robot by any means, print one integer $-1$.

Otherwise, print the minimum possible value of $\max \limits_{i = 1}^{n} p_i$, if all values of $p_i$ are set in such a way that the "Robo-Coder Inc." robot gets strictly more points than the "BionicSolver Industries" robot.


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

Output
3

Input
3
0 0 0
0 0 0

Output
-1

Input
4
1 1 1 1
1 1 1 1

Output
-1

Input
9
1 0 0 0 0 0 0 0 1
0 1 1 0 1 1 1 1 0

Output
4



-----Note-----

In the first example, one of the valid score assignments is $p = [3, 1, 3, 1, 1]$. Then the "Robo-Coder" gets $7$ points, the "BionicSolver" — $6$ points.

In the second example, both robots get $0$ points, and the score distribution does not matter.

In the third example, both robots solve all problems, so their points are equal.
user: Piegirl is buying stickers for a project. Stickers come on sheets, and each sheet of stickers contains exactly n stickers. Each sticker has exactly one character printed on it, so a sheet of stickers can be described by a string of length n. Piegirl wants to create a string s using stickers. She may buy as many sheets of stickers as she wants, and may specify any string of length n for the sheets, but all the sheets must be identical, so the string is the same for all sheets. Once she attains the sheets of stickers, she will take some of the stickers from the sheets and arrange (in any order) them to form s. Determine the minimum number of sheets she has to buy, and provide a string describing a possible sheet of stickers she should buy.


-----Input-----

The first line contains string s (1 ≤ |s| ≤ 1000), consisting of lowercase English characters only. The second line contains an integer n (1 ≤ n ≤ 1000).


-----Output-----

On the first line, print the minimum number of sheets Piegirl has to buy. On the second line, print a string consisting of n lower case English characters. This string should describe a sheet of stickers that Piegirl can buy in order to minimize the number of sheets. If Piegirl cannot possibly form the string s, print instead a single line with the number -1.


-----Examples-----
Input
banana
4

Output
2
baan

Input
banana
3

Output
3
nab

Input
banana
2

Output
-1



-----Note-----

In the second example, Piegirl can order 3 sheets of stickers with the characters "nab". She can take characters "nab" from the first sheet, "na" from the second, and "a" from the third, and arrange them to from "banana".
user: Karl likes Codeforces and subsequences. He wants to find a string of lowercase English letters that contains at least $k$ subsequences codeforces. Out of all possible strings, Karl wants to find a shortest one.

Formally, a codeforces subsequence of a string $s$ is a subset of ten characters of $s$ that read codeforces from left to right. For example, codeforces contains codeforces a single time, while codeforcesisawesome contains codeforces four times: codeforcesisawesome, codeforcesisawesome, codeforcesisawesome, codeforcesisawesome.

Help Karl find any shortest string that contains at least $k$ codeforces subsequences.


-----Input-----

The only line contains a single integer $k$ ($1 \leq k \leq 10^{16})$.


-----Output-----

Print a shortest string of lowercase English letters that contains at least $k$ codeforces subsequences. If there are several such strings, print any of them.


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

Output
codeforces

Input
3

Output
codeforcesss
user: Sagheer is playing a game with his best friend Soliman. He brought a tree with n nodes numbered from 1 to n and rooted at node 1. The i-th node has a_{i} apples. This tree has a special property: the lengths of all paths from the root to any leaf have the same parity (i.e. all paths have even length or all paths have odd length).

Sagheer and Soliman will take turns to play. Soliman will make the first move. The player who can't make a move loses.

In each move, the current player will pick a single node, take a non-empty subset of apples from it and do one of the following two things:  eat the apples, if the node is a leaf.  move the apples to one of the children, if the node is non-leaf. 

Before Soliman comes to start playing, Sagheer will make exactly one change to the tree. He will pick two different nodes u and v and swap the apples of u with the apples of v.

Can you help Sagheer count the number of ways to make the swap (i.e. to choose u and v) after which he will win the game if both players play optimally? (u, v) and (v, u) are considered to be the same pair.


-----Input-----

The first line will contain one integer n (2 ≤ n ≤ 10^5) — the number of nodes in the apple tree.

The second line will contain n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^7) — the number of apples on each node of the tree.

The third line will contain n - 1 integers p_2, p_3, ..., p_{n} (1 ≤ p_{i} ≤ n) — the parent of each node of the tree. Node i has parent p_{i} (for 2 ≤ i ≤ n). Node 1 is the root of the tree.

It is guaranteed that the input describes a valid tree, and the lengths of all paths from the root to any leaf will have the same parity.


-----Output-----

On a single line, print the number of different pairs of nodes (u, v), u ≠ v such that if they start playing after swapping the apples of both nodes, Sagheer will win the game. (u, v) and (v, u) are considered to be the same pair.


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

Output
1

Input
3
1 2 3
1 1

Output
0

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

Output
4



-----Note-----

In the first sample, Sagheer can only win if he swapped node 1 with node 3. In this case, both leaves will have 2 apples. If Soliman makes a move in a leaf node, Sagheer can make the same move in the other leaf. If Soliman moved some apples from a root to a leaf, Sagheer will eat those moved apples. Eventually, Soliman will not find a move.

In the second sample, There is no swap that will make Sagheer win the game.

Note that Sagheer must make the swap even if he can win with the initial tree.
user: You are planning to build housing on a street. There are $n$ spots available on the street on which you can build a house. The spots are labeled from $1$ to $n$ from left to right. In each spot, you can build a house with an integer height between $0$ and $h$.

In each spot, if a house has height $a$, you will gain $a^2$ dollars from it.

The city has $m$ zoning restrictions. The $i$-th restriction says that the tallest house from spots $l_i$ to $r_i$ (inclusive) must be at most $x_i$.

You would like to build houses to maximize your profit. Determine the maximum profit possible.


-----Input-----

The first line contains three integers $n$, $h$, and $m$ ($1 \leq n,h,m \leq 50$) — the number of spots, the maximum height, and the number of restrictions.

Each of the next $m$ lines contains three integers $l_i$, $r_i$, and $x_i$ ($1 \leq l_i \leq r_i \leq n$, $0 \leq x_i \leq h$) — left and right limits (inclusive) of the $i$-th restriction and the maximum possible height in that range.


-----Output-----

Print a single integer, the maximum profit you can make.


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

Output
14

Input
4 10 2
2 3 8
3 4 7

Output
262



-----Note-----

In the first example, there are $3$ houses, the maximum height of a house is $3$, and there are $3$ restrictions. The first restriction says the tallest house between $1$ and $1$ must be at most $1$. The second restriction says the tallest house between $2$ and $2$ must be at most $3$. The third restriction says the tallest house between $3$ and $3$ must be at most $2$.

In this case, it is optimal to build houses with heights $[1, 3, 2]$. This fits within all the restrictions. The total profit in this case is $1^2 + 3^2 + 2^2 = 14$.

In the second example, there are $4$ houses, the maximum height of a house is $10$, and there are $2$ restrictions. The first restriction says the tallest house from $2$ to $3$ must be at most $8$. The second restriction says the tallest house from $3$ to $4$ must be at most $7$.

In this case, it's optimal to build houses with heights $[10, 8, 7, 7]$. We get a profit of $10^2+8^2+7^2+7^2 = 262$. Note that there are two restrictions on house $3$ and both of them must be satisfied. Also, note that even though there isn't any explicit restrictions on house $1$, we must still limit its height to be at most $10$ ($h=10$).
user: Very soon Berland will hold a School Team Programming Olympiad. From each of the m Berland regions a team of two people is invited to participate in the olympiad. The qualifying contest to form teams was held and it was attended by n Berland students. There were at least two schoolboys participating from each of the m regions of Berland. The result of each of the participants of the qualifying competition is an integer score from 0 to 800 inclusive.

The team of each region is formed from two such members of the qualifying competition of the region, that none of them can be replaced by a schoolboy of the same region, not included in the team and who received a greater number of points. There may be a situation where a team of some region can not be formed uniquely, that is, there is more than one school team that meets the properties described above. In this case, the region needs to undertake an additional contest. The two teams in the region are considered to be different if there is at least one schoolboy who is included in one team and is not included in the other team. It is guaranteed that for each region at least two its representatives participated in the qualifying contest.

Your task is, given the results of the qualifying competition, to identify the team from each region, or to announce that in this region its formation requires additional contests.


-----Input-----

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 10 000, n ≥ 2m) — the number of participants of the qualifying contest and the number of regions in Berland.

Next n lines contain the description of the participants of the qualifying contest in the following format: Surname (a string of length from 1 to 10 characters and consisting of large and small English letters), region number (integer from 1 to m) and the number of points scored by the participant (integer from 0 to 800, inclusive).

It is guaranteed that all surnames of all the participants are distinct and at least two people participated from each of the m regions. The surnames that only differ in letter cases, should be considered distinct.


-----Output-----

Print m lines. On the i-th line print the team of the i-th region — the surnames of the two team members in an arbitrary order, or a single character "?" (without the quotes) if you need to spend further qualifying contests in the region.


-----Examples-----
Input
5 2
Ivanov 1 763
Andreev 2 800
Petrov 1 595
Sidorov 1 790
Semenov 2 503

Output
Sidorov Ivanov
Andreev Semenov

Input
5 2
Ivanov 1 800
Andreev 2 763
Petrov 1 800
Sidorov 1 800
Semenov 2 503

Output
?
Andreev Semenov



-----Note-----

In the first sample region teams are uniquely determined.

In the second sample the team from region 2 is uniquely determined and the team from region 1 can have three teams: "Petrov"-"Sidorov", "Ivanov"-"Sidorov", "Ivanov" -"Petrov", so it is impossible to determine a team uniquely.
user: Natasha is going to fly to Mars. She needs to build a rocket, which consists of several stages in some order. Each of the stages is defined by a lowercase Latin letter. This way, the rocket can be described by the string — concatenation of letters, which correspond to the stages.

There are $n$ stages available. The rocket must contain exactly $k$ of them. Stages in the rocket should be ordered by their weight. So, after the stage with some letter can go only stage with a letter, which is at least two positions after in the alphabet (skipping one letter in between, or even more). For example, after letter 'c' can't go letters 'a', 'b', 'c' and 'd', but can go letters 'e', 'f', ..., 'z'.

For the rocket to fly as far as possible, its weight should be minimal. The weight of the rocket is equal to the sum of the weights of its stages. The weight of the stage is the number of its letter in the alphabet. For example, the stage 'a 'weighs one ton,' b 'weighs two tons, and' z' — $26$ tons.

Build the rocket with the minimal weight or determine, that it is impossible to build a rocket at all. Each stage can be used at most once.


-----Input-----

The first line of input contains two integers — $n$ and $k$ ($1 \le k \le n \le 50$) – the number of available stages and the number of stages to use in the rocket.

The second line contains string $s$, which consists of exactly $n$ lowercase Latin letters. Each letter defines a new stage, which can be used to build the rocket. Each stage can be used at most once.


-----Output-----

Print a single integer — the minimal total weight of the rocket or -1, if it is impossible to build the rocket at all.


-----Examples-----
Input
5 3
xyabd

Output
29
Input
7 4
problem

Output
34
Input
2 2
ab

Output
-1
Input
12 1
abaabbaaabbb

Output
1


-----Note-----

In the first example, the following rockets satisfy the condition:



 "adx" (weight is $1+4+24=29$);

 "ady" (weight is $1+4+25=30$);

 "bdx" (weight is $2+4+24=30$);

 "bdy" (weight is $2+4+25=31$).

Rocket "adx" has the minimal weight, so the answer is $29$.

In the second example, target rocket is "belo". Its weight is $2+5+12+15=34$.

In the third example, $n=k=2$, so the rocket must have both stages: 'a' and 'b'. This rocket doesn't satisfy the condition, because these letters are adjacent in the alphabet. Answer is -1.
user: Nothing has changed since the last round. Dima and Inna still love each other and want to be together. They've made a deal with Seryozha and now they need to make a deal with the dorm guards...

There are four guardposts in Dima's dorm. Each post contains two guards (in Russia they are usually elderly women). You can bribe a guard by a chocolate bar or a box of juice. For each guard you know the minimum price of the chocolate bar she can accept as a gift and the minimum price of the box of juice she can accept as a gift. If a chocolate bar for some guard costs less than the minimum chocolate bar price for this guard is, or if a box of juice for some guard costs less than the minimum box of juice price for this guard is, then the guard doesn't accept such a gift.

In order to pass through a guardpost, one needs to bribe both guards.

The shop has an unlimited amount of juice and chocolate of any price starting with 1. Dima wants to choose some guardpost, buy one gift for each guard from the guardpost and spend exactly n rubles on it.

Help him choose a post through which he can safely sneak Inna or otherwise say that this is impossible. Mind you, Inna would be very sorry to hear that!


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 10^5) — the money Dima wants to spend. Then follow four lines describing the guardposts. Each line contains four integers a, b, c, d (1 ≤ a, b, c, d ≤ 10^5) — the minimum price of the chocolate and the minimum price of the juice for the first guard and the minimum price of the chocolate and the minimum price of the juice for the second guard, correspondingly.


-----Output-----

In a single line of the output print three space-separated integers: the number of the guardpost, the cost of the first present and the cost of the second present. If there is no guardpost Dima can sneak Inna through at such conditions, print -1 in a single line. 

The guardposts are numbered from 1 to 4 according to the order given in the input.

If there are multiple solutions, you can print any of them.


-----Examples-----
Input
10
5 6 5 6
6 6 7 7
5 8 6 6
9 9 9 9

Output
1 5 5

Input
10
6 6 6 6
7 7 7 7
4 4 4 4
8 8 8 8

Output
3 4 6

Input
5
3 3 3 3
3 3 3 3
3 3 3 3
3 3 3 3

Output
-1



-----Note-----

Explanation of the first example.

The only way to spend 10 rubles to buy the gifts that won't be less than the minimum prices is to buy two 5 ruble chocolates to both guards from the first guardpost.

Explanation of the second example.

Dima needs 12 rubles for the first guardpost, 14 for the second one, 16 for the fourth one. So the only guardpost we can sneak through is the third one. So, Dima can buy 4 ruble chocolate for the first guard and 6 ruble juice of the second guard.
user: Polycarp invited all his friends to the tea party to celebrate the holiday. He has n cups, one for each of his n friends, with volumes a_1, a_2, ..., a_{n}. His teapot stores w milliliters of tea (w ≤ a_1 + a_2 + ... + a_{n}). Polycarp wants to pour tea in cups in such a way that:  Every cup will contain tea for at least half of its volume  Every cup will contain integer number of milliliters of tea  All the tea from the teapot will be poured into cups  All friends will be satisfied. 

Friend with cup i won't be satisfied, if there exists such cup j that cup i contains less tea than cup j but a_{i} > a_{j}.

For each cup output how many milliliters of tea should be poured in it. If it's impossible to pour all the tea and satisfy all conditions then output -1.


-----Input-----

The first line contains two integer numbers n and w (1 ≤ n ≤ 100, $1 \leq w \leq \sum_{i = 1}^{n} a_{i}$).

The second line contains n numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100).


-----Output-----

Output how many milliliters of tea every cup should contain. If there are multiple answers, print any of them.

If it's impossible to pour all the tea and satisfy all conditions then output -1.


-----Examples-----
Input
2 10
8 7

Output
6 4 

Input
4 4
1 1 1 1

Output
1 1 1 1 

Input
3 10
9 8 10

Output
-1



-----Note-----

In the third example you should pour to the first cup at least 5 milliliters, to the second one at least 4, to the third one at least 5. It sums up to 14, which is greater than 10 milliliters available.