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

Ваша задача — построить массив $$$a$$$, состоящий из $$$n$$$ целых чисел, каждый элемент должен быть от $$$1$$$ до $$$k$$$.

Массив должен быть неубывающим ($$$a_i \le a_{i+1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$).

Также есть дополнительные ограничения на него. Каждое ограничение одного из трех следующих типов:

  • $$$1~i~x$$$: $$$a_i$$$ должно быть не равно $$$x$$$;
  • $$$2~i~j~x$$$: $$$a_i + a_j$$$ должно быть меньше или равно $$$x$$$;
  • $$$3~i~j~x$$$: $$$a_i + a_j$$$ должно быть больше или равно $$$x$$$.

Постройте любой неубывающий массив, который удовлетворяет всем ограничениям, или скажите, что такого массива не существует.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны три целых числа $$$n, m$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^4$$$; $$$0 \le m \le 2 \cdot 10^4$$$; $$$2 \le k \le 10$$$).

В $$$i$$$-й из следующих $$$m$$$ строк записано описание ограничения. Каждое ограничение одного из трех следующих типов:

  • $$$1~i~x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le k$$$): $$$a_i$$$ должно быть не равно $$$x$$$;
  • $$$2~i~j~x$$$ ($$$1 \le i < j \le n$$$; $$$2 \le x \le 2 \cdot k$$$): $$$a_i + a_j$$$ должно быть меньше или равно $$$x$$$;
  • $$$3~i~j~x$$$ ($$$1 \le i < j \le n$$$; $$$2 \le x \le 2 \cdot k$$$): $$$a_i + a_j$$$ должно быть больше или равно $$$x$$$.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^4$$$. Сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^4$$$.

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

Для каждого набора входных данных определит, существует ли неубывающий массив, который удовлетворяет всем ограничениям. Если такого не существует, то выведите -1. Иначе выведите валидный массив — $$$n$$$ целых чисел от $$$1$$$ до $$$k$$$.

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