F. Разделение студентов
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно было очередное зачисление новых студентов в Берляндский государственный университет (БГУ). Все студенты при поступлении попадают в группу в зависимости от факультета и направления. Некоторые группы могут получиться очень большими, и тогда группу делят на две подгруппы, которые посещают занятия отдельно друг от друга. Вам нужно помочь разделить группы студентов, принятых на факультет информационных технологий.

Всего на факультет поступило $$$t$$$ разных групп. Студенты каждой группы будут посещать занятия по трём дисциплинам — математике, программированию и физкультуре. Все эти занятия проводятся в разных местах — занятия по математике проходят в лекционных аудиториях, по программированию — в компьютерных классах, по физкультуре — в спортзалах.

Каждую группу необходимо разделить на две подгруппы так, чтобы в каждой подгруппе количество студентов на каждом занятии не превышало вместимость аудитории, класса или спортзала. У первой подгруппы $$$i$$$-й группы занятия по математике проводятся в аудитории, вмещающей не более $$$a_{i, 1}$$$ студентов; по программированию — в классе, вмещающем не более $$$b_{i, 1}$$$ студентов; по физкультуре — в спортзале, вмещающем не более $$$c_{i, 1}$$$ студентов. Аналогично со второй подгруппой — на занятиях по математике, программированию и физкультуре может поместиться не более $$$a_{i, 2}$$$, $$$b_{i, 2}$$$ и $$$c_{i, 2}$$$ студентов, соответственно.

Как известно, студенты часто пропускают занятия. У каждого студента есть какое-то количество (от $$$0$$$ до $$$3$$$) предметов, которые он считает бесполезными — а значит, не посещает ни одного занятия по этим предметам (а на занятия по остальным предметам он приходит). Эти данные вам были предоставлены в следующем формате — $$$i$$$-я группа состоит из:

  1. $$$d_{i, 1}$$$ студентов, посещающих все занятия;
  2. $$$d_{i, 2}$$$ студентов, посещающих все занятия, кроме физкультуры;
  3. $$$d_{i, 3}$$$ студентов, посещающих все занятия, кроме программирования;
  4. $$$d_{i, 4}$$$ студентов, посещающих только математику;
  5. $$$d_{i, 5}$$$ студентов, посещающих все занятия, кроме математики;
  6. $$$d_{i, 6}$$$ студентов, посещающих только программирование;
  7. $$$d_{i, 7}$$$ студентов, посещающих только физкультуру.

Отметим, что есть и восьмой тип студентов — те, кто не посещает университет вообще. Но так как на места в аудиториях они (по очевидным причинам) не претендуют, данные о количестве таких студентов вас не интересуют.

Теперь перед вами стоит следующая задача: определить, как разделить каждую группу на две подгруппы таким образом, чтобы в каждой аудитории (или в компьютерном классе, или в спортзале, в зависимости от занятия) хватало места для всех студентов из подгруппы, приходящих на это занятие (если это вообще возможно). Каждый студент из $$$i$$$-й группы должен быть определен ровно в одну подгруппу $$$i$$$-й группы; перемещать студентов между группами запрещено.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 300$$$) — количество групп.

Далее следуют описания групп. Описание $$$i$$$-й группы состоит из трех строк:

  • в первой строке заданы три целых числа $$$a_{i, 1}$$$, $$$b_{i, 1}$$$ и $$$c_{i, 1}$$$ ($$$1 \le a_{i, 1}, b_{i, 1}, c_{i, 1} \le 3000$$$) — вместимость лекционной аудитории, компьютерного класса и спортзала для первой подгруппы $$$i$$$-й группы соответственно;
  • во второй строке заданы три целых числа $$$a_{i, 2}$$$, $$$b_{i, 2}$$$ и $$$c_{i, 2}$$$ ($$$1 \le a_{i, 2}, b_{i, 2}, c_{i, 2} \le 3000$$$) — вместимость лекционной аудитории, компьютерного класса и спортзала для второй подгруппы $$$i$$$-й группы соответственно;
  • в третьей строке заданы семь целых чисел $$$d_{i, 1}$$$, $$$d_{i, 2}$$$, ..., $$$d_{i, 7}$$$ ($$$0 \le d_{i, j} \le 3000$$$) — количество студентов каждого из описанных в условии семи типов в $$$i$$$-й группе. Не гарантируется, что сумма этих чисел будет отличной от нуля — группа вполне может состоять из студентов, не ходящих на занятия вообще.

Гарантируется, что суммарное количество студентов во всех группах не превосходит $$$3000$$$.

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

Для всех групп выведите результат разделения группы в следующем формате:

  • если группу разделить невозможно, выведите одно целое число $$$-1$$$;
  • иначе выведите семь целых чисел $$$f_{i, 1}$$$, $$$f_{i, 2}$$$, ..., $$$f_{i, 7}$$$ ($$$0 \le f_{i, j} \le d_{i, j}$$$) — количество студентов каждого типа в первой подгруппе $$$i$$$-й группы (все остальные студенты из группы автоматически определяются во вторую подгруппу). Если ответов несколько, выведите любой из них.
Пример
Входные данные
3
9 4 13
1 10 3
1 2 3 4 5 6 7
9 4 13
1 10 3
2 1 3 4 5 6 7
1 2 3
4 5 6
0 0 0 0 0 0 0
Выходные данные
1 1 3 4 2 0 7
-1
0 0 0 0 0 0 0