19873번 - Олимпиада для роботов 서브태스크스페셜 저지다국어

Жюри чемпионата по скоростному вычислению булевых функций среди роботов готовит задания для участников.

Задание для роботов представляет собой таблицу из m строк и n столбцов, каждая ячейка которой содержит целое число. Обозначим число в i-й строке, j-м столбце таблицы как x_i,j. В каждом столбце значения в ячейках таблицы образую перестановку чисел от 0 до m − 1. Иначе говоря, числа в каждом столбце различны: если i ≠ k, то x_i,j ≠ x_k,j для всех j, и выполнено условие 0 ≤ x_i,j < m.

Для каждого столбца таблицы задаётся значение порога — целое неотрицательное число z_j от 0 до m. В качестве аргументов булевых функций, которые будут вычислять участники олимпиады, используются значения логических выражений x_i,j < z_j. Значение такого логического выражения равно 1, если неравенство выполнено, иначе оно равно 0.

В процессе соревнования участники вычисляют значения m булевых функций — по одному для каждой строки. Каждая булева функция задаётся в виде бесповторной монотонной линейной программы (БМЛП).

Рассмотрим БМЛП для i-й строки таблицы. Она представляет собой последовательность из n − 1 инструкции, пронумерованных от 1 до n − 1, p-я инструкция задаётся тремя числами: a_p, b_p и op_p. Число op_p принимает два возможных значения: 1 для операции and — логическое «и», 2 для операции or — логическое «или». Числа a_p и b_p являются номерами аргументов p-й инструкции, выполнены неравенства 1 ≤ a_p, b_p < n + p.

Рассмотрим массив val[1..2n − 1], каждое из значений которого равно 0 или 1. Проинициализируем значения val[1]..val[n] с использованием порогов, val[j] = 1, если x_i,j < z_j, иначе val[j] = 0. Значение val[n + p] вычисляется с использованием p-й инструкции.

• Если opp = 1, то val[n + p] = (val[a_p] and val[b_p]), то есть значение val[n + p] равно 1 если и только если каждое из значений val[a_p] и val[b_p] равно 1.
• Если opp = 2, то val[n + p] = (val[a_p] or val[b_p]), то есть значение val[n + p] равно 1 если и только если хотя бы одно из значений val[a_p] и val[b_p] равно 1.

При этом программа является бесповторной, а именно все 2n − 2 значений a_p и b_p для p от 1 до n − 1 различны. Иначе говоря, a_p ≠ b_p, а если p ≠ q, то a_p ≠ a_q, a_p ≠ b_q, b_p ≠ a_q и b_p ≠ b_q.

Результатом исполнения программы является значение val[2n − 1].

Жюри олимпиады подготовило таблицу x_i,j, выбрало булевы функции для каждой строки и записало их в виде БМЛП. Теперь осталось выбрать значение порога для каждого столбца, чтобы получить задание для олимпиады. Жюри считает задание сбалансированным, если ровно s из m программ для строк таблицы возвращают единицу, а остальные m − s возвращают ноль. Ваша задача — помочь жюри найти подходящие значения порогов.

Требуется написать программу, которая по заданным значениям в ячейках таблицы и БМЛП для строк таблицы определяет такие значения порогов z_j, чтобы значение ровно s из m заданных функций было равно 1. Можно доказать, что при описанных в условии задачи ограничениях требуемые значения порогов всегда можно подобрать.

В первой строке входных данных заданы целые числа n, m и s (1 ≤ n ≤ 3 · 10⁵, 1 ≤ m ≤ 3 · 10⁵, n · m ≤ 3 · 10⁵, 0 ≤ s ≤ m).

Далее следует m блоков по n−1 строке в каждом, каждый блок задает бесповторную монотонную линейную программу для одной строки таблицы. В каждом блоке p-я строка содержит 3 целых числа: a_p, b_p и op_p (1 ≤ a_p < n + p, 1 ≤ b_p < n + p, гарантируется, что в одном блоке все значения a_p и bp попарно различны, op_p = 1 или op_p = 2).

Последние m строк задают таблицу, i-я строка содержит n целых чисел, j-е из которых равно x_i,j (0 ≤ x_i,j ≤ m−1, в каждом столбце все числа различны, то есть если i ≠ k, то x_i,j ≠ x_k,j для всех j).

Выведите n целых чисел — искомые значения порогов z₁, z₂, . . . , z_n (0 ≤ z_j ≤ m). Если подходящих вариантов несколько, выведите любой из них.

В примере в таблице три строки, каждой соответствует формула. Необходимо найти четыре порога так, чтобы ровно две формулы возвращали 1, а оставшаяся — 0.

Рассмотрим, как будет вычисляться массив val для первой строки.

Первые четыре значения вычисляются на основе чисел в этой строке и порогов:

• val[1] = (x1,1 < z1) = (0 < 0) = 0;
• val[2] = (x1,2 < z2) = (1 < 1) = 0;
• val[3] = (x1,3 < z3) = (2 < 2) = 0;
• val[4] = (x1,4 < z4) = (2 < 3) = 1.

Далее выполняем линейную программу для первой строки:

• val[5] = (val[1] and val[2]) = (0 and 0) = 0;
• val[6] = (val[3] and val[4]) = (0 and 1) = 0;
• val[7] = (val[5] or val[6]) = (0 or 0) = 0.

Таким образом значение булевой функции для первой строки равно 0. Кстати, если эту функцию записать формулой, то получится:

(((x1,1 < z1) and (x1,2 < z2)) or ((x1,3 < z3) and (x1,4 < z4))).

Аналогично, булева функция для второй строки равна:

((((x2,1 < z1) or (x2,2 < z2)) and (x2,3 < z3)) or (x2,4 < z4)),

а для третьей строки:

(((x3,1 < z1) and (x3,4 < z4)) or ((x3,2 < z2) and (x3,3 < z3))).

При подстановке порогов z1 = 0, z2 = 1, z3 = 2, z4 = 3 получим следующие выражения. Вторая строка:

((((2 < 0) or (2 < 1)) and (1 < 2)) or (0 < 3)) = (((0 or 0) and 1) or 1) = (0 or 1) = 1,

Третья строка:

(((1 < 0) and (1 < 3)) or ((0 < 1) and (0 < 2))) = ((0 and 1) or (1 and 1)) = (0 or 1) = 1.

Заметим, что это не единственный подходящий набор порогов, также подойдут, например, значения z₁ = 0, z₂ = 0, z₃ = 3, z₄ = 3.