D. Делители и степенные разности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана матрица $$$a$$$, состоящая из положительных целых чисел. В ней $$$n$$$ строк и $$$m$$$ столбцов.

Постройте матрицу $$$b$$$, состоящую из положительных целых чисел. Она должна иметь такой же размер, что и матрица $$$a$$$, а также должны выполняться следующие условия:

  • $$$1 \le b_{i,j} \le 10^6$$$;
  • $$$b_{i,j}$$$ делится на $$$a_{i,j}$$$;
  • модуль разности чисел в любой паре соседних клеток (двух клеток, имеющих общую сторону) в $$$b$$$ равен $$$k^4$$$ для некоторого целого числа $$$k \ge 1$$$ ($$$k$$$ не обязательно одинаковое для всех пар, для каждой пары это число может быть свое).

Можно показать, что ответ всегда существует.

Входные данные

В первой строке находятся два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n,m \le 500$$$).

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел. $$$j$$$-е число в $$$i$$$-й строке — это $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le 16$$$).

Выходные данные

Выведите $$$n$$$ строк, в каждой $$$m$$$ целых чисел. $$$j$$$-е число в $$$i$$$-й строке должно быть $$$b_{i,j}$$$.

Примеры
Входные данные
2 2
1 2
2 3
Выходные данные
1 2
2 3
Входные данные
2 3
16 16 16
16 16 16
Выходные данные
16 32 48
32 48 64
Входные данные
2 2
3 11
12 8
Выходные данные
327 583
408 664
Примечание

В первом примере матрица $$$a$$$ может быть использована как матрица $$$b$$$, потому что модуль разности чисел в любой паре соседних клеток равен $$$1 = 1^4$$$.

В третьем примере:

  • $$$327$$$ делится на $$$3$$$, $$$583$$$ делится на $$$11$$$, $$$408$$$ делится на $$$12$$$, $$$664$$$ делится на $$$8$$$;
  • $$$|408 - 327| = 3^4$$$, $$$|583 - 327| = 4^4$$$, $$$|664 - 408| = 4^4$$$, $$$|664 - 583| = 3^4$$$.