Ваша задача — построить массив \(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\).
Постройте любой неубывающий массив, который удовлетворяет всем ограничениям, или скажите, что такого массива не существует.
Выходные данные
Для каждого набора входных данных определит, существует ли неубывающий массив, который удовлетворяет всем ограничениям. Если такого не существует, то выведите -1. Иначе выведите валидный массив — \(n\) целых чисел от \(1\) до \(k\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|