Задача 4. Олимпиада для роботов ≡

Условие

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

Задание для роботов представляет собой таблицу из 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-й инструкции.

• Если op_p = 1, то val[n + p] = (val[a_p] and al[b_p]), то есть значение val[n + p] равно 1 если и только если каждое из значений val[a_p] и val[b_p] равно 1.
• Если op_p = 2, то val[n + p] = (val[a_p] or al[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 и b_p попарно различны, 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 ≤ n ≤ 3 ⋅ 10⁵, 1 ≤ m ≤ 3 ⋅ 10⁵, n ⋅ m ≤ 3 ⋅ 10⁵, 0 ≤ s ≤ m

1 ≤ a_p < n + p, 1 ≤ b_p < n + p, гарантируется, что в одном блоке все значения a_p и b_p попарно различны, op_p = 1 или op_p = 2

1 ≤ t_i ≤ 10⁹, 1 ≤ k_i ≤ 10¹⁸

0 ≤ x_{i, j} ≤ m − 1, в каждом столбце все числа различны, то есть если i ≠ k, то x_{i, j} ≠ x_{k, j} для всех j

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Замечание

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

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

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

• val[1] = (x_1,1 < z₁) = (0 < 0) = 0;
• val[2] = (x_1,2 < z₂) = (1 < 1) = 0;
• val[3] = (x_1,3 < z₃) = (2 < 2) = 0;
• val[4] = (x_1,4 < z₄) = (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. Кстати, если эту функцию записать формулой, то получится:

(((x_1,1 < z₁) and (x_1,2 < z₂)) or ((x_1,3 < z₃) and (x_1,4 < z₄))).

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

((((x_2,1 < z₁) or (x_2,2 < z₂)) and (x_2,3 < z₃)) or (x_2,4 < z₄)),

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

(((x_3,1 < z₁) and (x_3,4 < z₄)) or ((x_3,2 < z₂) and (x_3,3 < z₃))).

При подстановке порогов z₁ = 0, z₂ = 1, z₃ = 2, z₄ = 3 получим следующие выражения.

Вторая строка:

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

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

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

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

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

4 3 2
1 2 1
3 4 1
5 6 2
1 2 2
3 5 1
4 6 2
1 4 1
2 3 1
5 6 2
0 1 2 2
2 2 1 0
1 0 0 1

0 1 2 3

Разбор

Отметим три важных свойства операций and и or : сохранение 0, сохранение 1 и монотонность:

• 0 and 0 = 0 и 0 or 0 = 0, поэтому если все входные переменные равны 0, то значение любой функции, которую можно задать БМЛП, равно 0.
• 1 and 1 = 1 и 1 or 1 = 1, поэтому если все входные переменные равны 1, то значение любой функции, которую можно задать БМЛП, равно 1.
• Если увеличить значение аргумента, то значение and и or не уменьшается. Значит если входное значение изменяется c 0 на 1, то значение функции, которую вычисляет БМЛП либо не изменяется, либо изменяется с 0 на 1.

Изначально положим z_i = 0. Поскольку x < 0 ложно для всех неотрицательных x, все начальные значения val будут 0, а значит в силу сохранения 0 все значения функций равны 0.

Изменим одно из значений z_i < m на z_i + 1. Заметим, что в этом столбце ровно одно значение x_j,i равно z_i. Только у j-й булевой функции изменятся входные переменные, причем 0 заменится на 1, а значит в силу монотонности количество программ, возвращающих единицу, либо не изменится, либо увеличится на один.

Наконец, если все z_i = m, то все входные переменные равны 1 и значение всех функций равно 1.

Сделав эти наблюдения, получаем первое решение задачи. Будем последовательно выбирать любое значение z_i < m и увеличивать его на один. После этого будем пересчитывать количество программ, возвращающих единицу, то в какой-то момент мы обязательно получим s программ. Такая наивная реализация работает за O((nm)²) и решает подзадачи 1 и 3.

Заметим, что поскольку входные данные изменяются только для одной функции, то можно пересчитывать значение только для неё. Время работы усовершенствованного решения равно O(mn²) = O((nm)n), поэтому оно решает подзадачи с небольшим n: 1, 2, 3 и 6.

Поскольку порядок изменений z_i не важен, можно, например, сначала увеличивать z₁, пока оно не станет равно m, потом z₂ и так далее. Теперь для зафиксированного i можно сделать двоичный поиск по количеству изменений. Полученное решение работает за O(nmlognm) и при достаточно оптимальной реализации может пройти тесты для всех подзадач.

Рассмотрим теперь решение без двоичного поиска. Для каждой инструкции нас интересует первый момент, когда она станет равна единице. Заметим, что результат каждой инструкция, кроме последней в каждой программе, является входом ровно одной другой инструкции. Поэтому, когда мы увеличиваем z_i, мы изменяем ровно одно выражение (x_j,i < z_i) с нуля на единицу, которое в свою очередь может изменить выход той инструкцию, в которой это выражение было входом, и так далее. Следуя этой логике, будем рекурсивно подниматься по дереву разбора программы и изменять выходы инструкций с нуля на единицу, пока не встретим единицу или не прекратим изменение. Так как каждая инструкция будет изменена не более одного раза, итоговое время работы составит O(nm). В этом решении используется бесповторность программы: факт, что каждая ячейка массива val используется как вход ровно один раз.