Рисунок можно представить в виде таблицы \(n\times m\) (\(n\) строк, \(m\) столбцов), при этом каждая из \(n \cdot m\) клеток будет покрашена в один из цветов. У вас есть \(k\) красок различных цветов. Количество каждой краски ограниченно, а именно, вы можете покрасить не более \(a_i\) клеток в \(i\)-й цвет.
Рисунок называется красивым, если у каждой клетки не менее \(3\) тороидных соседних клеток имеют такой же цвет.
Две клетки являются тороидными соседями, если они имеют общую сторону на торе. Другими словами, для некоторых целых чисел \(1 \leq x_1,x_2 \leq n\) и \(1 \leq y_1,y_2 \leq m\) клетка в \(x_1\)-й строке \(y_1\)-м столбце является тороидным соседом клетки в \(x_2\)-й строке и \(y_2\)-м столбце, если выполняется одно из следующих двух условий:
- \(x_1-x_2 \equiv \pm1 \pmod{n}\) и \(y_1=y_2\), или
- \(y_1-y_2 \equiv \pm1 \pmod{m}\) и \(x_1=x_2\).
Обратите внимание, что у каждой клетки ровно \(4\) тороидных соседа. Например, если \(n=3\), а \(m=4\), то тороидными соседями клетки \((1, 2)\) (клетки в первой строке втором столбце) являются клетки \((3, 2)\), \((2, 2)\), \((1, 3)\), \((1, 1)\). Они выделены серым на рисунке ниже:
Серым выделены тороидные соседи клетки \((1, 2)\). Можно ли покрасить все клетки таблицы имеющимися красками и получить красивый рисунок?
Примечание
В первом примере одно из возможных решений следующее:
В третьем примере можно покрасить все клетки в \(1\)-й цвет.