AT_arc226_e.Cellular Messenger

Snuke wants to design a cellular automaton that conveys a binary sequence, written into a certain cell over $N$ turns, to a distant cell.

1. Grid

There is an infinitely large grid. Each cell has a state of $0$ or $1$.

Let some row of the grid be row $0$ and some column be column $0$, with row numbers increasing by $1$ downward and column numbers increasing by $1$ to the right. Let $(r,c)$ denote the coordinates of the cell at row $r$ and column $c$. The coordinates of the cells are as shown in the figure below.

The cells adjacent to a given cell refer to the eight cells sharing an edge or a vertex with it.

You may choose a rectangular region satisfying the following conditions, and freely set the initial states of the cells within the region.

• Both the height $H$ and the width $W$ are between $1$ and $150$, inclusive.
• The coordinates of the top-left cell are $(0,0)$.

The initial states of all cells outside the region are $0$.

2. Update Operation

Decide on a value $F_{i,j}$, either $0$ or $1$, for each $i=0,1$ and $j=0,1,\ldots,8$; let these values be the update rule. However, $F_{0,0}=0$ must hold.

In the update operation, the states of all cells are updated simultaneously. For a given cell, let $i$ be its state before the update and $j$ be the sum of the states of the eight adjacent cells; then its state after the update is $F_{i,j}$.

3. Designing the Automaton

You need to decide on and output the following values.

• The update rule $F_{i,j}$ $(i=0,1)$ $(0 \le j \le 8)$
  • $F_{0,0}=0$ must hold.
• The height $H$ and width $W$ of the rectangular region for which the initial state is set
  • Both $H$ and $W$ must be between $1$ and $150$, inclusive.
• The initial states $A_{r,c}$ $(0 \le r \lt H)$ $(0 \le c \lt W)$ within the rectangular region
• The coordinates $(R_s,C_s)$ of the sending cell and $(R_t,C_t)$ of the receiving cell
  • $0 \le R_s,R_t \lt H$ and $0 \le C_s,C_t \lt W$ must hold.
  • $50 \le |C_s-C_t| \le 100$ must hold.
• The delay $D$ from sending to receiving
  • It must be possible to read, at the receiving cell on turn $k+D-1$, the value that was written to the sending cell on turn $k$.
  • $50 \le D \le 100$ must hold.

4. Judging Method

Judging is performed as follows.

1. Decide on a positive integer $N$ and a sequence $S=(S_1,S_2, \ldots ,S_N)$ of length $N$ consisting of $0$s and $1$s. These are fixed for each test case.

2. Receive the design of the automaton that you output.

3. Prepare an empty sequence $T$, and simulate $N+D-1$ turns starting from the initial state. Specifically, for each $k=1,2,\ldots,N+D-1$, perform the following steps in order on turn $k$.

   1. If $k \le N$, change the state of the sending cell $(R_s,C_s)$ to $S_k$.
   2. Perform one update operation on the grid.
   3. If $D \le k < D+N$, append the state of the receiving cell $(R_t,C_t)$ to the end of $T$.

4. After the simulation ends, if $S=T$, your output is judged correct; otherwise, it is judged incorrect.

It is guaranteed that there exists a design of the automaton that is judged correct regardless of $N$ and $S$, but due to implementation details of the judge for this problem, $N$ and $S$ are fixed for each test case file, and only cases with $N \le 300$ are used.

すぬけさんは、$N$ ターンにわたってある特定のセルに書き込まれた 0/1 の列を、遠く離れた別のセルへと伝達するセルオートマトンを設計したいと考えています。

1．グリッド

無限に広いグリッドが存在します。各セルの状態は $0$ または $1$ のいずれかです。

グリッドの適当な行を「行 $0$」、適当な列を「列 $0$」とし、行番号は下方向に $1$ ずつ増加し、列番号は右方向に $1$ ずつ増加するものとします。$(r,c)$ は、行 $r$、列 $c$ にあるセルの座標を表します。セルの座標は以下の図の通りです。

あるセルの「隣接セル」とは、そのセルと辺または頂点を共有する 8 個のセルを指します。

以下の条件を満たす長方形領域を自由に選び、その領域内のセルの初期状態を任意に設定できます。

• 高さ $H$ および幅 $W$ はともに $1$ 以上 $150$ 以下（両端含む）である。
• 左上角のセルの座標は $(0,0)$ である。

領域外のすべてのセルの初期状態は $0$ です。

2．更新操作

各 $i=0,1$ および $j=0,1,\ldots,8$ に対して値 $F_{i,j} \in \{0,1\}$ を定め、これを更新規則と呼びます。ただし、$F_{0,0}=0$ でなければなりません。

更新操作では、すべてのセルの状態が同時に更新されます。あるセルについて、更新前の状態を $i$、その 8 個の隣接セルの状態の和を $j$ とするとき、更新後の状態は $F_{i,j}$ となります。

3．オートマトンの設計

以下の値を決定し、出力する必要があります。

• 更新規則 $F_{i,j}$（$i=0,1$，$0 \le j \le 8$）
  • $F_{0,0}=0$ を満たさなければならない。
• 初期状態を設定する長方形領域の高さ $H$ および幅 $W$
  • $H$ および $W$ はともに $1$ 以上 $150$ 以下（両端含む）でなければならない。
• 長方形領域内の初期状態 $A_{r,c}$（$0 \le r \lt H$，$0 \le c \lt W$）
• 送信セルの座標 $(R_s,C_s)$ および 受信セルの座標 $(R_t,C_t)$
  • $0 \le R_s,R_t \lt H$ かつ $0 \le C_s,C_t \lt W$ を満たさなければならない。
  • $50 \le |C_s-C_t| \le 100$ を満たさなければならない。
• 送信から受信までの遅延 $D$
  • ターン $k$ に送信セル $(R_s,C_s)$ に書き込まれた値が、ターン $k+D-1$ に受信セル $(R_t,C_t)$ で読み取れることを保証しなければならない。
  • $50 \le D \le 100$ を満たさなければならない。

4．判定方法

判定は以下のように行われます。

1. 正の整数 $N$ および長さ $N$ の 0/1 列 $S=(S_1,S_2, \ldots ,S_N)$ を決定します。これらは各テストケースごとに固定されます。

2. あなたが出力したオートマトンの設計を受け取ります。

3. 空の列 $T$ を用意し、初期状態から $N+D-1$ ターンのシミュレーションを行います。具体的には、各 $k=1,2,\ldots,N+D-1$ について、ターン $k$ において以下の手順を順に行います。

   1. $k \le N$ ならば、送信セル $(R_s,C_s)$ の状態を $S_k$ に変更する。
   2. グリッド全体に対して 1 回の更新操作を行う。
   3. $D \le k < D+N$ ならば、受信セル $(R_t,C_t)$ の状態を $T$ の末尾に追加する。

4. シミュレーション終了後、$S=T$ が成り立てば正解と判定され、そうでなければ不正解と判定されます。

任意の $N$ および $S$ に対しても正解となるようなオートマトンの設計が必ず存在することが保証されていますが、本問題のジャッジ実装の都合上、各テストケースファイルにおいて $N$ および $S$ は固定されており、また $N \le 300$ のみが使用されます。

This problem provides no input.

本题不提供输入。

Output in the following format:

$F_{0,0}F_{0,1}\ldots F_{0,8}$
$F_{1,0}F_{1,1}\ldots F_{1,8}$
$H$ $W$
$A_{0,0}A_{0,1}\ldots A_{0,W-1}$
$A_{1,0}A_{1,1}\ldots A_{1,W-1}$
$\vdots$
$A_{H-1,0}A_{H-1,1}\ldots A_{H-1,W-1}$
$R_s$ $C_s$ $R_t$ $C_t$ $D$

Your output must satisfy the following conditions.

• $F_{i,j} \in {0,1}$
• $F_{0,0} = 0$
• $1 \le H,W \le 150$
• $A_{r,c} \in {0,1}$
• $0 \le R_s,R_t \lt H$
• $0 \le C_s,C_t \lt W$
• $50 \le |C_s-C_t| \le 100$
• $50 \le D \le 100$

If your output satisfies the above conditions, and is judged correct by the judging method described above for all prepared test cases, this problem is considered solved.

按以下格式输出：

$F_{0,0}F_{0,1}\ldots F_{0,8}$
$F_{1,0}F_{1,1}\ldots F_{1,8}$
$H$ $W$
$A_{0,0}A_{0,1}\ldots A_{0,W-1}$
$A_{1,0}A_{1,1}\ldots A_{1,W-1}$
$\vdots$
$A_{H-1,0}A_{H-1,1}\ldots A_{H-1,W-1}$
$R_s$ $C_s$ $R_t$ $C_t$ $D$

你的输出必须满足以下条件：

• $F_{i,j} \in \{0,1\}$
• $F_{0,0} = 0$
• $1 \le H,W \le 150$
• $A_{r,c} \in \{0,1\}$
• $0 \le R_s,R_t < H$
• $0 \le C_s,C_t < W$
• $50 \le |C_s-C_t| \le 100$
• $50 \le D \le 100$

若你的输出满足上述所有条件，且对所有预设测试用例均能通过前述评测方法判定为正确，则本题视为解答成功。

Visualizer

You can check the behavior of your automaton using the visualizer.

Constraints

• The $N$ used by the judge is between $1$ and $300$, inclusive.

可视化工具

你可以使用 可视化工具 来检查你的自动机的行为。

限制条件

• 评测所用的 $N$ 在 $1$ 到 $300$（含）之间。