C. Мексимальный массив 2
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ferus Melek - Brute Force
⠀

Вам даны три целых положительных числа $$$n$$$, $$$k$$$ и $$$q$$$. Также вам даны $$$q$$$ кортежей $$$(c, l, r)$$$, где $$$1 \leq c \leq 2$$$ и $$$1 \leq l \leq r \leq n$$$.

Массив $$$a_1, a_2, \ldots, a_n$$$ является мексимальным, если $$$0 \leq a_i \leq 10^9$$$ для каждого $$$i$$$ в $$$[1, n]$$$, и для каждого данного кортежа $$$(c, l, r)$$$:

  • если $$$c = 1$$$, то $$$\min(a_l, a_{l+1}, \ldots, a_r) = k$$$;
  • если $$$c = 2$$$, то $$$\operatorname{MEX}$$$$$$^{\text{∗}}$$$$$$(a_l, a_{l+1}, \ldots, a_r) = k$$$.

Обратите внимание, что параметр $$$k$$$ одинаков для всех условий.

Найдите мексимальный массив $$$a_1, a_2, \ldots, a_n$$$ длиной $$$n$$$. Входные данные сгенерированы таким образом, что всегда существует допустимый массив. Если существует несколько возможных массивов, вы можете вывести любой из них.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$a_1, a_2, \ldots, a_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$a$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$, $$$q$$$ ($$$1 \leq k \leq n \leq 100$$$, $$$1 \leq q \leq 100$$$) — длина массива $$$a_1, a_2, \ldots, a_n$$$, результат вычислений $$$\min$$$ и $$$\operatorname{MEX}$$$, описанных кортежами, и количество кортежей.

Затем следуют $$$q$$$ строк. $$$i$$$-я строка содержит кортеж $$$(c, l, r)$$$, который задает ограничение для $$$a_l, a_{l+1}, \ldots, a_r$$$ в соответствии с условием.

Гарантируется, что существует допустимый массив, соответствующий данным входным данным.

Обратите внимание, что нет ограничений на сумму $$$n$$$, $$$k$$$ или $$$q$$$ по всем наборам входных данных.

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

Для каждого набора входных данных выведите одну строку, содержащую мексимальный массив $$$a_1, a_2, \ldots, a_n$$$.

Пример
Входные данные
4
6 2 2
1 1 3
2 2 6
3 3 1
2 1 3
3 3 2
1 1 1
1 3 3
3 2 2
2 1 2
2 2 3
Выходные данные
2 5 4 3 0 1
2 0 1
3 3 3
1 0 1
Примечание

В первом наборе входных данных вам нужно построить мексимальный массив с $$$n = 6$$$, $$$k = 2$$$ и с $$$q = 2$$$ ограничениями, заданных кортежами.

  • кортеж $$$(1, 1, 3)$$$: $$$\min(a_1, a_2, a_3)$$$ должен быть $$$2$$$;
  • кортеж $$$(2, 2, 6)$$$: $$$\operatorname{MEX}(a_2, a_3, a_4, a_5, a_6)$$$ должен быть $$$2$$$.

Возможный массив, который удовлетворяет всем этим ограничениям и имеет элементы $$$0 \leq a_i \leq 10^9$$$, это $$$[2, 5, 4, 3, 0, 1]$$$.

Во втором наборе входных данных вам нужно построить мексимальный массив с $$$n = 3$$$, $$$k = 3$$$ и с $$$q = 1$$$ ограничением, заданным кортежем.

  • кортеж $$$(2, 1, 3)$$$: $$$\operatorname{MEX}(a_1, a_2, a_3)$$$ должен быть $$$3$$$.

Возможный массив, который удовлетворяет этому ограничению и имеет элементы $$$0 \leq a_i \leq 10^9$$$, это $$$[2, 0, 1]$$$.