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