apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Everyone knows that hobbits love to organize all sorts of parties and celebrations. There are n hobbits living in the Shire. They decided to organize the Greatest Party (GP) that would last for several days. Next day the hobbits wrote a guest list, some non-empty set containing all the inhabitants of the Shire. To ensure that everybody enjoy themselves and nobody gets bored, for any two days (say, days A and B) of the GP there existed at least one hobbit, invited to come on day A and on day B. However, to ensure that nobody has a row, for any three different days A, B, C there shouldn't be a hobbit invited on days A, B and C. The Shire inhabitants are keen on keeping the GP going for as long as possible. Your task is given number n, to indicate the GP's maximum duration and the guest lists for each day.

## Input Format
The first line contains an integer n (3 ≤ n ≤ 10000), representing the number of hobbits.

## Output Format
In the first output line print a number k — the maximum duration of GP in days. Then on k lines print the guest lists, (the guests should be separated by spaces). Print each guest list on the single line. Each list can contain an arbitrary positive number of hobbits. The hobbits are numbered with integers from 1 to n.

## Examples
```input
4
```
```output
3
1 2
1 3
2 3
```
-----
```input
5
```
```output
3
1 2
1 3
2 3
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
An arithmetic progression is such a non-empty sequence of numbers where the difference between any two successive numbers is constant. This constant number is called common difference. For example, the sequence 3, 7, 11, 15 is an arithmetic progression. The definition implies that any sequences whose length equals 1 or 2 are arithmetic and all sequences whose length equals 0 are non-arithmetic.

You are given a sequence of different integers a1, a2, ..., an. You should either split it into two arithmetic progressions or find out that the operation is impossible to perform. Splitting assigns each member of the given sequence to one of two progressions, but the relative order of numbers does not change. Splitting is an inverse operation to merging.

## Input Format
The first line contains a positive integer n (2 ≤ n ≤ 30000), n is the length of the given sequence. The second line contains elements of the given sequence a1, a2, ..., an ( - 108 ≤ ai ≤ 108). The elements of the progression are different integers.

## Output Format
Print the required arithmetic progressions, one per line. The progressions can be positioned in any order. Each progression should contain at least one number. If there's no solution, then print "No solution" (without the quotes)in the only line of the input file. If there are several solutions, print any of them.

## Examples
```input
6
4 1 2 7 3 10
```
```output
1 2 3
4 7 10
```
-----
```input
5
1 2 3 -2 -7
```
```output
1 2 3
-2 -7
```

## Note
In the second sample another solution is also possible (number three can be assigned to the second progression): 1, 2 and 3, -2, -7.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 8.0 seconds
Memory limit: 256.0 MB

# Problem
The MST (Meaningless State Team) company won another tender for an important state reform in Berland.

There are n cities in Berland, some pairs of the cities are connected by roads. Each road has its price. One can move along any road in any direction. The MST team should carry out the repair works on some set of roads such that one can get from any city to any other one moving only along the repaired roads. Moreover, this set should contain exactly k capital roads (that is, the roads that start or finish in the capital). The number of the capital is 1.

As the budget has already been approved, the MST Company will profit by finding the set with minimum lengths of roads.

## Input Format
The first input line contains three integers n, m, k (1 ≤ n ≤ 5000;0 ≤ m ≤ 105;0 ≤ k < 5000), where n is the number of cities in the country, m is the number of roads in the country, k is the number of capital roads in the required set. Then m lines enumerate the roads in question. Each road is specified by three numbers ai, bi, wi (1 ≤ ai, bi ≤ n; 1 ≤ w ≤ 105), where ai, bi are the numbers of cities linked by a road and wi is its length.

Between each pair of cities no more than one road exists. There are no roads that start and finish in one city. The capital's number is 1.

## Output Format
In the first line print the number of roads in the required set. The second line should contain the numbers of roads included in the sought set. If the sought set does not exist, print -1.

## Examples
```input
4 5 2
1 2 1
2 3 1
3 4 1
1 3 3
1 4 2
```
```output
3
1 5 2
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Recently Polycarp noticed that some of the buttons of his keyboard are malfunctioning. For simplicity, we assume that Polycarp's keyboard contains $$$26$$$ buttons (one for each letter of the Latin alphabet). Each button is either working fine or malfunctioning.

To check which buttons need replacement, Polycarp pressed some buttons in sequence, and a string $$$s$$$ appeared on the screen. When Polycarp presses a button with character $$$c$$$, one of the following events happened:

- if the button was working correctly, a character $$$c$$$ appeared at the end of the string Polycarp was typing;
- if the button was malfunctioning, two characters $$$c$$$ appeared at the end of the string.

For example, suppose the buttons corresponding to characters a and c are working correctly, and the button corresponding to b is malfunctioning. If Polycarp presses the buttons in the order a, b, a, c, a, b, a, then the string he is typing changes as follows: a $$$\rightarrow$$$ abb $$$\rightarrow$$$ abba $$$\rightarrow$$$ abbac $$$\rightarrow$$$ abbaca $$$\rightarrow$$$ abbacabb $$$\rightarrow$$$ abbacabba.

You are given a string $$$s$$$ which appeared on the screen after Polycarp pressed some buttons. Help Polycarp to determine which buttons are working correctly for sure (that is, this string could not appear on the screen if any of these buttons was malfunctioning).

You may assume that the buttons don't start malfunctioning when Polycarp types the string: each button either works correctly throughout the whole process, or malfunctions throughout the whole process.

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

Then the test cases follow. Each test case is represented by one line containing a string $$$s$$$ consisting of no less than $$$1$$$ and no more than $$$500$$$ lowercase Latin letters.

## Output Format
For each test case, print one line containing a string $$$res$$$. The string $$$res$$$ should contain all characters which correspond to buttons that work correctly in alphabetical order, without any separators or repetitions. If all buttons may malfunction, $$$res$$$ should be empty.

## Examples
```input
4
a
zzaaz
ccff
cbddbb
```
```output
a
z

bc
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A palindrome is a string $$$t$$$ which reads the same backward as forward (formally, $$$t[i] = t[|t| + 1 - i]$$$ for all $$$i \in [1, |t|]$$$). Here $$$|t|$$$ denotes the length of a string $$$t$$$. For example, the strings 010, 1001 and 0 are palindromes.

You have $$$n$$$ binary strings $$$s_1, s_2, \dots, s_n$$$ (each $$$s_i$$$ consists of zeroes and/or ones). You can swap any pair of characters any number of times (possibly, zero). Characters can be either from the same string or from different strings — there are no restrictions.

Formally, in one move you:

- choose four integer numbers $$$x, a, y, b$$$ such that $$$1 \le x, y \le n$$$ and $$$1 \le a \le |s_x|$$$ and $$$1 \le b \le |s_y|$$$ (where $$$x$$$ and $$$y$$$ are string indices and $$$a$$$ and $$$b$$$ are positions in strings $$$s_x$$$ and $$$s_y$$$ respectively),
- swap (exchange) the characters $$$s_x[a]$$$ and $$$s_y[b]$$$.

What is the maximum number of strings you can make palindromic simultaneously?

## Input Format
The first line contains single integer $$$Q$$$ ($$$1 \le Q \le 50$$$) — the number of test cases.

The first line on each test case contains single integer $$$n$$$ ($$$1 \le n \le 50$$$) — the number of binary strings you have.

Next $$$n$$$ lines contains binary strings $$$s_1, s_2, \dots, s_n$$$ — one per line. It's guaranteed that $$$1 \le |s_i| \le 50$$$ and all strings constist of zeroes and/or ones.

## Output Format
Print $$$Q$$$ integers — one per test case. The $$$i$$$-th integer should be the maximum number of palindromic strings you can achieve simultaneously performing zero or more swaps on strings from the $$$i$$$-th test case.

## Examples
```input
4
1
0
3
1110
100110
010101
2
11111
000001
2
001
11100111
```
```output
1
2
2
2
```

## Note
In the first test case, $$$s_1$$$ is palindrome, so the answer is $$$1$$$.

In the second test case you can't make all three strings palindromic at the same time, but you can make any pair of strings palindromic. For example, let's make $$$s_1 = \text{0110}$$$, $$$s_2 = \text{111111}$$$ and $$$s_3 = \text{010000}$$$.

In the third test case we can make both strings palindromic. For example, $$$s_1 = \text{11011}$$$ and $$$s_2 = \text{100001}$$$.

In the last test case $$$s_2$$$ is palindrome and you can make $$$s_1$$$ palindrome, for example, by swapping $$$s_1[2]$$$ and $$$s_1[3]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a huge integer $$$a$$$ consisting of $$$n$$$ digits ($$$n$$$ is between $$$1$$$ and $$$3 \cdot 10^5$$$, inclusive). It may contain leading zeros.

You can swap two digits on adjacent (neighboring) positions if the swapping digits are of different parity (that is, they have different remainders when divided by $$$2$$$).

For example, if $$$a = 032867235$$$ you can get the following integers in a single operation:

- $$$302867235$$$ if you swap the first and the second digits;
- $$$023867235$$$ if you swap the second and the third digits;
- $$$032876235$$$ if you swap the fifth and the sixth digits;
- $$$032862735$$$ if you swap the sixth and the seventh digits;
- $$$032867325$$$ if you swap the seventh and the eighth digits.

Note, that you can't swap digits on positions $$$2$$$ and $$$4$$$ because the positions are not adjacent. Also, you can't swap digits on positions $$$3$$$ and $$$4$$$ because the digits have the same parity.

You can perform any number (possibly, zero) of such operations.

Find the minimum integer you can obtain.

Note that the resulting integer also may contain leading zeros.

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

The only line of each test case contains the integer $$$a$$$, its length $$$n$$$ is between $$$1$$$ and $$$3 \cdot 10^5$$$, inclusive.

It is guaranteed that the sum of all values $$$n$$$ does not exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case print line — the minimum integer you can obtain.

## Examples
```input
3
0709
1337
246432
```
```output
0079
1337
234642
```

## Note
In the first test case, you can perform the following sequence of operations (the pair of swapped digits is highlighted): $$$0 \underline{\textbf{70}} 9 \rightarrow 0079$$$.

In the second test case, the initial integer is optimal.

In the third test case you can perform the following sequence of operations: $$$246 \underline{\textbf{43}} 2 \rightarrow 24 \underline{\textbf{63}}42 \rightarrow 2 \underline{\textbf{43}} 642 \rightarrow 234642$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are the head of a large enterprise. $$$n$$$ people work at you, and $$$n$$$ is odd (i. e. $$$n$$$ is not divisible by $$$2$$$).

You have to distribute salaries to your employees. Initially, you have $$$s$$$ dollars for it, and the $$$i$$$-th employee should get a salary from $$$l_i$$$ to $$$r_i$$$ dollars. You have to distribute salaries in such a way that the median salary is maximum possible.

To find the median of a sequence of odd length, you have to sort it and take the element in the middle position after sorting. For example:

- the median of the sequence $$$[5, 1, 10, 17, 6]$$$ is $$$6$$$,
- the median of the sequence $$$[1, 2, 1]$$$ is $$$1$$$.

It is guaranteed that you have enough money to pay the minimum salary, i.e $$$l_1 + l_2 + \dots + l_n \le s$$$.

Note that you don't have to spend all your $$$s$$$ dollars on salaries.

You have to answer $$$t$$$ test cases.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.

The first line of each query contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n < 2 \cdot 10^5$$$, $$$1 \le s \le 2 \cdot 10^{14}$$$) — the number of employees and the amount of money you have. The value $$$n$$$ is not divisible by $$$2$$$.

The following $$$n$$$ lines of each query contain the information about employees. The $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$).

It is guaranteed that the sum of all $$$n$$$ over all queries does not exceed $$$2 \cdot 10^5$$$.

It is also guaranteed that you have enough money to pay the minimum salary to each employee, i. e. $$$\sum\limits_{i=1}^{n} l_i \le s$$$.

## Output Format
For each test case print one integer — the maximum median salary that you can obtain.

## Examples
```input
3
3 26
10 12
1 4
10 11
1 1337
1 1000000000
5 26
4 4
2 4
6 8
5 6
2 7
```
```output
11
1337
6
```

## Note
In the first test case, you can distribute salaries as follows: $$$sal_1 = 12, sal_2 = 2, sal_3 = 11$$$ ($$$sal_i$$$ is the salary of the $$$i$$$-th employee). Then the median salary is $$$11$$$.

In the second test case, you have to pay $$$1337$$$ dollars to the only employee.

In the third test case, you can distribute salaries as follows: $$$sal_1 = 4, sal_2 = 3, sal_3 = 6, sal_4 = 6, sal_5 = 7$$$. Then the median salary is $$$6$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Several days ago you bought a new house and now you are planning to start a renovation. Since winters in your region can be very cold you need to decide how to heat rooms in your house.

Your house has $$$n$$$ rooms. In the $$$i$$$-th room you can install at most $$$c_i$$$ heating radiators. Each radiator can have several sections, but the cost of the radiator with $$$k$$$ sections is equal to $$$k^2$$$ burles.

Since rooms can have different sizes, you calculated that you need at least $$$sum_i$$$ sections in total in the $$$i$$$-th room.

For each room calculate the minimum cost to install at most $$$c_i$$$ radiators with total number of sections not less than $$$sum_i$$$.

## Input Format
The first line contains single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of rooms.

Each of the next $$$n$$$ lines contains the description of some room. The $$$i$$$-th line contains two integers $$$c_i$$$ and $$$sum_i$$$ ($$$1 \le c_i, sum_i \le 10^4$$$) — the maximum number of radiators and the minimum total number of sections in the $$$i$$$-th room, respectively.

## Output Format
For each room print one integer — the minimum possible cost to install at most $$$c_i$$$ radiators with total number of sections not less than $$$sum_i$$$.

## Examples
```input
4
1 10000
10000 1
2 6
4 6
```
```output
100000000
1
18
10
```

## Note
In the first room, you can install only one radiator, so it's optimal to use the radiator with $$$sum_1$$$ sections. The cost of the radiator is equal to $$$(10^4)^2 = 10^8$$$.

In the second room, you can install up to $$$10^4$$$ radiators, but since you need only one section in total, it's optimal to buy one radiator with one section.

In the third room, there $$$7$$$ variants to install radiators: $$$[6, 0]$$$, $$$[5, 1]$$$, $$$[4, 2]$$$, $$$[3, 3]$$$, $$$[2, 4]$$$, $$$[1, 5]$$$, $$$[0, 6]$$$. The optimal variant is $$$[3, 3]$$$ and it costs $$$3^2+ 3^2 = 18$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$a$$$ and $$$b$$$. You may perform any number of operations on them (possibly zero).

During each operation you should choose any positive integer $$$x$$$ and set $$$a := a - x$$$, $$$b := b - 2x$$$ or $$$a := a - 2x$$$, $$$b := b - x$$$. Note that you may choose different values of $$$x$$$ in different operations.

Is it possible to make $$$a$$$ and $$$b$$$ equal to $$$0$$$ simultaneously?

Your program should answer $$$t$$$ independent test cases.

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

Then the test cases follow, each test case is represented by one line containing two integers $$$a$$$ and $$$b$$$ for this test case ($$$0 \le a, b \le 10^9$$$).

## Output Format
For each test case print the answer to it — YES if it is possible to make $$$a$$$ and $$$b$$$ equal to $$$0$$$ simultaneously, 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).

## Examples
```input
3
6 9
1 1
1 2
```
```output
YES
NO
YES
```

## Note
In the first test case of the example two operations can be used to make both $$$a$$$ and $$$b$$$ equal to zero:

1. choose $$$x = 4$$$ and set $$$a := a - x$$$, $$$b := b - 2x$$$. Then $$$a = 6 - 4 = 2$$$, $$$b = 9 - 8 = 1$$$;
2. choose $$$x = 1$$$ and set $$$a := a - 2x$$$, $$$b := b - x$$$. Then $$$a = 2 - 2 = 0$$$, $$$b = 1 - 1 = 0$$$.

Now solve the problem and return the code.