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

# Problem
Рассмотрим следующий код сортировки слиянием на языке Python:

Как можно заметить, этот код использует логирование — важнейший инструмент разработки.

Старший разработчик ВКонтакте Вася сгенерировал перестановку $$$a$$$ (массив из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$), дал её на вход функции sort и получил на выходе строку $$$s$$$. На следующий день строку $$$s$$$ Вася нашёл, а перестановка $$$a$$$ потерялась.

Вася хочет восстановить любую перестановку $$$a$$$ такую, что вызов функции sort от неё даст ту же строку $$$s$$$. Помогите ему!

## Input Format
Ввод содержит непустую строку $$$s$$$, состоящую из символов 0 и 1.

В этой версии задачи для любого теста существует перестановка длины не более $$$10^5$$$, удовлетворяющая условию. Тем не менее, ваш ответ может иметь любую длину, в том числе превышающую $$$10^5$$$.

## Output Format
В первой строке выведите целое число $$$n$$$ — длину перестановки.

Во второй строке выведите $$$n$$$ различных целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки.

Если существует несколько вариантов ответа, выведите любой из них.

## Examples
```input
00000000000000000000000000000000
```
```output
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
```
-----
```input
11111111111111111111111111111111
```
```output
16
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
```
-----
```input
101011010001100100011011001111011000011110010
```
```output
16
13 6 1 7 12 5 4 15 14 16 10 11 3 8 9 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 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
Four players participate in the playoff tournament. The tournament is held according to the following scheme: the first player will play with the second, and the third player with the fourth, then the winners of the pairs will play in the finals of the tournament.

It is known that in a match between two players, the one whose skill is greater will win. The skill of the $$$i$$$-th player is equal to $$$s_i$$$ and all skill levels are pairwise different (i. e. there are no two identical values in the array $$$s$$$).

The tournament is called fair if the two players with the highest skills meet in the finals.

Determine whether the given tournament is fair.

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

A single line of test case contains four integers $$$s_1, s_2, s_3, s_4$$$ ($$$1 \le s_i \le 100$$$) — skill of the players. It is guaranteed that all the numbers in the array are different.

## Output Format
For each testcase, output YES if the tournament is fair, or NO otherwise.

## Examples
```input
4
3 7 9 5
4 5 6 9
5 3 8 1
6 5 3 2
```
```output
YES
NO
YES
NO
```

## Note
Consider the example:

1. in the first test case, players $$$2$$$ and $$$3$$$ with skills $$$7$$$ and $$$9$$$ advance to the finals;
2. in the second test case, players $$$2$$$ and $$$4$$$ with skills $$$5$$$ and $$$9$$$ advance to the finals. The player with skill $$$6$$$ does not advance, but the player with skill $$$5$$$ advances to the finals, so the tournament is not fair;
3. in the third test case, players $$$1$$$ and $$$3$$$ with skills $$$5$$$ and $$$8$$$ advance to the finals;
4. in the fourth test case, players $$$1$$$ and $$$3$$$ with skills $$$6$$$ and $$$3$$$ advance to the finals. The player with skill $$$5$$$ does not advance, but the player with skill $$$3$$$ advances to the finals, so the tournament is not fair.

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 are given an array $$$a$$$ consisting of $$$n$$$ integers.

Let's call a pair of indices $$$i$$$, $$$j$$$ good if $$$1 \le i < j \le n$$$ and $$$\gcd(a_i, 2a_j) > 1$$$ (where $$$\gcd(x, y)$$$ is the greatest common divisor of $$$x$$$ and $$$y$$$).

Find the maximum number of good index pairs if you can reorder the array $$$a$$$ in an arbitrary way.

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

The first line of the test case contains a single integer $$$n$$$ ($$$2 \le n \le 2000$$$) — the number of elements in the array.

The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

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

## Output Format
For each test case, output a single integer — the maximum number of good index pairs if you can reorder the array $$$a$$$ in an arbitrary way.

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

## Note
In the first example, the array elements can be rearranged as follows: $$$[6, 3, 5, 3]$$$.

In the third example, the array elements can be rearranged as follows: $$$[4, 4, 2, 1, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string $$$s$$$ consisting of the characters 0, 1, and ?.

Let's call a string unstable if it consists of the characters 0 and 1 and any two adjacent characters are different (i. e. it has the form 010101... or 101010...).

Let's call a string beautiful if it consists of the characters 0, 1, and ?, and you can replace the characters ? to 0 or 1 (for each character, the choice is independent), so that the string becomes unstable.

For example, the strings 0??10, 0, and ??? are beautiful, and the strings 00 and ?1??1 are not.

Calculate the number of beautiful contiguous substrings of the string $$$s$$$.

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

The first and only line of each test case contains the string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) consisting of characters 0, 1, and ?.

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

## Output Format
For each test case, output a single integer — the number of beautiful substrings of the string $$$s$$$.

## Examples
```input
3
0?10
???
?10??1100
```
```output
8
6
25
```

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
$$$2^k$$$ teams participate in a playoff tournament. The tournament consists of $$$2^k - 1$$$ games. They are held as follows: first of all, the teams are split into pairs: team $$$1$$$ plays against team $$$2$$$, team $$$3$$$ plays against team $$$4$$$ (exactly in this order), and so on (so, $$$2^{k-1}$$$ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $$$2^{k-1}$$$ teams remain. If only one team remains, it is declared the champion; otherwise, $$$2^{k-2}$$$ games are played: in the first one of them, the winner of the game "$$$1$$$ vs $$$2$$$" plays against the winner of the game "$$$3$$$ vs $$$4$$$", then the winner of the game "$$$5$$$ vs $$$6$$$" plays against the winner of the game "$$$7$$$ vs $$$8$$$", and so on. This process repeats until only one team remains.

For example, this picture describes the chronological order of games with $$$k = 3$$$:

Let the string $$$s$$$ consisting of $$$2^k - 1$$$ characters describe the results of the games in chronological order as follows:

- if $$$s_i$$$ is 0, then the team with lower index wins the $$$i$$$-th game;
- if $$$s_i$$$ is 1, then the team with greater index wins the $$$i$$$-th game;
- if $$$s_i$$$ is ?, then the result of the $$$i$$$-th game is unknown (any team could win this game).

Let $$$f(s)$$$ be the number of possible winners of the tournament described by the string $$$s$$$. A team $$$i$$$ is a possible winner of the tournament if it is possible to replace every ? with either 1 or 0 in such a way that team $$$i$$$ is the champion.

You are given the initial state of the string $$$s$$$. You have to process $$$q$$$ queries of the following form:

- $$$p$$$ $$$c$$$ — replace $$$s_p$$$ with character $$$c$$$, and print $$$f(s)$$$ as the result of the query.

## Input Format
The first line contains one integer $$$k$$$ ($$$1 \le k \le 18$$$).

The second line contains a string consisting of $$$2^k - 1$$$ characters — the initial state of the string $$$s$$$. Each character is either ?, 0, or 1.

The third line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, the $$$i$$$-th line contains an integer $$$p$$$ and a character $$$c$$$ ($$$1 \le p \le 2^k - 1$$$; $$$c$$$ is either ?, 0, or 1), describing the $$$i$$$-th query.

## Output Format
For each query, print one integer — $$$f(s)$$$.

## Examples
```input
3
0110?11
6
5 1
6 ?
7 ?
1 ?
5 ?
1 1
```
```output
1
2
3
3
5
4
```

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: 1024.0 MB

# Problem
Suppose you are given two strings $$$a$$$ and $$$b$$$. You can apply the following operation any number of times: choose any contiguous substring of $$$a$$$ or $$$b$$$, and sort the characters in it in non-descending order. Let $$$f(a, b)$$$ the minimum number of operations you have to apply in order to make them equal (or $$$f(a, b) = 1337$$$ if it is impossible to make $$$a$$$ and $$$b$$$ equal using these operations).

For example:

- $$$f(\text{ab}, \text{ab}) = 0$$$;
- $$$f(\text{ba}, \text{ab}) = 1$$$ (in one operation, we can sort the whole first string);
- $$$f(\text{ebcda}, \text{ecdba}) = 1$$$ (in one operation, we can sort the substring of the second string starting from the $$$2$$$-nd character and ending with the $$$4$$$-th character);
- $$$f(\text{a}, \text{b}) = 1337$$$.

You are given $$$n$$$ strings $$$s_1, s_2, \dots, s_k$$$ having equal length. Calculate $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.

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

Then $$$n$$$ lines follow, each line contains one of the strings $$$s_i$$$, consisting of lowercase Latin letters. $$$|s_1| = |s_2| = \ldots = |s_n|$$$, and $$$n \cdot |s_1| \le 2 \cdot 10^5$$$. All these strings are pairwise distinct.

## Output Format
Print one integer: $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.

## Examples
```input
4
zzz
bac
abc
acb
```
```output
4015
```
-----
```input
2
a
b
```
```output
1337
```

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
Let's define $$$S(x)$$$ to be the sum of digits of number $$$x$$$ written in decimal system. For example, $$$S(5) = 5$$$, $$$S(10) = 1$$$, $$$S(322) = 7$$$.

We will call an integer $$$x$$$ interesting if $$$S(x + 1) < S(x)$$$. In each test you will be given one integer $$$n$$$. Your task is to calculate the number of integers $$$x$$$ such that $$$1 \le x \le n$$$ and $$$x$$$ is interesting.

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

Then $$$t$$$ lines follow, the $$$i$$$-th line contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) for the $$$i$$$-th test case.

## Output Format
Print $$$t$$$ integers, the $$$i$$$-th should be the answer for the $$$i$$$-th test case.

## Examples
```input
5
1
9
10
34
880055535
```
```output
0
1
1
3
88005553
```

## Note
The first interesting number is equal to $$$9$$$.

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 are given two strings $$$s$$$ and $$$t$$$, both consisting of lowercase English letters. You are going to type the string $$$s$$$ character by character, from the first character to the last one.

When typing a character, instead of pressing the button corresponding to it, you can press the "Backspace" button. It deletes the last character you have typed among those that aren't deleted yet (or does nothing if there are no characters in the current string). For example, if $$$s$$$ is "abcbd" and you press Backspace instead of typing the first and the fourth characters, you will get the string "bd" (the first press of Backspace deletes no character, and the second press deletes the character 'c'). Another example, if $$$s$$$ is "abcaa" and you press Backspace instead of the last two letters, then the resulting text is "a".

Your task is to determine whether you can obtain the string $$$t$$$, if you type the string $$$s$$$ and press "Backspace" instead of typing several (maybe zero) characters of $$$s$$$.

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

The first line of each test case contains the string $$$s$$$ ($$$1 \le |s| \le 10^5$$$). Each character of $$$s$$$ is a lowercase English letter.

The second line of each test case contains the string $$$t$$$ ($$$1 \le |t| \le 10^5$$$). Each character of $$$t$$$ is a lowercase English letter.

It is guaranteed that the total number of characters in the strings over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print "YES" if you can obtain the string $$$t$$$ by typing the string $$$s$$$ and replacing some characters with presses of "Backspace" button, or "NO" if you cannot.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

## Examples
```input
4
ababa
ba
ababa
bb
aaa
aaaa
aababa
ababa
```
```output
YES
NO
NO
YES
```

## Note
Consider the example test from the statement.

In order to obtain "ba" from "ababa", you may press Backspace instead of typing the first and the fourth characters.

There's no way to obtain "bb" while typing "ababa".

There's no way to obtain "aaaa" while typing "aaa".

In order to obtain "ababa" while typing "aababa", you have to press Backspace instead of typing the first character, then type all the remaining characters.

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

# Problem
You have an array $$$a$$$ consisting of $$$n$$$ distinct positive integers, numbered from $$$1$$$ to $$$n$$$. Define $$$p_k$$$ as $$$$$$p_k = \sum_{1 \le i, j \le k} a_i \bmod a_j,$$$$$$ where $$$x \bmod y$$$ denotes the remainder when $$$x$$$ is divided by $$$y$$$. You have to find and print $$$p_1, p_2, \ldots, p_n$$$.

## Input Format
The first line contains $$$n$$$ — the length of the array ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ space-separated distinct integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^5$$$, $$$a_i \neq a_j$$$ if $$$i \neq j$$$).

## Output Format
Print $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$.

## Examples
```input
4
6 2 7 3
```
```output
0 2 12 22
```
-----
```input
3
3 2 1
```
```output
0 3 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 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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ distinct elements and an integer $$$k$$$. Each element in the array is a non-negative integer not exceeding $$$2^k-1$$$.

Let's define the XOR distance for a number $$$x$$$ as the value of

$$$$$$f(x) = \min\limits_{i = 1}^{n} \min\limits_{j = i + 1}^{n} |(a_i \oplus x) - (a_j \oplus x)|,$$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation.

For every integer $$$x$$$ from $$$0$$$ to $$$2^k-1$$$, you have to calculate $$$f(x)$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le 19$$$; $$$2 \le n \le 2^k$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^k-1$$$). All these integers are distinct.

## Output Format
Print $$$2^k$$$ integers. The $$$i$$$-th of them should be equal to $$$f(i-1)$$$.

## Examples
```input
3 3
6 0 3
```
```output
3 1 1 2 2 1 1 3
```
-----
```input
3 4
13 4 2
```
```output
2 2 6 6 3 1 2 2 2 2 1 3 6 6 2 2
```

## Note
Consider the first example:

- for $$$x = 0$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[6, 0, 3]$$$, and the minimum absolute difference of two elements is $$$3$$$;
- for $$$x = 1$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[7, 1, 2]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 2$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[4, 2, 1]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 3$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[5, 3, 0]$$$, and the minimum absolute difference of two elements is $$$2$$$;
- for $$$x = 4$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[2, 4, 7]$$$, and the minimum absolute difference of two elements is $$$2$$$;
- for $$$x = 5$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[3, 5, 6]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 6$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[0, 6, 5]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 7$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[1, 7, 4]$$$, and the minimum absolute difference of two elements is $$$3$$$.

Now solve the problem and return the code.