Задача F. Круговая оборона ≡

Условие

У государства Централии есть четыре агрессивных соседа: Верхия, Низия, Правия и Левия. Правители соседних государств постоянно сосредотачивают на границе с Централией свои армии, ожидая удобного случая для вторжения. Удобным агрессоры считают случай, когда количество армий Централии, охраняющих границу с данным государством, будет меньше, чем количество армий, сосредоточенных на границе агрессором.

Поскольку содержание армий — дорогостоящее занятие, Централия может постоянно поддерживать только $N$ армий. К счастью, по той же причине её соседи, чья экономика менее стабильна, чем в Централии, могут в $i$-й год подготовить для завоевания $A_{i,k}$ армий, где $k = 0 \dots 3$ — номер соседа.

В Централии проживает могущественный колдун-экономист, который сумел предсказать количество враждебных армий на $T$ лет вперёд. Вам поручена роль главнокомандующего армиями Централии с задачей распределения армий по границам таким образом, чтобы удобный для вторжения случай предоставился как можно позже. Задача осложняется тем, что за один год любая армия Централии может переместиться с той границы, которую она занимала в прошлом году, только на соседнюю границу, т.е. с $k$-й границы либо на границу $(k + 1) mod 4$, либо на границу $(k + 3) mod 4$.

Формат входного файла

Формат выходного файла

В выходном файле должно содержаться число $Q$ — максимальное количество лет, в течение которого можно избежать вторжения ($0 \le Q \le T$), за которым следуют $Q$ четвёрок чисел $B_{i,0}\,B_{i,1}\,B_{i,2}\,B_{i,3}$ — количество армий, которые следует в $i$-м году расположить на каждой из границ ($B_{i,0} + B_{i,1} + B_{i,2} + B_{i,3} = N$). Расположение защищающихся армий в первом году может быть произвольным, а расположение в каждом следующем году должно учитывать ограничения на перемещение армий.

Если существует несколько оптимальных решений, вывести любое из них.

Ограничения

Примеры тестов

4 2
0 4 0 0
2 1 1 0

2
0 4 0 0
2 1 1 0

4 2
0 4 0 0
2 0 1 1

1
0 4 0 0