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 python3.

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:
```python
<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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There is an array $$$a$$$ with $$$n-1$$$ integers. Let $$$x$$$ be the bitwise XOR of all elements of the array. The number $$$x$$$ is added to the end of the array $$$a$$$ (now it has length $$$n$$$), and then the elements are shuffled.

You are given the newly formed array $$$a$$$. What is $$$x$$$? If there are multiple possible values of $$$x$$$, you can output any of them.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of integers in the resulting array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 127$$$) — the elements of the newly formed array $$$a$$$.

Additional constraint on the input: the array $$$a$$$ is made by the process described in the statement; that is, some value of $$$x$$$ exists.

## Output Format
For each test case, output a single integer — the value of $$$x$$$, as described in the statement. If there are multiple possible values of $$$x$$$, output any of them.

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

## Note
In the first test case, one possible array $$$a$$$ is $$$a=[2, 5, 4]$$$. Then $$$x = 2 \oplus 5 \oplus 4 = 3$$$ ($$$\oplus$$$ denotes the bitwise XOR), so the new array is $$$[2, 5, 4, 3]$$$. Afterwards, the array is shuffled to form $$$[4, 3, 2, 5]$$$.

In the second test case, one possible array $$$a$$$ is $$$a=[1, 10, 6, 10]$$$. Then $$$x = 1 \oplus 10 \oplus 6 \oplus 10 = 7$$$, so the new array is $$$[1, 10, 6, 10, 7]$$$. Afterwards, the array is shuffled to form $$$[6, 1, 10, 7, 10]$$$.

In the third test case, all elements of the array are equal to $$$6$$$, so $$$x=6$$$.

In the fourth test case, one possible array $$$a$$$ is $$$a=[100, 100]$$$. Then $$$x = 100 \oplus 100 = 0$$$, so the new array is $$$[100, 100, 0]$$$. Afterwards, the array is shuffled to form $$$[100, 100, 0]$$$. (Note that after the shuffle, the array can remain the same.)

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ piles of sand where the $$$i$$$-th pile has $$$a_i$$$ blocks of sand. The $$$i$$$-th pile is called too tall if $$$1 < i < n$$$ and $$$a_i > a_{i-1} + a_{i+1}$$$. That is, a pile is too tall if it has more sand than its two neighbours combined. (Note that piles on the ends of the array cannot be too tall.)

You are given an integer $$$k$$$. An operation consists of picking $$$k$$$ consecutive piles of sand and adding one unit of sand to them all. Formally, pick $$$1 \leq l,r \leq n$$$ such that $$$r-l+1=k$$$. Then for all $$$l \leq i \leq r$$$, update $$$a_i \gets a_i+1$$$.

What is the maximum number of piles that can simultaneously be too tall after some (possibly zero) operations?

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq k \leq n$$$) — the number of piles of sand and the size of the operation, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the sizes of the piles.

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, output a single integer — the maximum number of piles that are simultaneously too tall after some (possibly zero) operations.

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

## Note
In the first test case, we can perform the following three operations:

- Add one unit of sand to piles $$$1$$$ and $$$2$$$: $$$[\color{red}{3}, \color{red}{10}, 2, 4, 1]$$$.
- Add one unit of sand to piles $$$4$$$ and $$$5$$$: $$$[3, 10, 2, \color{red}{5}, \color{red}{2}]$$$.
- Add one unit of sand to piles $$$3$$$ and $$$4$$$: $$$[3, 10, \color{red}{3}, \color{red}{6}, 2]$$$.

In the second test case, any operation will increase all piles by $$$1$$$ unit, so the number of too tall piles will always be $$$0$$$.

In the third test case, we can increase any pile by $$$1$$$ unit of sand. It can be shown that the maximum number of too tall piles is $$$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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of length $$$n$$$. The array is called 3SUM-closed if for all distinct indices $$$i$$$, $$$j$$$, $$$k$$$, the sum $$$a_i + a_j + a_k$$$ is an element of the array. More formally, $$$a$$$ is 3SUM-closed if for all integers $$$1 \leq i < j < k \leq n$$$, there exists some integer $$$1 \leq l \leq n$$$ such that $$$a_i + a_j + a_k = a_l$$$.

Determine if $$$a$$$ is 3SUM-closed.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — the elements of the array.

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, output "YES" (without quotes) if $$$a$$$ is 3SUM-closed and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

## Examples
```input
4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4
```
```output
YES
NO
YES
NO
```

## Note
In the first test case, there is only one triple where $$$i=1$$$, $$$j=2$$$, $$$k=3$$$. In this case, $$$a_1 + a_2 + a_3 = 0$$$, which is an element of the array ($$$a_2 = 0$$$), so the array is 3SUM-closed.

In the second test case, $$$a_1 + a_4 + a_5 = -1$$$, which is not an element of the array. Therefore, the array is not 3SUM-closed.

In the third test case, $$$a_i + a_j + a_k = 0$$$ for all distinct $$$i$$$, $$$j$$$, $$$k$$$, and $$$0$$$ is an element of the array, so the array is 3SUM-closed.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There is a binary string $$$t$$$ of length $$$10^{100}$$$, and initally all of its bits are $$$\texttt{0}$$$. You are given a binary string $$$s$$$, and perform the following operation some times:

- Select some substring of $$$t$$$, and replace it with its XOR with $$$s$$$.$$$^\dagger$$$

Find the lexicographically largest$$$^\ddagger$$$ string $$$t$$$ satisfying these constraints, or report that no such string exists.

$$$^\dagger$$$ Formally, choose an index $$$i$$$ such that $$$0 \leq i \leq 10^{100}-|s|$$$. For all $$$1 \leq j \leq |s|$$$, if $$$s_j = \texttt{1}$$$, then toggle $$$t_{i+j}$$$. That is, if $$$t_{i+j}=\texttt{0}$$$, set $$$t_{i+j}=\texttt{1}$$$. Otherwise if $$$t_{i+j}=\texttt{1}$$$, set $$$t_{i+j}=\texttt{0}$$$.

$$$^\ddagger$$$ A binary string $$$a$$$ is lexicographically larger than a binary string $$$b$$$ of the same length if in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a bit $$$\texttt{1}$$$ and the corresponding bit in $$$b$$$ is $$$\texttt{0}$$$.

## Input Format
The only line of each test contains a single binary string $$$s$$$ ($$$1 \leq |s| \leq 35$$$).

## Output Format
If no string $$$t$$$ exists as described in the statement, output -1. Otherwise, output the integers $$$p$$$ and $$$q$$$ ($$$1 \leq p < q \leq 10^{100}$$$) such that the $$$p$$$-th and $$$q$$$-th bits of the lexicographically maximal $$$t$$$ are $$$\texttt{1}$$$.

## Examples
```input
1
```
```output
1 2
```
-----
```input
001
```
```output
3 4
```
-----
```input
1111
```
```output
1 5
```
-----
```input
00000
```
```output
-1
```
-----
```input
00000111110000011111000001111101010
```
```output
6 37452687
```

## Note
In the first test, you can perform the following operations. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{1}}\texttt{0000}\ldots \to \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots$$$$$$

In the second test, you can perform the following operations. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{001}}\texttt{00}\ldots \to \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots$$$$$$

In the third test, you can perform the following operations. $$$$$$\texttt{00000}\ldots \to \color{red}{\texttt{1111}}\texttt{0}\ldots \to \texttt{1}\color{red}{\texttt{0001}}\ldots$$$$$$

It can be proven that these strings $$$t$$$ are the lexicographically largest ones.

In the fourth test, you can't make a single bit $$$\texttt{1}$$$, so it is impossible.

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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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.