After getting bored of playing video games, Mike decided to go hiking. Like any good hiker, he brought a map along with him. However, shortly after setting out for the hike, Mike was caught in a rainstorm. Once he found shelter under a nearby tree, Mike realized his map had gotten drenched as well!
Determined to finish his hike, Mike wants you to reconstruct the map. The map is represented as an array of integers, each indicating the elevation at a particular point. Remembering that certain sections of the map were uphill or downhill, Mike will give you requirements, each in the form :
- If , the subarray from index to index is strictly increasing.
- If , the subarray from index to index is strictly decreasing.
Mike also has some additional requirements for the map: First of all, he tells you that the trail is never flat, so no two adjacent elements can be equal. Second of all, each element must be a positive integer not exceeding . Third of all, the maximum element of the array should be as small as possible.
Help Mike reconstruct his map, or tell him that it is impossible to do so.
Constraints
Subtask 1 [50%]
If your submission outputs a valid map but does not minimize the maximum element, you will receive out of the of points available for this subtask.
Subtask 2 [50%]
No additional constraints.
If your submission outputs a valid map but does not minimize the maximum element, you will receive out of the of points available for this subtask.
Input Specification
The first line contains integers and .
The -th of the following lines each contain integers , describing a requirement as specified in the statement.
Output Specification
If no valid output exists, output .
Otherwise, output one line containing positive integers that satisfy all requirements. Each element must be within the range , and no two adjacent elements can be equal.
If there are multiple valid answers, you may output any of them.
Sample Input 1
5 2
1 1 3
2 3 5
Sample Output 1
1 2 3 2 1
Sample Input 2
3 3
1 1 2
1 2 3
2 1 3
Sample Output 2
-1
Comments