Ваша задача — построить массив \(a\), состоящий из \(n\) целых чисел, каждый элемент должен быть от \(1\) до \(k\).
Массив должен быть неубывающим (\(a_i \le a_{i+1}\) для всех \(i\) от \(1\) до \(n-1\)).
Также есть дополнительные ограничения на него. Каждое ограничение одного из трех следующих типов:
Постройте любой неубывающий массив, который удовлетворяет всем ограничениям, или скажите, что такого массива не существует.
В первой строке записано одно целое число \(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\) строк записано описание ограничения. Каждое ограничение одного из трех следующих типов:
Сумма \(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
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач