Недавно было очередное зачисление новых студентов в Берляндский государственный университет (БГУ). Все студенты при поступлении попадают в группу в зависимости от факультета и направления. Некоторые группы могут получиться очень большими, и тогда группу делят на две подгруппы, которые посещают занятия отдельно друг от друга. Вам нужно помочь разделить группы студентов, принятых на факультет информационных технологий.
Всего на факультет поступило \(t\) разных групп. Студенты каждой группы будут посещать занятия по трём дисциплинам — математике, программированию и физкультуре. Все эти занятия проводятся в разных местах — занятия по математике проходят в лекционных аудиториях, по программированию — в компьютерных классах, по физкультуре — в спортзалах.
Каждую группу необходимо разделить на две подгруппы так, чтобы в каждой подгруппе количество студентов на каждом занятии не превышало вместимость аудитории, класса или спортзала. У первой подгруппы \(i\)-й группы занятия по математике проводятся в аудитории, вмещающей не более \(a_{i, 1}\) студентов; по программированию — в классе, вмещающем не более \(b_{i, 1}\) студентов; по физкультуре — в спортзале, вмещающем не более \(c_{i, 1}\) студентов. Аналогично со второй подгруппой — на занятиях по математике, программированию и физкультуре может поместиться не более \(a_{i, 2}\), \(b_{i, 2}\) и \(c_{i, 2}\) студентов, соответственно.
Как известно, студенты часто пропускают занятия. У каждого студента есть какое-то количество (от \(0\) до \(3\)) предметов, которые он считает бесполезными — а значит, не посещает ни одного занятия по этим предметам (а на занятия по остальным предметам он приходит). Эти данные вам были предоставлены в следующем формате — \(i\)-я группа состоит из:
- \(d_{i, 1}\) студентов, посещающих все занятия;
- \(d_{i, 2}\) студентов, посещающих все занятия, кроме физкультуры;
- \(d_{i, 3}\) студентов, посещающих все занятия, кроме программирования;
- \(d_{i, 4}\) студентов, посещающих только математику;
- \(d_{i, 5}\) студентов, посещающих все занятия, кроме математики;
- \(d_{i, 6}\) студентов, посещающих только программирование;
- \(d_{i, 7}\) студентов, посещающих только физкультуру.
Отметим, что есть и восьмой тип студентов — те, кто не посещает университет вообще. Но так как на места в аудиториях они (по очевидным причинам) не претендуют, данные о количестве таких студентов вас не интересуют.
Теперь перед вами стоит следующая задача: определить, как разделить каждую группу на две подгруппы таким образом, чтобы в каждой аудитории (или в компьютерном классе, или в спортзале, в зависимости от занятия) хватало места для всех студентов из подгруппы, приходящих на это занятие (если это вообще возможно). Каждый студент из \(i\)-й группы должен быть определен ровно в одну подгруппу \(i\)-й группы; перемещать студентов между группами запрещено.