K. Тождество

Это задача с двойным запуском.

Строкой Фибоначчи длины $n$ называется строка из нулей и единиц, в которой нет двух единиц подряд. Их количество обозначим $F_n$; например, $F_3 = 5$: это 000, 001, 010, 100, 101.

Известно тождество

Суммирование идёт, пока верхний индекс не превысит нижний. Докажите его биекцией: сопоставьте каждой строке Фибоначчи длины $n$ сочетание из $n + 1 - k$ элементов по $k$ — и восстановите строку обратно.

При первом запуске в первой строке записано слово first. Во второй — число $n$ ($1 \le n \le 300\,000$). В третьей — строка Фибоначчи длины $n$.

При втором запуске в первой строке записано слово second. Во второй — числа $m$ и $k$, в третьей — сочетание из $k$ элементов; это ровно то, что вы вывели при первом запуске. При $k = 0$ третья строка пустая.

При первом запуске выведите $m$ и $k$ (должно выполняться $m + k = n + 1$), а во второй строке — сочетание из $k$ различных чисел от 1 до $m$ по возрастанию.

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