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
There are $$$n$$$ coins labeled from $$$1$$$ to $$$n$$$. Initially, coin $$$c_i$$$ is on position $$$i$$$ and is facing upwards (($$$c_1, c_2, \dots, c_n)$$$ is a permutation of numbers from $$$1$$$ to $$$n$$$). You can do some operations on these coins.

In one operation, you can do the following:

- Choose $$$2$$$ distinct indices $$$i$$$ and $$$j$$$.
- Then, swap the coins on positions $$$i$$$ and $$$j$$$.
- Then, flip both coins on positions $$$i$$$ and $$$j$$$. (If they are initially faced up, they will be faced down after the operation and vice versa)

Construct a sequence of at most $$$n+1$$$ operations such that after performing all these operations the coin $$$i$$$ will be on position $$$i$$$ at the end, facing up.

Note that you do not need to minimize the number of operations.

## Input Format
The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the number of coins.

The second line contains $$$n$$$ integers $$$c_1,c_2,\dots,c_n$$$ ($$$1 \le c_i \le n$$$, $$$c_i \neq c_j$$$ for $$$i\neq j$$$).

## Output Format
In the first line, output an integer $$$q$$$ $$$(0 \leq q \leq n+1)$$$ — the number of operations you used.

In the following $$$q$$$ lines, output two integers $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq n, i \ne j)$$$ — the positions you chose for the current operation.

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

## Note
Let coin $$$i$$$ facing upwards be denoted as $$$i$$$ and coin $$$i$$$ facing downwards be denoted as $$$-i$$$.

The series of moves performed in the first sample changes the coins as such:

- $$$[~~~2,~~~1,~~~3]$$$
- $$$[-3,~~~1,-2]$$$
- $$$[-3,~~~2,-1]$$$
- $$$[~~~1,~~~2,~~~3]$$$

In the second sample, the coins are already in their correct positions so there is no need to swap.

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

# Problem
Yuezheng Ling gives Luo Tianyi a tree which has $$$n$$$ nodes, rooted at $$$1$$$.

Luo Tianyi will tell you that the parent of the $$$i$$$-th node is $$$a_i$$$ ($$$1 \leq a_i<i$$$ for $$$2 \le i \le n$$$), and she will ask you to perform $$$q$$$ queries of $$$2$$$ types:

1. She'll give you three integers $$$l$$$, $$$r$$$ and $$$x$$$ ($$$2 \le l \le r \le n$$$, $$$1 \le x \le 10^5$$$). You need to replace $$$a_i$$$ with $$$\max(a_i-x,1)$$$ for all $$$i$$$ with $$$l \leq i \leq r$$$.
2. She'll give you two integers $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$). You need to find the LCA of nodes $$$u$$$ and $$$v$$$ (their lowest common ancestor).

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2\leq n,q \leq 10^5$$$) — the number of nodes and the number of queries, respectively.

The second line contains $$$n-1$$$ integers $$$a_2, a_3,\dots, a_n$$$ ($$$1 \le a_i < i$$$), where $$$a_i$$$ is the parent of the node $$$i$$$.

Next $$$q$$$ lines contain queries. For each query, the first integer of each line is $$$t$$$ ($$$t = 1$$$ or $$$2$$$) — the type of the query.

If $$$t = 1$$$, this represents the query of the first type. Then, three integers will follow: $$$l$$$, $$$r$$$, $$$x$$$ ($$$2 \le l \le r \le n$$$, $$$1 \le x \le 10^5$$$), meaning that you have to replace $$$a_i$$$ with $$$\max(a_i-x,1)$$$ for all $$$i$$$ with $$$l \leq i \leq r$$$.

If $$$t = 2$$$, this represents the query of the second type. Then, two integers will follow: $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), and you have to find the LCA of $$$u$$$ and $$$v$$$.

It's guaranteed that there is at least one query of the second type.

## Output Format
For each query of the second type output answer on a new line.

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

## Note
The tree in example is shown below.

After the query of the first type, the tree changes and is looking as shown below.

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

# Problem
In the house where Krosh used to live, he had $$$n$$$ cupboards standing in a line, the $$$i$$$-th cupboard had the height of $$$h_i$$$. Krosh moved recently, but he wasn't able to move the cupboards with him. Now he wants to buy $$$n$$$ new cupboards so that they look as similar to old ones as possible.

Krosh does not remember the exact heights of the cupboards, but for every three consecutive cupboards he remembers the height difference between the tallest and the shortest of them. In other words, if the cupboards' heights were $$$h_1, h_2, \ldots, h_n$$$, then Krosh remembers the values $$$w_i = \max(h_{i}, h_{i + 1}, h_{i + 2}) - \min(h_{i}, h_{i + 1}, h_{i + 2})$$$ for all $$$1 \leq i \leq n - 2$$$.

Krosh wants to buy such $$$n$$$ cupboards that all the values $$$w_i$$$ remain the same. Help him determine the required cupboards' heights, or determine that he remembers something incorrectly and there is no suitable sequence of heights.

## Input Format
The first line contains two integers $$$n$$$ and $$$C$$$ ($$$3 \leq n \leq 10^6$$$, $$$0 \leq C \leq 10^{12}$$$) — the number of cupboards and the limit on possible $$$w_i$$$.

The second line contains $$$n - 2$$$ integers $$$w_1, w_2, \ldots, w_{n - 2}$$$ ($$$0 \leq w_i \leq C$$$) — the values defined in the statement.

## Output Format
If there is no suitable sequence of $$$n$$$ cupboards, print "NO".

Otherwise print "YES" in the first line, then in the second line print $$$n$$$ integers $$$h'_1, h'_2, \ldots, h'_n$$$ ($$$0 \le h'_i \le 10^{18}$$$) — the heights of the cupboards to buy, from left to right.

We can show that if there is a solution, there is also a solution satisfying the constraints on heights.

If there are multiple answers, print any.

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

## Note
Consider the first example:

- $$$w_1 = \max(4, 8, 8) - \min(4, 8, 8) = 8 - 4 = 4$$$
- $$$w_2 = \max(8, 8, 16) - \min(8, 8, 16) = 16 - 8 = 8$$$
- $$$w_3 = \max(8, 16, 20) - \min(8, 16, 20) = 20 - 8 = 12$$$
- $$$w_4 = \max(16, 20, 4) - \min(16, 20, 4) = 20 - 4 = 16$$$
- $$$w_5 = \max(20, 4, 0) - \min(20, 4, 0) = 20 - 0 = 20$$$

There are other possible solutions, for example, the following: $$$0, 1, 4, 9, 16, 25, 36$$$.

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
A sequence $$$(b_1, b_2, \ldots, b_k)$$$ is called strange, if the absolute difference between any pair of its elements is greater than or equal to the maximum element in the sequence. Formally speaking, it's strange if for every pair $$$(i, j)$$$ with $$$1 \le i<j \le k$$$, we have $$$|a_i-a_j|\geq MAX$$$, where $$$MAX$$$ is the largest element of the sequence. In particular, any sequence of length at most $$$1$$$ is strange.

For example, the sequences $$$(-2021, -1, -1, -1)$$$ and $$$(-1, 0, 1)$$$ are strange, but $$$(3, 0, 1)$$$ is not, because $$$|0 - 1| < 3$$$.

Sifid has an array $$$a$$$ of $$$n$$$ integers. Sifid likes everything big, so among all the strange subsequences of $$$a$$$, he wants to find the length of the longest one. Can you help him?

A sequence $$$c$$$ is a subsequence of an array $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by deletion of several (possibly, zero or all) elements.

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

The first line of each test case contains an integer $$$n$$$ $$$(1\le n\le 10^5)$$$ — the length of the array $$$a$$$.

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

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

## Output Format
For each test case output a single integer — the length of the longest strange subsequence of $$$a$$$.

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

## Note
In the first test case, one of the longest strange subsequences is $$$(a_1, a_2, a_3, a_4)$$$

In the second test case, one of the longest strange subsequences is $$$(a_1, a_3, a_4, a_5, a_7)$$$.

In the third test case, one of the longest strange subsequences is $$$(a_1, a_3, a_4, a_5)$$$.

In the fourth test case, one of the longest strange subsequences is $$$(a_2)$$$.

In the fifth test case, one of the longest strange subsequences is $$$(a_1, a_2, a_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: 512.0 MB

# Problem
Немногие знают, что сотрудники ВКонтакте могут менять цвет подсветки в куполе знаменитого Дома Зингера, где расположена штаб-квартира ВКонтакте. Для этого нужно всего лишь отправить сообщение с цветом в специальный чат «Зингер | color», а бот его распознает и сменит подсветку. При этом на время городских мероприятий смена цвета блокируется.

Формально, бот обрабатывает три типа сообщений:

- lock: заблокировать изменение цвета. Если оно и так заблокировано на данный момент, сообщение игнорируется.
- unlock: разблокировать изменение цвета. Если оно и так разблокировано на данный момент, сообщение игнорируется.
- red / orange / yellow / green / blue / indigo / violet: изменить цвет купола на заданный, если изменение цвета на данный момент не заблокировано.

Вам дана история сообщений, полученных ботом, в хронологическом порядке. Считайте, что перед получением первого сообщения купол подсвечивается голубым (blue), а изменение цвета не заблокировано.

Определите, какой цвет будет у купола Дома Зингера после обработки этих сообщений.

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

В следующих $$$n$$$ строках заданы сообщения, полученные ботом, в хронологическом порядке, по одному сообщению в строке. Каждое сообщение — строка из следующего набора: lock, unlock, red, orange, yellow, green, blue, indigo, violet.

## Output Format
Выведите цвет купола после обработки сообщений ботом.

## Examples
```input
7
red
violet
unlock
red
orange
lock
indigo
```
```output
orange
```
-----
```input
5
lock
unlock
lock
unlock
unlock
```
```output
blue
```

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: 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 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
ВКонтакте открыла второй штаб в Санкт-Петербурге! Вы не преминули возможностью сменить обстановку и решили переехать из офиса в Доме Зингера в офис на Красном мосту.

Для комфортной работы вам потребуются два монитора с одинаковой высотой, чтобы изображение на них выглядело единым целым. На складе офиса на Красном мосту есть $$$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 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
Все готовятся к 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 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.

В этой версии задачи для любого теста существует перестановка длины $$$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 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^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.