시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 374 143 102 33.443%

문제

수업시간이 너무나 지루했던 태석이는 종이에 길이가 N인 수열 A를 적었다. 이 수열은 1보다 크거나 같고, N보다 작거나 같은 양의 정수로 이루어져 있고, 각 숫자는 정확히 한 번씩 등장한다.

그런 다음 태석이는 다른 종이에 수열 A에 대한 설명을 M개 적었다.

각 설명은 다음과 같은 형태로 되어있다.

  • 1 x y v - x번째 수부터, y번째 수 중 제일 큰 값은 v
  • 2 x y v - x번째 수부터, y번째 수 중 제일 작은 값은 v

태석이는 설명만 적은 종이를 보성이에게 주었다. 보성이는 M개의 설명만 가지고 태석이가 원래 적은 수열을 맞추어보려고 한다.

M개의 설명이 주어졌을 때, 태석이가 원래 적은 수열을 구해 출력하는 프로그램을 작성하시오. 수열은 여러개 존재할 수 있다.

입력

첫째 줄에 수열의 크기 N과 설명의 개수 M이 주어진다. (1<=N<=200, 0<=M<=40,000) 둘째 줄부터 M개의 줄에는 태석이의 설명이 문제 설명과 같은 형식으로 주어진다.

출력

첫째 줄에 태석이가 원래 적은 수 N개를 공백으로 구분하여 출력한다. 만약 태석이의 설명과 일치하는 수열이 없다면 -1을 출력한다.

예제 입력 1

3 2
1 1 1 1
2 2 2 2

예제 출력 1

1 2 3

예제 입력 2

4 2
1 1 1 1
2 3 4 1

예제 출력 2

-1

예제 입력 3

5 2
1 2 3 3
2 4 5 4

예제 출력 3

1 2 3 4 5
W3sicHJvYmxlbV9pZCI6IjI3ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3NTRcdWQ1NWMgXHVjMjE4XHVjNWY0IFx1YmIzOFx1YzgxYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMjE4XHVjNWM1XHVjMmRjXHVhYzA0XHVjNzc0IFx1YjEwOFx1YmIzNFx1YjA5OCBcdWM5YzBcdWI4ZThcdWQ1ODhcdWIzNTggXHVkMGRjXHVjMTFkXHVjNzc0XHViMjk0IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWMyMThcdWM1ZjQgQVx1Yjk3YyBcdWM4MDFcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NDAgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjMjJiXHVjNzkwXHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2YwIFx1YjJlNFx1Yzc0YyBcdWQwZGNcdWMxMWRcdWM3NzRcdWIyOTQgXHViMmU0XHViOTc4IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWMyMThcdWM1ZjQgQVx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjMTI0XHViYTg1XHVjNzQ0IE1cdWFjMWMgXHVjODAxXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjMTI0XHViYTg1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVkMGRjXHViODVjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIHggeSB2IC0geFx1YmM4OFx1YzlmOCBcdWMyMThcdWJkODBcdWQxMzAsIHlcdWJjODhcdWM5ZjggXHVjMjE4IFx1YzkxMSBcdWM4MWNcdWM3N2MgXHVkMDcwIFx1YWMxMlx1Yzc0MCB2PFwvbGk+XHJcblx0PGxpPjIgeCB5IHYgLSB4XHViYzg4XHVjOWY4IFx1YzIxOFx1YmQ4MFx1ZDEzMCwgeVx1YmM4OFx1YzlmOCBcdWMyMTggXHVjOTExIFx1YzgxY1x1Yzc3YyBcdWM3OTFcdWM3NDAgXHVhYzEyXHVjNzQwIHY8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWQwZGNcdWMxMWRcdWM3NzRcdWIyOTQgXHVjMTI0XHViYTg1XHViOWNjIFx1YzgwMVx1Yzc0MCBcdWM4ODVcdWM3NzRcdWI5N2MgXHViY2Y0XHVjMTMxXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzhmY1x1YzVjOFx1YjJlNC4gXHViY2Y0XHVjMTMxXHVjNzc0XHViMjk0IE1cdWFjMWNcdWM3NTggXHVjMTI0XHViYTg1XHViOWNjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWQwZGNcdWMxMWRcdWM3NzRcdWFjMDAgXHVjNmQwXHViNzk4IFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWRlXHVjZDk0XHVjNWI0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+TVx1YWMxY1x1Yzc1OCBcdWMxMjRcdWJhODVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMGRjXHVjMTFkXHVjNzc0XHVhYzAwIFx1YzZkMFx1Yjc5OCBcdWM4MDFcdWM3NDAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YWQ2Y1x1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMjE4XHVjNWY0XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxYyBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIFx1YzEyNFx1YmE4NVx1Yzc1OCBcdWFjMWNcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJmx0Oz1OJmx0Oz0yMDAsIDAmbHQ7PU0mbHQ7PTQwLDAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwZGNcdWMxMWRcdWM3NzRcdWM3NTggXHVjMTI0XHViYTg1XHVjNzc0IFx1YmIzOFx1YzgxYyBcdWMxMjRcdWJhODVcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQwZGNcdWMxMWRcdWM3NzRcdWFjMDAgXHVjNmQwXHViNzk4IFx1YzgwMVx1Yzc0MCBcdWMyMTggTlx1YWMxY1x1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1ZDBkY1x1YzExZFx1Yzc3NFx1Yzc1OCBcdWMxMjRcdWJhODVcdWFjZmMgXHVjNzdjXHVjZTU4XHVkNTU4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3ODciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJTkZPUk1BQ0lKRSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gd2FzIGJvcmVkLCBzbyBoZSB0b29rIGEgcGllY2Ugb2YgcGFwZXIgYW5kIHdyb3RlIGRvd24gYSBzZXF1ZW5jZSBBIG9mIGxlbmd0aCBOLCB3aGljaCBjb250YWlucyBlYWNoIHBvc2l0aXZlIGludGVnZXIgYmV0d2VlbiAxIGFuZCBOLCBpbmNsdXNpdmUsIGV4YWN0bHkgb25jZS4gQWZ0ZXIgdGhhdCwgaGUgdG9vayBhbm90aGVyIHBpZWNlIG9mIHBhcGVyIGFuZCB3cm90ZSBkb3duIE0gZGVzY3JpcHRpb25zIG9mIHRoZSBzZXF1ZW5jZSBBLjxcL3A+XHJcblxyXG48cD5FYWNoIGRlc2NyaXB0aW9uIGhhcyBvbmUgb2YgdGhlIGZvbGxvd2luZyBmb3JtYXRzOjxcL3A+XHJcblxyXG48cD4xIHggeSB2ICZuZGFzaDsgdGhlIGxhcmdlc3QgbnVtYmVyIGluIHBvc2l0aW9ucyBiZXR3ZWVuIHggYW5kIHkgKGluY2x1c2l2ZSkgZXF1YWxzIHY8YnIgXC8+XHJcbjIgeCB5IHYgJm5kYXNoOyB0aGUgc21hbGxlc3QgbnVtYmVyIGluIHBvc2l0aW9ucyBiZXR3ZWVuIHggYW5kIHkgKGluY2x1c2l2ZSkgZXF1YWxzIHY8XC9wPlxyXG5cclxuPHA+VGhlbiBTbGF2a28gY2FtZSwgc2F3LCBhbmQgc3RvbGUgdGhlIGZpcnN0IHBhcGVyLiBNaXJrbyBpcyBkZXNwZXJhdGUgYW5kIGhhcyBhc2tlZCB5b3UgdG8gZmluZCBzb21lIHNlcXVlbmNlIG1hdGNoaW5nIHRoZSBkZXNjcmlwdGlvbnMsIG5vdCBuZWNlc3NhcmlseSBlcXVhbCB0byB0aGUgb3JpZ2luYWwgc2VxdWVuY2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMsIE4gKDEgJmxlOyBOICZsZTsgMjAwKSwgdGhlIGxlbmd0aCBvZiB0aGUgc2VxdWVuY2UsIGFuZCBNICgwICZsZTsgTSAmbGU7IDQwIDAwMCksIHRoZSBudW1iZXIgb2YgZGVzY3JpcHRpb25zLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyBhIGRlc2NyaXB0aW9uIGFzIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIGEgc2VxdWVuY2Ugb2YgTiBzcGFjZS1zZXBhcmF0ZWQgcG9zaXRpdmUgaW50ZWdlcnMgKG1hdGNoaW5nIHRoZSBkZXNjcmlwdGlvbnMgYW5kIGNvbnRhaW5pbmcgYWxsIHBvc2l0aXZlIGludGVnZXJzIGZyb20gMSB0byBOKSwgb3IgLTEgaWYgbm8gc3VjaCBzZXF1ZW5jZSBleGlzdHMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d