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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Define the score of some binary string $$$T$$$ as the absolute difference between the number of zeroes and ones in it. (for example, $$$T=$$$ 010001 contains $$$4$$$ zeroes and $$$2$$$ ones, so the score of $$$T$$$ is $$$|4-2| = 2$$$).

Define the creepiness of some binary string $$$S$$$ as the maximum score among all of its prefixes (for example, the creepiness of $$$S=$$$ 01001 is equal to $$$2$$$ because the score of the prefix $$$S[1 \ldots 4]$$$ is $$$2$$$ and the rest of the prefixes have a score of $$$2$$$ or less).

Given two integers $$$a$$$ and $$$b$$$, construct a binary string consisting of $$$a$$$ zeroes and $$$b$$$ ones with the minimum possible creepiness.

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

The only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$ 1 \le a, b \le 100$$$)  — the numbers of zeroes and ones correspondingly.

## Output Format
For each test case, print a binary string consisting of $$$a$$$ zeroes and $$$b$$$ ones with the minimum possible creepiness. If there are multiple answers, print any of them.

## Examples
```input
5
1 1
1 2
5 2
4 5
3 7
```
```output
10
011
0011000
101010101
0001111111
```

## Note
In the first test case, the score of $$$S[1 \ldots 1]$$$ is $$$1$$$, and the score of $$$S[1 \ldots 2]$$$ is $$$0$$$.

In the second test case, the minimum possible creepiness is $$$1$$$ and one of the other answers is 101.

In the third test case, the minimum possible creepiness is $$$3$$$ and one of the other answers is 0001100.

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
Recall that a permutation of length $$$n$$$ is an array where each element from $$$1$$$ to $$$n$$$ occurs exactly once.

For a fixed positive integer $$$d$$$, let's define the cost of the permutation $$$p$$$ of length $$$n$$$ as the number of indices $$$i$$$ $$$(1 \le i < n)$$$ such that $$$p_i \cdot d = p_{i + 1}$$$.

For example, if $$$d = 3$$$ and $$$p = [5, 2, 6, 7, 1, 3, 4]$$$, then the cost of such a permutation is $$$2$$$, because $$$p_2 \cdot 3 = p_3$$$ and $$$p_5 \cdot 3 = p_6$$$.

Your task is the following one: for a given value $$$n$$$, find the permutation of length $$$n$$$ and the value $$$d$$$ with maximum possible cost (over all ways to choose the permutation and $$$d$$$). If there are multiple answers, then print any of them.

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

The single line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

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

## Output Format
For each test case, print the value $$$d$$$ in the first line, and $$$n$$$ integers in the second line — the permutation itself. If there are multiple answers, then print any of them.

## Examples
```input
2
2
3
```
```output
2
1 2
3
2 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
There are $$$n$$$ workers and $$$m$$$ tasks. The workers are numbered from $$$1$$$ to $$$n$$$. Each task $$$i$$$ has a value $$$a_i$$$ — the index of worker who is proficient in this task.

Every task should have a worker assigned to it. If a worker is proficient in the task, they complete it in $$$1$$$ hour. Otherwise, it takes them $$$2$$$ hours.

The workers work in parallel, independently of each other. Each worker can only work on one task at once.

Assign the workers to all tasks in such a way that the tasks are completed as early as possible. The work starts at time $$$0$$$. What's the minimum time all tasks can be completed by?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le m \le 2 \cdot 10^5$$$) — the number of workers and the number of tasks.

The second line contains $$$m$$$ integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$) — the index of the worker proficient in the $$$i$$$-th task.

The sum of $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the minimum time all tasks can be completed by.

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

## Note
In the first testcase, the first worker works on tasks $$$1$$$ and $$$3$$$, and the second worker works on tasks $$$2$$$ and $$$4$$$. Since they both are proficient in the corresponding tasks, they take $$$1$$$ hour on each. Both of them complete $$$2$$$ tasks in $$$2$$$ hours. Thus, all tasks are completed by $$$2$$$ hours.

In the second testcase, it's optimal to assign the first worker to tasks $$$1, 2$$$ and $$$3$$$ and the second worker to task $$$4$$$. The first worker spends $$$3$$$ hours, the second worker spends $$$2$$$ hours (since they are not proficient in the taken task).

In the third example, each worker can be assigned to the task they are proficient at. Thus, each of them complete their task in $$$1$$$ hour.

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 wanted to write a text $$$t$$$ consisting of $$$m$$$ lowercase Latin letters. But instead, you have written a text $$$s$$$ consisting of $$$n$$$ lowercase Latin letters, and now you want to fix it by obtaining the text $$$t$$$ from the text $$$s$$$.

Initially, the cursor of your text editor is at the end of the text $$$s$$$ (after its last character). In one move, you can do one of the following actions:

- press the "left" button, so the cursor is moved to the left by one position (or does nothing if it is pointing at the beginning of the text, i. e. before its first character);
- press the "right" button, so the cursor is moved to the right by one position (or does nothing if it is pointing at the end of the text, i. e. after its last character);
- press the "home" button, so the cursor is moved to the beginning of the text (before the first character of the text);
- press the "end" button, so the cursor is moved to the end of the text (after the last character of the text);
- press the "backspace" button, so the character before the cursor is removed from the text (if there is no such character, nothing happens).

Your task is to calculate the minimum number of moves required to obtain the text $$$t$$$ from the text $$$s$$$ using the given set of actions, or determine it is impossible to obtain the text $$$t$$$ from the text $$$s$$$.

You have to answer $$$T$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$T$$$ ($$$1 \le T \le 5000$$$) — the number of test cases. Then $$$T$$$ test cases follow.

The first line of the test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 5000$$$) — the length of $$$s$$$ and the length of $$$t$$$, respectively.

The second line of the test case contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

The third line of the test case contains the string $$$t$$$ consisting of $$$m$$$ lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$ ($$$\sum n \le 5000$$$).

## Output Format
For each test case, print one integer — the minimum number of moves required to obtain the text $$$t$$$ from the text $$$s$$$ using the given set of actions, or -1 if it is impossible to obtain the text $$$t$$$ from the text $$$s$$$ in the given test case.

## Examples
```input
6
9 4
aaaaaaaaa
aaaa
7 3
abacaba
aaa
5 4
aabcd
abcd
4 2
abba
bb
6 4
baraka
baka
8 7
question
problem
```
```output
5
6
3
4
4
-1
```

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: 6.5 seconds
Memory limit: 512.0 MB

# Problem
A triple of points $$$i$$$, $$$j$$$ and $$$k$$$ on a coordinate line is called beautiful if $$$i < j < k$$$ and $$$k - i \le d$$$.

You are given a set of points on a coordinate line, initially empty. You have to process queries of three types:

- add a point;
- remove a point;
- calculate the number of beautiful triples consisting of points belonging to the set.

## Input Format
The first line contains two integers $$$q$$$ and $$$d$$$ ($$$1 \le q, d \le 2 \cdot 10^5$$$) — the number of queries and the parameter for defining if a triple is beautiful, respectively.

The second line contains $$$q$$$ integers $$$a_1, a_2, \dots, a_q$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) denoting the queries. The integer $$$a_i$$$ denotes the $$$i$$$-th query in the following way:

- if the point $$$a_i$$$ belongs to the set, remove it; otherwise, add it;
- after adding or removing the point, print the number of beautiful triples.

## Output Format
For each query, print one integer — the number of beautiful triples after processing the respective query.

## Examples
```input
7 5
8 5 3 2 1 5 6
```
```output
0
0
1
2
5
1
5
```

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
Mark is asked to take a group photo of $$$2n$$$ people. The $$$i$$$-th person has height $$$h_i$$$ units.

To do so, he ordered these people into two rows, the front row and the back row, each consisting of $$$n$$$ people. However, to ensure that everyone is seen properly, the $$$j$$$-th person of the back row must be at least $$$x$$$ units taller than the $$$j$$$-th person of the front row for each $$$j$$$ between $$$1$$$ and $$$n$$$, inclusive.

Help Mark determine if this is possible.

## Input Format
The first line contains one integer $$$t$$$ ($$$1\leq t\leq 100$$$) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains two positive integers $$$n$$$ and $$$x$$$ ($$$1\leq n\leq 100$$$, $$$1\leq x\leq 10^3$$$) — the number of people in each row and the minimum difference Mark wants.

The second line of each test case contains $$$2n$$$ positive integers $$$h_1,h_2,\ldots,h_{2n}$$$ ($$$1\leq h_i\leq 10^3$$$) — the height of each person in units.

Note that the sum of $$$n$$$ over all test cases is not bounded.

## Output Format
For each test case, print a single line containing "YES" if Mark could arrange people satisfying his condition and "NO" otherwise.

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answers).

## Examples
```input
3
3 6
1 3 9 10 12 16
3 1
2 5 2 2 2 5
1 2
8 6
```
```output
YES
NO
YES
```

## Note
In the first test case, one possible order is to have the third, fifth, and sixth person on the back row and the second, first, and fourth on the front row. The heights of the people will look like this.

Back$$$9$$$$$$12$$$$$$16$$$Front$$$3$$$$$$1$$$$$$10$$$

It works because

- $$$h_3-h_2 = 9-3 \geq 6$$$,
- $$$h_5-h_1 = 12-1\geq 6$$$, and
- $$$h_6-h_4 = 16-10\geq 6$$$.

In the second test case, it can be shown there is no way to order people in a way that satisfies the condition.

In the third test case, the only way to arrange people to satisfy the condition is to have the first person on the back row and the second person on the front row.

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.5 seconds
Memory limit: 256.0 MB

# Problem
Mark is cleaning a row of $$$n$$$ rooms. The $$$i$$$-th room has a nonnegative dust level $$$a_i$$$. He has a magical cleaning machine that can do the following three-step operation.

- Select two indices $$$i<j$$$ such that the dust levels $$$a_i$$$, $$$a_{i+1}$$$, $$$\dots$$$, $$$a_{j-1}$$$ are all strictly greater than $$$0$$$.
- Set $$$a_i$$$ to $$$a_i-1$$$.
- Set $$$a_j$$$ to $$$a_j+1$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$) — the number of test cases.

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

The second line of each test case contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0\leq a_i\leq 10^9$$$) — the dust level of each room.

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

## Output Format
For each test case, print a line containing a single integer — the minimum number of operations. It can be proven that there is a sequence of operations that meets the goal.

## Examples
```input
4
3
2 0 0
5
0 2 0 2 0
6
2 0 3 0 4 6
4
0 0 0 10
```
```output
3
5
11
0
```

## Note
In the first case, one possible sequence of operations is as follows.

- Choose $$$i=1$$$ and $$$j=2$$$, yielding the array $$$[1,1,0]$$$.
- Choose $$$i=1$$$ and $$$j=3$$$, yielding the array $$$[0,1,1]$$$.
- Choose $$$i=2$$$ and $$$j=3$$$, yielding the array $$$[0,0,2]$$$.

In the second case, one possible sequence of operations is as follows.

- Choose $$$i=4$$$ and $$$j=5$$$, yielding the array $$$[0,2,0,1,1]$$$.
- Choose $$$i=2$$$ and $$$j=3$$$, yielding the array $$$[0,1,1,1,1]$$$.
- Choose $$$i=2$$$ and $$$j=5$$$, yielding the array $$$[0,0,1,1,2]$$$.
- Choose $$$i=3$$$ and $$$j=5$$$, yielding the array $$$[0,0,0,1,3]$$$.
- Choose $$$i=4$$$ and $$$j=5$$$, yielding the array $$$[0,0,0,0,4]$$$.

In the last case, the array already satisfies the condition.

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
Burenka and Tonya are playing an old Buryat game with a chip on a board of $$$n \times m$$$ cells.

At the beginning of the game, the chip is located in the lower left corner of the board. In one move, the player can move the chip to the right or up by any odd number of cells (but you cannot move the chip both to the right and up in one move). The one who cannot make a move loses.

Burenka makes the first move, the players take turns. Burenka really wants to win the game, but she is too lazy to come up with a strategy, so you are invited to solve the difficult task of finding it. Name the winner of the game (it is believed that Burenka and Tonya are masters of playing with chips, so they always move in the optimal way).

Chip's starting cell is green, the only cell from which chip can't move is red. if the chip is in the yellow cell, then blue cells are all options to move the chip in one move.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The following is a description of the input data sets.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^9$$$) — the dimensions of the game board.

## Output Format
For each test case print a single line — the name of the winner of the game ("Burenka" or "Tonya").

## Examples
```input
6
1 1
1 4
5 6
2 2
6 3
999999999 1000000000
```
```output
Tonya
Burenka
Burenka
Tonya
Burenka
Burenka
```

## Note
In the first case, Burenka has no move, so Tonya wins.

In the second case, Burenka can move $$$3$$$ cells to the right, after which Tony will not be able to make a move, which means that Burenka wins.

In the third case, Burenka can move $$$5$$$ squares to the right. Then we can say that we have a game on a board of $$$1 \times 5$$$ cells, and Tonya is the first player. In such game the second player wins, so in the original one Burenka will win.

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
A new entertainment has appeared in Buryatia — a mathematical circus! The magician shows two numbers to the audience — $$$n$$$ and $$$k$$$, where $$$n$$$ is even. Next, he takes all the integers from $$$1$$$ to $$$n$$$, and splits them all into pairs $$$(a, b)$$$ (each integer must be in exactly one pair) so that for each pair the integer $$$(a + k) \cdot b$$$ is divisible by $$$4$$$ (note that the order of the numbers in the pair matters), or reports that, unfortunately for viewers, such a split is impossible.

Burenka really likes such performances, so she asked her friend Tonya to be a magician, and also gave him the numbers $$$n$$$ and $$$k$$$.

Tonya is a wolf, and as you know, wolves do not perform in the circus, even in a mathematical one. Therefore, he asks you to help him. Let him know if a suitable splitting into pairs is possible, and if possible, then tell it.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The following is a description of the input data sets.

The single line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^9$$$, $$$n$$$ is even) — the number of integers and the number being added $$$k$$$.

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

## Output Format
For each test case, first output the string "YES" if there is a split into pairs, and "NO" if there is none.

If there is a split, then in the following $$$\frac{n}{2}$$$ lines output pairs of the split, in each line print $$$2$$$ numbers — first the integer $$$a$$$, then the integer $$$b$$$.

## Examples
```input
4
4 1
2 0
12 10
14 11
```
```output
YES
1 2
3 4
NO
YES
3 4
7 8
11 12
2 1
6 5
10 9
YES
1 2
3 4
5 6
7 8
9 10
11 12
13 14
```

## Note
In the first test case, splitting into pairs $$$(1, 2)$$$ and $$$(3, 4)$$$ is suitable, same as splitting into $$$(1, 4)$$$ and $$$(3, 2)$$$.

In the second test case, $$$(1 + 0) \cdot 2 = 1 \cdot (2 + 0) = 2$$$ is not divisible by $$$4$$$, so there is no partition.

Now solve the problem and return the code.