Пациент был заражен неизвестной болезнью. Его тело представляет собой бесконечную сетку из треугольных ячеек, которая выглядит следующим образом:
Две клетки являются соседними, если у них есть общая сторона. Поэтому у каждой ячейки (\(x\), \(y\)) есть ровно три соседа:
- (\(x+1\), \(y\))
- (\(x-1\), \(y\))
- (\(x+1\), \(y-1\)), если \(x\) четно и (\(x-1\), \(y+1\)) в противном случае.
Изначально некоторые ячейки заражены, все остальные здоровы. Начинается процесс выздоровления. Каждую секунду для ровно одной ячейки (хотя может быть несколько ячеек, которые могут изменить свое состояние) происходит одно из следующих событий:
- Здоровая клетка с по крайней мере \(2\) зараженными соседями становится зараженной.
- Зараженная клетка с по крайней мере \(2\) здоровыми соседями становится здоровой.
Если такой клетки нет, то процесс выздоровления останавливается. Пациент считается выздоровевшим, если процесс выздоровления остановлен и все клетки здоровы.
Нас интересует худший сценарий: возможно ли, что пациент никогда не выздоровеет, или, если это невозможно, какова максимально возможная продолжительность процесса выздоровления?
Выходные данные
Если может случиться так, что организм никогда полностью не выздоровеет после болезни, выведите SICK. В противном случае выведите RECOVERED и в следующей строке целое число \(k\) — максимально возможную продолжительность процесса выздоровления, по модулю \(998244353\).
Примечание
Для первого примера следующие рисунки описывают самый длительный возможный процесс восстановления. Можно доказать, что нет периодов восстановления длиной \(5\) и более, и что организм всегда восстанавливается.
\(\hspace{40pt} \downarrow\) 
\(\hspace{40pt} \downarrow\) 
\(\hspace{40pt} \downarrow\) 
\(\hspace{40pt} \downarrow\)
\(\hspace{15pt}\) RECOVERED
Для второго теста можно заразить клетки \((2, 0)\), \((2, 1)\), \((0, 1)\). После этого ни одна клетка не может изменить свое состояние, поэтому ответ SICK, так как не все клетки здоровы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 0
1 0
2 0
0 1
|
RECOVERED
4
|
|
2
|
3
1 0
3 0
1 1
|
SICK
|