An và anh trai cùng thích một trò chơi trên máy tính. Trò chơi mô tả một vương quốc dưới dạng bảng có kích thước \(\mathbf{N \times N}\); mỗi ô vuông \(\mathbf{(i,\ j)\ }\)trên bảng (hàng thứ \(\mathbf{i}\) tính từ trên xuống dưới, cột thứ\(\mathbf{\ j\ }\)tính từ trái qua phải) được gán nhãn là \(\mathbf{1\ }\)nếu là ô cây và \(\mathbf{0}\) nếu là ô nước. Hai ô trong bảng có cùng một cạnh và cùng là cây thì ở cùng một đảo.

Trong trò chơi, người chơi cần di chuyển từ ô \(\mathbf{(x}_{\mathbf{a}}\mathbf{,}\mathbf{y}_{\mathbf{a}}\mathbf{)}\) đến \(\mathbf{(x}_{\mathbf{b}}\mathbf{,}\mathbf{y}_{\mathbf{b}}\mathbf{)}\) bằng cách thực hiện một dãy các bước di chuyển (có thể là không bước nào hoặc nhiều bước). Trong một lượt, nếu người chơi đang ở ô \(\mathbf{(x}_{\mathbf{i}}\mathbf{,}\mathbf{y}_{\mathbf{i}}\mathbf{)}\) thì cần thực hiện hai hành động:

• Loại 1: di chuyển từ \(\mathbf{(x}_{\mathbf{i}}\mathbf{,}\mathbf{y}_{\mathbf{i}}\mathbf{)}\) tới một ô cây \(\mathbf{(x}_{\mathbf{j}}\mathbf{,}\mathbf{y}_{\mathbf{j}}\mathbf{)}\) nằm ở đảo khác với chi phí là \(\mathbf{|x}_{\mathbf{i}}\mathbf{-}\mathbf{x}_{\mathbf{j}}\mathbf{| + |}\mathbf{y}_{\mathbf{i}}\mathbf{-}\mathbf{y}_{\mathbf{j}}\mathbf{|}\)

• Loại 2: di chuyển từ \(\mathbf{(x}_{\mathbf{i}}\mathbf{,}\mathbf{y}_{\mathbf{i}}\mathbf{)}\) tới một ô cây \(\mathbf{(x}_{\mathbf{j}}\mathbf{,}\mathbf{y}_{\mathbf{j}}\mathbf{)}\) nằm ở cùng đảo với chi phí là \(\mathbf{0}\)

Gọi vẻ đẹp của dãy các bước di chuyển là số hành động loại 1 trong khi đi từ ô \(\mathbf{(x}_{\mathbf{a}}\mathbf{,}\mathbf{y}_{\mathbf{a}}\mathbf{)}\) đến \(\mathbf{(x}_{\mathbf{b}}\mathbf{,}\mathbf{y}_{\mathbf{b}}\mathbf{)}\). Chi phí đơn giản là chi phí nhỏ nhất của dãy có vẻ đẹp \(\mathbf{\leq 1}\).

An muốn tìm vẻ đẹp tối đa để đi từ ô \(\mathbf{(x}_{\mathbf{a}}\mathbf{,}\mathbf{y}_{\mathbf{a}}\mathbf{)}\) đến \(\mathbf{(x}_{\mathbf{b}}\mathbf{,}\mathbf{y}_{\mathbf{b}}\mathbf{)}\) mà không vượt quá chi phí đơn giản.

Yêu cầu: Bạn hãy giúp An tìm câu trả lời với mọi ô cây có thể \(\mathbf{(x}_{\mathbf{b}}\mathbf{,}\mathbf{y}_{\mathbf{b}}\mathbf{)}\).

Lưu ý ta không cần tối thiểu chi phí của chuyến đi, chỉ cần vẻ đẹp tối đa mà không vượt quá chi phí đơn giản.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên \(\mathbf{N}\)

• \(\mathbf{N\ }\)dòng tiếp theo mỗi dòng chứa một xâu \(S = \mathbf{s}_{\mathbf{1}}\mathbf{s}_{\mathbf{2}}\mathbf{\ldots}\mathbf{s}_{\mathbf{N}}\). Xâu thứ \(\mathbf{i}\) thể hiện hàng thứ \(\mathbf{i\ }\)của bảng, với \(\mathbf{s}_{\mathbf{j}}\) là \(\mathbf{1}\) nếu ô \(\mathbf{(i,\ j)}\) là cây, và \(\mathbf{0}\) nếu nó là nước.

• Dòng cuối chứa hai số nguyên \(\mathbf{x}_{\mathbf{a}}\) và \(\mathbf{y}_{\mathbf{a}}\). Dữ liệu đảm bảo \(\mathbf{(x}_{\mathbf{a}}\mathbf{,}\mathbf{y}_{\mathbf{a}}\mathbf{)}\) là một ô cây.

Kết quả:

• In ra \(\mathbf{N}\) dòng, mỗi dòng chứa \(\mathbf{N}\) số nguyên.

• Số nguyên thứ \(\mathbf{j}\) ở hàng thứ \(\mathbf{i\ }\)thể hiện vẻ đẹp lớn nhất có thể của đường đi từ \(\mathbf{(x}_{\mathbf{a}}\mathbf{,}\mathbf{y}_{\mathbf{a}}\mathbf{)}\) tới ô \(\mathbf{(i,\ j)\ }\)thỏa mãn các điều kiện trên, nếu ô \(\mathbf{(i,\ j)\ }\)là cây. Nếu \(\mathbf{(i,\ j)}\) là ô nước hoặc cùng đảo với \(\mathbf{(x}_{\mathbf{a}}\mathbf{,}\mathbf{y}_{\mathbf{a}}\mathbf{)}\) , in ra giá trị \(\mathbf{0}\). Các giá trị 0, 1 cách nhau 1 dấu cách.

Ví dụ:

Giải thích

• Ở test thứ 1: Chi phí đơn giản từ (1, 1) tới (1, 7) là |1 - 1| + |1 - 7| = 0 + 6 = 6. Tuy nhiên chúng ta có thể đạt được vẻ đẹp 2 mà không vượt quá chi phí đơn giản theo cách:

• Hành động loại 1 từ (1, 1) tới (1, 3) chi phí là 2.

• Hành động loại 2 từ (1, 3) tới (1, 5) chi phí là 0.

• Hành động loại 1 từ (1, 5) tới (1, 7) chi phí là 2.

Chú ý rằng chi phí một số dãy có vẻ đẹp >1 có thể nhỏ hơn chi phí đơn giản.

• Ở test thứ 2: Chi phí đơn giản từ (2, 4) tới (5, 2) là |2 - 5| + |4 - 2| = 3 + 2 = 5. Ta có thể đạt được vẻ đẹp bằng 2 mà không vượt quá chi phí đơn giản theo cách:

• Hành động loại 1 từ (2, 4) tới (5, 4) có chi phí là 3.

• Hành động loại 1 từ (5, 4) tới (5, 2) có chi phí là 2.

Giới hạn:

• Subtask 1: 40% tổng số test có \(N\) \(\leq\) 50.

• Subtask 2: 30% tổng số test có \(N\) \(\leq\) 100.

• Subtask 3: 30% tổng số test có \(N\) \(\leq\) 200.