Замовлення від фермерів

Limits: 2 sec., 256 MiB

До компанiї Зеника й Марiчки PLVIV звернулося iз замовленням фермерське господарство.

У розпорядженні господарства є прямокутне помідорове поле, поділене на $n \times m$ ділянок. На деяких ділянках можна садити помідори, а на деяких — ні.

Щоб помідори добре росли, повинна виконуватись така умова. Якщо помідори ростуть на деякій ділянці поля, то на всіх сусідніх по діагоналі ділянках поля також повинні рости помідори.

Господарство хоче посадити якомога більше помідорів, щоб задовольнити цю умову.

Напишіть програму, яка визначає, на яких ділянках потрібно посадити помідори.

Input

У першому рядку задано два цілі числа $n$ і $m$ — розміри поля.

У наступних $n$ рядках записано по $m$ символів — 1, якщо на відповідній ділянці можна садити помідори, або 0, якщо не можна.

Output

Виведіть $n$ рядків по $m$ символів — 1, якщо на відповідній ділянці потрібно посадити помідори, або 0, якщо ні.

Constraints

$1 \le n, m \le 300$.

Samples

Input (stdin) сopy	Output (stdout) сopy
1 1 1	1

Input (stdin) сopy	Output (stdout) сopy
7 7 1011011 1011011 1011011 1000011 1111011 1111011 1111011	0000000 0000000 0000000 0000000 0000000 0000000 0000000

Input (stdin) сopy	Output (stdout) сopy
2 3 111 010	101 010