CF1446E.Long Recovery

A patient has been infected with an unknown disease. His body can be seen as an infinite grid of triangular cells which looks as follows:

Two cells are neighboring if they share a side. Therefore, each cell ($x$, $y$) has exactly three neighbors:

• ($x+1$, $y$)
• ($x-1$, $y$)
• ($x+1$, $y-1$) if $x$ is even and ($x-1$, $y+1$) otherwise.

Initially some cells are infected, all the others are healthy. The process of recovery begins. Each second, for exactly one cell (even though there might be multiple cells that could change its state) one of the following happens:

• A healthy cell with at least $2$ infected neighbors also becomes infected.
• An infected cell with at least $2$ healthy neighbors also becomes healthy.

If no such cell exists, the process of recovery stops. Patient is considered recovered if the process of recovery has stopped and all the cells are healthy.

We're interested in a worst-case scenario: is it possible that the patient never recovers, or if it's not possible, what is the maximum possible duration of the recovery process?

一名患者感染了一种未知疾病。他的身体可被视为一个无限的三角形网格，如下图所示：

若两个格子共享一条边，则称它们为相邻格子。因此，每个格子 $(x, y)$ 恰好有三个相邻格子：

• $(x+1, y)$
• $(x-1, y)$
• 若 $x$ 为偶数，则为 $(x+1, y-1)$；否则为 $(x-1, y+1)$。

初始时，部分格子被感染，其余格子健康。康复过程随即开始。每一秒，恰好有一个格子（尽管可能有多个格子满足状态变更条件）发生以下两种情形之一：

• 一个健康格子，若其至少有 $2$ 个被感染的相邻格子，则也变为被感染；
• 一个被感染格子，若其至少有 $2$ 个健康的相邻格子，则也变为健康。

若不存在满足上述任一条件的格子，则康复过程终止。当康复过程终止且所有格子均为健康时，该患者被视为已康复。

我们关注最坏情况：是否可能存在患者永远无法康复的情形？若不可能，则康复过程的最大可能持续时间是多少？

The first line contains one integer $n$ $(1 \leq n \leq 250000)$ — the number of infected cells.

The $i$-th of the next $n$ lines contains two space-separated integers $x_i$ and $y_i$ $(0 \leq x_i, y_i \lt 500)$, meaning that cell $(x_i, y_i)$ is infected. All cells $(x_i, y_i)$ are distinct, and all other cells are considered healthy.

第一行包含一个整数 $n$ $(1 \leq n \leq 250000)$ —— 表示被感染的细胞数量。

接下来的 $n$ 行中，第 $i$ 行包含两个用空格分隔的整数 $x_i$ 和 $y_i$ $(0 \leq x_i, y_i \lt 500)$，表示细胞 $(x_i, y_i)$ 被感染。所有细胞 $(x_i, y_i)$ 互不相同，其余所有细胞均视为健康。

If it is possible that the organism never fully recovers from the disease, print SICK. Otherwise, you should print RECOVERED and in the next line an integer $k$ — the longest possible recovery period, modulo $998244353$.

如果该生物可能永远无法从疾病中完全康复，则输出 SICK。否则，应输出 RECOVERED，并在下一行输出一个整数 $k$ —— 最长可能的康复期，对 $998244353$ 取模。

For the first testcase, the following drawings describe the longest possible recovery process. It can be proven that there are no recovery periods of length $5$ or longer, and the organism always recovers in this testcase.

$\hspace{40pt} \downarrow$ $\hspace{40pt} \downarrow$ $\hspace{40pt} \downarrow$ $\hspace{40pt} \downarrow$

$\hspace{15pt}$ RECOVERED

For the second testcase, it is possible for the cells $(2, 0)$, $(2, 1)$, $(0, 1)$ to become infected. After that, no cell can change its state, so the answer is SICK, as not all of the cells are healthy.

对于第一个测试用例，以下图示描述了可能的最长恢复过程。可以证明，不存在长度为 $5$ 或更长的恢复期，且该测试用例中的生物体总能完全恢复。

$\hspace{40pt} \downarrow$ $\hspace{40pt} \downarrow$ $\hspace{40pt} \downarrow$ $\hspace{40pt} \downarrow$

$\hspace{15pt}$ 已恢复

对于第二个测试用例，细胞 $(2, 0)$、$(2, 1)$、$(0, 1)$ 可能被感染。此后，没有任何细胞能够改变其状态，因此答案为“患病”，因为并非所有细胞都处于健康状态。