Козак Вус і програмування

Усім відомо, що у Козака є його улюблений робот Атлас, з яким він багато грався у дитинстві. Сьогодні Вус зрозумів, що ще ніколи не намагався запрограмувати робота на якісь інші дії, і тому почав читати інструкцію. З'ясувалося, що у пам'яті Атласа зберігаються $40$ пронумерованих з одиниці регістрів, кожний із яких містить $64$ біти. Це означає, що кожен регістр складається з $64$-ох нулів та одиниць:

Вус також зрозумів, що для програмування робота можна використовувати наступні $7$ команд, які виконують операції над регістрами. Для зручності будемо регістром $i$ називати регістр під номером $i$, а також $a_i$ "— число, яке записане в $i$-му регістрі

1. setValue(i, j) "— замінити регістр $i$ на регістр $j$. Тобто кожен біт першого регістра замінити на відповідний біт у другому регістрі. Іншими словами, виконати операцію присвоєння $a_i=a_j$.

2. setXor(i, j, k) "— замінити регістр $i$ на побітовий xor регістрів $j$ та $k$. Тобто кожен біт регістра $i$ замінити на xor відповідних бітів у регістрів $j$ та $k$. Про операцію xor буде зазначено нижче.

3. setAnd(i, j, k) "— замінити регістр $i$ на побітовий and регістрів $j$ та $k$. Тобто кожен біт регістра $i$ замінити на and відповідних бітів у регістрів $j$ та $k$. Про операцію and буде зазначено нижче.

4. setOr(i, j, k) "— замінити регістр $i$ на побітовий or регістрів $j$ та $k$. Тобто кожен біт регістра $i$ замінити на or відповідних бітів у регістрів $j$ та $k$. Про операцію or буде зазначено нижче.

5. shiftLeft(i, x) "— зсунути всі біти регістру $i$ на $x$ позицій вліво. Про операцію зсуву буде зазначено нижче.

6. shiftRight(i, x) "— зсунути всі біти регістру $i$ на $x$ позицій вправо. Про операцію зсуву буде зазначено нижче.

7. setNot(i, j) "— замінити регістр $i$ на інвертований регістр $j$. Тобто кожен біт регістра $i$ замінити на $1$, якщо на відповідній позиції регістра $j$ записане $0$, і замінити на $0$, якщо на відповідній позиції регістра $j$ записане $1$.

Результатом операції xor двох бітів є $0$, якщо біти однакові, та $1$, якщо різні.

Результатом операції and двох бітів є $1$, якщо обидва біти є рівними $1$, та $0$, якщо хоча б один біт рівний $0$.

Результатом операції or двох бітів є $0$, якщо обидва біти є рівними $0$, та $1$, якщо хоча б один біт рівний $1$.

Результатом операції зсув регістру на $x$ позицій уліво є регістр, у якому кожний біт рівний біту, що був записаний у початковому регістрі на $x$ позицій правіше, та рівний $0$, якщо не існувало у початковому регістрі позиції на $x$ правіше.

Результатом операції зсув регістру на $x$ позицій управо є регістр, у якому кожний біт рівний біту, що був записаний у початковому регістрі на $x$ позицій лівіше, та рівний $0$, якщо не існувало у початковому регістрі позиції на $x$ лівіше.

Прочитавши інструкцію, Козак Вус одразу ж придумав $6$ досить цікавих задач. Ще трохи подумавши, Козак зрозумів, що для того, щоб запрограмувати робота на конкретну задачу, потрібно лише ввести роботу набір команд, який би вирішував цю задачу. Припустимо, що $t$ "— кількість команд, яку ви виконали в певній задачі.

А ось і самі задачі:

Підзадача 1: (до $6$ балів) у регістрі $1$ записане число $x$. Усі інші регістри повністю складаються з $0$-ів. Нехай число $y$ дорівнює $1$, якщо число $x$ парне, і дорівнює $0$, якщо $x$ непарне. Задача полягає в тому, щоб після виконання роботом операцій у регістрі $2$ було записане число $y$. Ви отримаєте $\lfloor 6-\sqrt[3]{t-\min (3,t)}\rfloor$ балів.

Підзадача 2: (до $10$ балів) у регістрі $1$ записане $x$, а в регістрі $2$ записане $y$. Усі інші регістри повністю складаються з $0$-ів. Нехай $z=x+y$. Задача полягає в тому, щоб після виконання роботом операцій у регістрі $3$ було записане число $z$. Потрібно зазначити, що якщо двійковий запис числа $z$ потребує більше ніж $64$ розряди, то в регістрі $3$ мають бути записані лише перші $64$ розряди. Ви отримаєте $\lfloor 10-\sqrt[3]{t-\min (260,t)}\rfloor$ балів.

Підзадача 3: (до $13$ балів) у регістрі $1$ записане $x$. Нехай число $y$ "— це кількість одиниць у двійковому записі числа $x$. Тоді після виконання роботом операцій у регістрі $2$ має бути записане $y$. Ви отримаєте $\lfloor 13-\log (t-\min (1505,t)+1)\rfloor$ балів.

Підзадача 4: (до $23$ балів) у регістрах $1$ та $2$ записані два різні числа $x$ та $y$ відповідно. Нехай якщо $x>y$, то $a=0,b=1$, а якщо $y>x$, то $b=0,a=1$. Задача полягає в тому, щоб після виконання роботом операцій у регістрах $3$ та $4$ були записані числа $a$ та $b$ відповідно. Ви отримаєте $\lfloor 23-\sqrt[2.5]{t-\min (92,t)}\rfloor$ балів.

Підзадача 5: (до $18$ балів) у регістрі $1$ записане число $x$. Нехай число $y$ "— це кількість одиниць у двійковому записі числа $x$. Тоді після виконання роботом операцій у регістрі $1$ має бути записане число $2^y-1$. Ви отримаєте $\lfloor 18-\sqrt[4]{t-\min (6560,t)}\rfloor$ балів.

Підзадача 6: (до $30$ балів) нехай $a$ "— це масив, який містить $9$ невід'ємних цілих попарно різних чисел. Тоді для кожного $i$ від $1$-ого до $9$-и у $i$-ому регістрі записане $a_i$. Нехай $b$ "— це відсортований за зростанням масив $a$. Тоді після виконання роботом операцій, для кожного $i$ від $1$-ого до $9$-и у $i$-ому регістрі має бути записане $b_i$. Потрібно зазначити, що нумерація у масивах $a$ та $b$ починається з одиниці. Ви отримаєте $\lfloor 30-\sqrt[3]{t-\min (4644,t)}\rfloor$ балів.

Якщо про початкове значення регістру нічого не сказано, тоді на початку він повністю складається з нулів. Усі числа від $0$ до $2^{64}-1$.

Козак Вус якимось чином дізнався кількість команд, яка необхідна для вирішення кожної задачі, проте він ще не знає, які саме команди потрібно використати, і тому звернувся по допомогу до вас. Він просить вас знайти таку послідовність команд, яка розв'яже задачу для будь-яких можливих вхідних даних.

Зверніть увагу, що ви можете виконати не більше $10^5$ команд. Якщо ви виконаєте більше, то ви отримаєте $0$ балів та вердикт Неправильна відповідь. Якщо ви виконаєте неправильний запит, то ви отримаєте $0$ балів та вердикт Помилка виконання. Результатом вашого рішення в кожній підзадачі будуть ті регістри, у яких мають бути записані рішення. В усіх інших регістрах можуть бути будь-які числа.

Протокол взаємодії

Для кожної підзадачі вам потрібно окремо реалізувати одну функцію:

void solve()

• ця функція не приймає ніяких параметрів та нічого не повертає.

Ви можете використовувати наступні функції:

void setValue(integer i, integer j)

• ця функція надає регістру $i$ ($1\le i\le 40$) значення регістра $j$ ($1\le j\le 40$).

void setXor(integer i, integer j, integer k)

• ця функція надає регістру $i$ ($1\le i\le 40$) значення операції xor регістрів $j$ ($1\le j\le 40$) та $k$ ($1\le k\le 40$).

void setAnd(integer i, integer j, integer k)

• ця функція надає регістру $i$ ($1\le i\le 40$) значення операції and регістрів $j$ ($1\le j\le 40$) та $k$ ($1\le k\le 40$).

void setOr(integer i, integer j, integer k)

• ця функція надає регістру $i$ ($1\le i\le 40$) значення операції or регістрів $j$ ($1\le j\le 40$) та $k$ ($1\le k\le 40$).

void shiftLeft(integer i, integer x)

• ця функція реалізовує зсув регістру $i$ ($1\le i\le 40$) на $x$ ($0\le x\le 64$) позицій уліво.

void shiftRight(integer i, integer x)

• ця функція реалізовує зсув регістру $i$ ($1\le i\le 40$) на $x$ ($0\le x\le 64$) позицій управо.

void setNot(integer i, integer j)

• ця функція надає регістру $i$ ($1\le i\le 40$) значення інвертованого регістру $j$ ($1\le j\le 40$).

Приклади

Припустимо, що в регістрі $1$ записане число $6$, а в регістрі $2$ число $3$, тоді якщо виконаємо такі команди:

setValue(3, 1)
setXor(4, 1, 2)
setAnd(5, 1, 2)
setOr(6, 2, 1)
shiftLeft(2, 3)
shiftRight(1, 2)
setNot(7, 2)

то перші сім чисел масиву будуть виглядати так: $[1$, $24$, $6$, $5$, $2$, $7$, $18446744073709551591]$.