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

# Problem
ВКонтакте открыла второй штаб в Санкт-Петербурге! Вы не преминули возможностью сменить обстановку и решили переехать из офиса в Доме Зингера в офис на Красном мосту.

Для комфортной работы вам потребуются два монитора с одинаковой высотой, чтобы изображение на них выглядело единым целым. На складе офиса на Красном мосту есть $$$n$$$ мониторов, $$$i$$$-й из них имеет ширину $$$w_i$$$ и высоту $$$h_i$$$. Любой монитор можно повернуть на 90 градусов, и тогда он будет иметь ширину $$$h_i$$$ и высоту $$$w_i$$$.

Назовём неупорядоченную пару из двух различных мониторов подходящей, если можно их повернуть так, чтобы они имели одинаковую высоту. Любой из мониторов в паре можно как повернуть относительно исходной ориентации, так и не поворачивать.

Подсчитайте подходящие пары мониторов.

## Input Format
В первой строке задано одно целое число $$$n$$$ — число мониторов на складе.

В каждой из следующих $$$n$$$ строк заданы два целых числа $$$w_i$$$ и $$$h_i$$$ ($$$1 \le w_i, h_i \le 10^9$$$) — ширина и высота $$$i$$$-го монитора. Обратите внимание, что мониторы могут быть квадратными ($$$w_i = h_i$$$), а размеры разных мониторов могут совпадать.

В этой версии задачи $$$2 \le n \le 10^3$$$.

## Output Format
Выведите число подходящих пар мониторов.

## Examples
```input
5
3 2
2 2
5 5
3 5
4 3
```
```output
5
```
-----
```input
7
10 10
10 20
20 10
10 20
10 20
10 10
20 10
```
```output
21
```

## Note
В первом примере подходящими являются пары мониторов с номерами $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(3, 4)$$$, $$$(4, 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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
ВКонтакте открыла второй штаб в Санкт-Петербурге! Вы не преминули возможностью сменить обстановку и решили переехать из офиса в Доме Зингера в офис на Красном мосту.

Для комфортной работы вам потребуются два монитора с одинаковой высотой, чтобы изображение на них выглядело единым целым. На складе офиса на Красном мосту есть $$$n$$$ мониторов, $$$i$$$-й из них имеет ширину $$$w_i$$$ и высоту $$$h_i$$$. Любой монитор можно повернуть на 90 градусов, и тогда он будет иметь ширину $$$h_i$$$ и высоту $$$w_i$$$.

Назовём неупорядоченную пару из двух различных мониторов подходящей, если можно их повернуть так, чтобы они имели одинаковую высоту. Любой из мониторов в паре можно как повернуть относительно исходной ориентации, так и не поворачивать.

Подсчитайте подходящие пары мониторов.

## Input Format
В первой строке задано одно целое число $$$n$$$ — число мониторов на складе.

В каждой из следующих $$$n$$$ строк заданы два целых числа $$$w_i$$$ и $$$h_i$$$ ($$$1 \le w_i, h_i \le 10^9$$$) — ширина и высота $$$i$$$-го монитора. Обратите внимание, что мониторы могут быть квадратными ($$$w_i = h_i$$$), а размеры разных мониторов могут совпадать.

В этой версии задачи $$$2 \le n \le 10^5$$$.

## Output Format
Выведите число подходящих пар мониторов.

## Examples
```input
5
3 2
2 2
5 5
3 5
4 3
```
```output
5
```
-----
```input
7
10 10
10 20
20 10
10 20
10 20
10 10
20 10
```
```output
21
```

## Note
В первом примере подходящими являются пары мониторов с номерами $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(3, 4)$$$, $$$(4, 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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Все готовятся к VK Fest 2021! Для того, чтобы зрителям была лучше видна главная сцена, планируется построить амфитеатр. В этой задаче мы будем рассматривать его сбоку — схематично он будет иметь форму лестницы из $$$n$$$ одинаковых квадратов. Лестница — это одна или более башен квадратов, выстроенных в ряд, где высоты башен невозрастают слева направо.

На следующем рисунке можно видеть три разные фигуры из $$$12$$$ квадратов. Первые две фигуры — лестницы, а третья — нет.

Из эстетических соображений было решено, что амфитеатр должен быть симметричным. Формально, амфитеатр называется симметричным, если при отражении его схемы относительно прямой $$$x = y$$$ получается тот же самый рисунок (где ось $$$x$$$ направлена слева направо, а ось $$$y$$$ — снизу вверх). Например, первая лестница на рисунке выше — симметричная, а вторая — нет.

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

По заданному числу $$$n$$$ нарисуйте схему амфитеатра из ровно $$$n$$$ квадратов, удовлетворяющую всем условиям.

## Input Format
В единственной строке задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — число квадратов, из которых нужно составить схему амфитеатра.

## Output Format
Если не существует схемы амфитеатра из $$$n$$$ квадратов, выведите единственное число $$$-1$$$.

Иначе в первой строке выведите целое число $$$m$$$ — минимальное возможное число строк и столбцов в схеме амфитеатра. Далее выведите $$$m$$$ строк, описывающих схему. Каждая строка должна содержать ровно $$$m$$$ символов 'o' (строчная латинская буква) или '.', где 'o' описывает построенный квадрат, а '.' — пустое место. Схема амфитеатра должна состоять ровно из $$$n$$$ символов 'o'. Ячейка в левом нижнем углу должна содержать квадрат. Если возможных ответов с минимальным $$$m$$$ несколько, выведите любой из них.

## Examples
```input
3
```
```output
2
o.
oo
```
-----
```input
17
```
```output
5
o....
ooo..
oooo.
oooo.
ooooo
```

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

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

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

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

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

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

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

## 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 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: 512.0 MB

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

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

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

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

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

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

## 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 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: 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 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: 512.0 MB

# Problem
A string $$$s$$$ of length $$$n$$$ ($$$1 \le n \le 26$$$) is called alphabetical if it can be obtained using the following algorithm:

- first, write an empty string to $$$s$$$ (i.e. perform the assignment $$$s$$$ := "");
- then perform the next step $$$n$$$ times;
- at the $$$i$$$-th step take $$$i$$$-th lowercase letter of the Latin alphabet and write it either to the left of the string $$$s$$$ or to the right of the string $$$s$$$ (i.e. perform the assignment $$$s$$$ := $$$c+s$$$ or $$$s$$$ := $$$s+c$$$, where $$$c$$$ is the $$$i$$$-th letter of the Latin alphabet).

In other words, iterate over the $$$n$$$ first letters of the Latin alphabet starting from 'a' and etc. Each time we prepend a letter to the left of the string $$$s$$$ or append a letter to the right of the string $$$s$$$. Strings that can be obtained in that way are alphabetical.

For example, the following strings are alphabetical: "a", "ba", "ab", "bac" and "ihfcbadeg". The following strings are not alphabetical: "z", "aa", "ca", "acb", "xyz" and "ddcba".

From the given string, determine if it is alphabetical.

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

Each test case is written on a separate line that contains one string $$$s$$$. String $$$s$$$ consists of lowercase letters of the Latin alphabet and has a length between $$$1$$$ and $$$26$$$, inclusive.

## Output Format
Output $$$t$$$ lines, each of them must contain the answer to the corresponding test case. Output YES if the given string $$$s$$$ is alphabetical and NO otherwise.

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

## Examples
```input
11
a
ba
ab
bac
ihfcbadeg
z
aa
ca
acb
xyz
ddcba
```
```output
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
```

## Note
The example contains test cases from the main part of 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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array of positive integers $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ ($$$n \ge 2$$$).

In one step, the array $$$a$$$ is replaced with another array of length $$$n$$$, in which each element is the greatest common divisor (GCD) of two neighboring elements (the element itself and its right neighbor; consider that the right neighbor of the $$$(n - 1)$$$-th element is the $$$0$$$-th element).

Formally speaking, a new array $$$b = [b_0, b_1, \dots, b_{n - 1}]$$$ is being built from array $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ such that $$$b_i$$$ $$$= \gcd(a_i, a_{(i + 1) \mod n})$$$, where $$$\gcd(x, y)$$$ is the greatest common divisor of $$$x$$$ and $$$y$$$, and $$$x \mod y$$$ is the remainder of $$$x$$$ dividing by $$$y$$$. In one step the array $$$b$$$ is built and then the array $$$a$$$ is replaced with $$$b$$$ (that is, the assignment $$$a$$$ := $$$b$$$ is taking place).

For example, if $$$a = [16, 24, 10, 5]$$$ then $$$b = [\gcd(16, 24)$$$, $$$\gcd(24, 10)$$$, $$$\gcd(10, 5)$$$, $$$\gcd(5, 16)]$$$ $$$= [8, 2, 5, 1]$$$. Thus, after one step the array $$$a = [16, 24, 10, 5]$$$ will be equal to $$$[8, 2, 5, 1]$$$.

For a given array $$$a$$$, find the minimum number of steps after which all values $$$a_i$$$ become equal (that is, $$$a_0 = a_1 = \dots = a_{n - 1}$$$). If the original array $$$a$$$ consists of identical elements then consider the number of steps is equal to $$$0$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

Each test case contains two lines. The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — length of the sequence $$$a$$$. The second line contains $$$n$$$ integers $$$a_0, a_1, \dots, a_{n - 1}$$$ ($$$1 \le a_i \le 10^6$$$).

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

## Output Format
Print $$$t$$$ numbers — answers for each test case.

## Examples
```input
5
4
16 24 10 5
4
42 42 42 42
3
4 6 4
5
1 2 3 4 5
6
9 9 27 9 9 63
```
```output
3
0
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 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
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 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 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.