Problem Statement

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 0s and 1s. 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.

Constraints

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

Sample Output

000100000
001100000
4 54
100000000000000000000000000000000000000000000000000000
000010000000000000000000000000000000000000000000000000
100010000000000000000000000000000000000000000000000000
011110000000000000000000000000000000000000000000000000
0 3 0 53 100

This sample output is provided to illustrate the output format. For N=1, it is correct for all S, but for 2 \le N, there exist some S for which it is incorrect.

Visualizer

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