Известная игра «Ультимативные крестики-нолики» проводится на доске 9×99\times 9 (с нумерацией строк и столбцов от 0,1,…,80,1,\ldots,8), мысленно разделенной на девять маленьких досок 3×33\times 3. Игроки обозначаются как «X» и «O» и ходят по очереди, начиная с X.

На каждом ходу игрок выбирает пустую клетку на доске и ставит в нее свой символ. Главное ограничение заключается в том, что, когда это возможно, маленькая доска, на которую игрок ставит свой символ, должна соответствовать клетке, в которую сходил предыдущий игрок. Формально: если игрок делает ход в клетку (x,y)(x,y), то следующий игрок должен выбрать клетку на маленькой доске (x mod 3,y mod 3)(x \text{ mod } 3, y \text{ mod } 3).

Например, предположим, что X делает ход в клетку (4,6)(4,6), то есть в пятую строку и седьмой столбец. Эта клетка является частью средней правой маленькой доски. На этой доске 3×33\times 3 это самая левая клетка в среднем ряду. Следовательно, следующий ход (игрока O) должен быть сделан на средне-левой маленькой доске (в любой свободной клетке этой доски), то есть на доске (1,0)(1, 0).

На любом этапе игры, если игрок делает выигрышный ход (в обычном понимании крестиков-ноликов) на маленькой доске 3×33\times 3, эта доска считается «заблокированной», и ее глобальное значение совпадает с символом победившего игрока. Если маленькая доска полностью заполнена без выявившегося победителя, она также считается «заблокированной», но не имеет глобального значения.

Если маленькая доска, на которой игрок должен сделать ход (согласно описанному ранее правилу), заблокирована, игрок вместо этого может свободно выбрать любую клетку на любой незаблокированной маленькой доске.

Игра считается выигранной, если глобальные значения маленьких досок определены таким образом, что если рассматривать маленькие доски как клетки сетки 3×33\times 3, они оказались заполненными выигрышным образом (в обычном понимании крестиков-ноликов).

Мы можем пронумеровать клетки доски числами 0,1,2,…,800,1,2,\ldots,80, начиная с левой верхней клетки и двигаясь по строкам (так, первая строка — это 0,1,…,80,1,\ldots, 8, вторая — 9,10,…,179,10,\ldots,17 и т.д.). При такой нумерации игру можно описать как последовательность чисел. В качестве примера рассмотрим следующую игру

Заканчивающуюся на доске

где O побеждает по диагонали из маленьких досок.

Абсолютно ультимативные крестики-нолики — это такая игра, в которой:

Игра длится 81 ход (то есть вся доска заполнена);
Последние 9 ходов выигрывают по одной из маленьких досок каждая (никаких ничьих, и ни одна маленькая доска не выигрывается раньше этого моменты);
Последний ход приносит победу в игре.

Обратите внимание, что допускаются ходы, которые мы обычно сочли бы нерациональными (игрок игнорирует возможности выиграть маленькую доску), поскольку цель здесь — выполнить эти три условия, и мы можем считать, что оба игрока, X и O, пытаются сотрудничать для достижения успеха.

Ваша цель: найти абсолютно ультимативные крестики-нолики. Предоставьте свое решение в описанном формате.

Бонус «*» будет присужден за нахождение абсолютно ультимативных крестиков-ноликов для случая 5x5, что означает 25 маленьких досок по 5×55\times 5 клеток каждая, с нумерацией ходов от 0,1,…,6240,1,\ldots,624.