시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 128 MB326538.462%

문제

보섭이는 컴퓨터 구조와 논리 숙제로 작은 프로세서를 디자인했다. 이 프로세서는 총 N개의 레지스터를 가지고 있고, 1번부터 N번까지 번호가 매겨져 있다. 각 레지스터는 unsigned 32비트 정수를 일반적인 이진수 형태로 저장하고 있다. (0 ~ 232-1) 프로세서는 다음과 같은 두 가지 명령을 수행할 수 있다.

명령어 설명 예제
1 K M 레지스터 K에 저장되어 있는 비트를 M만큼 오른쪽으로 회전시킨다음 다시 K에 저장한다. 00000000000000000010001111111011 → (M = 1010) → 11111110110000000000000000001000
(10진법: 9211 → (M = 10) → 4273995784)
2 K L 레지스터 KL에 저장되어 있는 값을 XOR시킨 다음, 시스템 버스로 결과를 출력한다. 00000000000000000000001111000111 XOR 00000000000001111100000000000111 = 00000000000001111100001111000000
(10진법: 967 XOR 507911 = 508864)

보섭이는 이미 프로세서를 만들었다. 하지만, 가장 중요한 연산인 레지스터에 저장된 값을 읽는 명령을 만들지 않았다는 사실을 알게 되었다. 특정 레지스터에 저장된 값을 알기 위해서는 1번과 2번 연산을 적절히 수행해서 알아내는 방법밖에 없다. 보섭이가 명령을 수행시킨 순서와 2번 연산의 출력값이 주어졌을 때, 처음에 레지스터에 저장되어 있는 값을 구하는 프로그램을 작성하시오.

만약, 레지스터의 초기값이 여러 가지가 있다면, 사전순으로 가장 작은 것을 구한다.

입력

첫째 줄에 레지스터의 수 N과 프로세서가 수행한 명령의 수 E가 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ E ≤ 100,000)

다음 줄에는 프로세서가 수행한 연산이 하나씩 주어진다. 모든 명령은 올바른 명령이고 1 ≤ K, L ≤ N, 0 ≤ M < 32를 만족한다. 2번 명령이 주어진 경우에 다음 줄에는 시스템 버스가 출력한 결과가 10진수로 주어진다.

출력

첫째 줄에 N개 레지스터의 초기값을 공백으로 구분하여 1번 레지스터부터 출력한다.

만약, 그러한 결과를 출력하는 레지스터의 초기값이 없는 경우에는 -1을 출력한다.

예제 입력 1

3 3
2 1 2
1
2 1 3
2
2 2 3
3

예제 출력 1

0 1 2

예제 입력 2

4 6
2 4 2
3
2 4 1
6
1 3 1
2 3 1
2
1 2 2
2 2 3
7

예제 출력 2

5 0 14 3

예제 입력 3

5 6
2 4 2
10
2 5 3
2
2 2 3
1
2 1 4
3
1 3 1
2 3 4
2147483663

예제 출력 3

15 6 7 12 5
W3sicHJvYmxlbV9pZCI6IjMwODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MDRcdWI4NWNcdWMxMzhcdWMxMWMgXHViNTE0XHVjNzkwXHVjNzc4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjZjRcdWMxMmRcdWM3NzRcdWIyOTQgXHVjZWY0XHVkNGU4XHVkMTMwIFx1YWQ2Y1x1Yzg3MFx1YzY0MCBcdWIxN2NcdWI5YWMgXHVjMjE5XHVjODFjXHViODVjIFx1Yzc5MVx1Yzc0MCBcdWQ1MDRcdWI4NWNcdWMxMzhcdWMxMWNcdWI5N2MgXHViNTE0XHVjNzkwXHVjNzc4XHVkNTg4XHViMmU0LiBcdWM3NzQgXHVkNTA0XHViODVjXHVjMTM4XHVjMTFjXHViMjk0IFx1Y2QxZCBOXHVhYzFjXHVjNzU4IFx1YjgwOFx1YzljMFx1YzJhNFx1ZDEzMFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwLCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWIyOTQgdW5zaWduZWQgMzJcdWJlNDRcdWQyYjggXHVjODE1XHVjMjE4XHViOTdjIFx1Yzc3Y1x1YmMxOFx1YzgwMVx1Yzc3OCBcdWM3NzRcdWM5YzRcdWMyMTggXHVkNjE1XHVkMGRjXHViODVjIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuICgwIH4gMjxzdXA+MzI8XC9zdXA+LTEpIFx1ZDUwNFx1Yjg1Y1x1YzEzOFx1YzExY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHViYTg1XHViODM5XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MTAwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MTAlXCI+XHViYTg1XHViODM5XHVjNWI0PFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjI1JVwiPlx1YzEyNFx1YmE4NTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDo2NSVcIj5cdWM2MDhcdWM4MWM8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEgPHN0cm9uZz5LIE08XC9zdHJvbmc+PFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzAgPHN0cm9uZz5LPFwvc3Ryb25nPlx1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YmU0NFx1ZDJiOFx1Yjk3YyA8c3Ryb25nPk08XC9zdHJvbmc+XHViOWNjXHVkMDdjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYThcdWIyZTRcdWM3NGMgXHViMmU0XHVjMmRjIDxzdHJvbmc+SzxcL3N0cm9uZz5cdWM1ZDAgXHVjODAwXHVjN2E1XHVkNTVjXHViMmU0LjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAwMDAwMDAwMDAwMDAwMDAwMTAwMDExMTExMTEwMTEgJnJhcnI7ICg8c3Ryb25nPk08XC9zdHJvbmc+ID0gMTAxMCkgJnJhcnI7IDExMTExMTEwMTEwMDAwMDAwMDAwMDAwMDAwMDAxMDAwPGJyIFwvPlxyXG5cdFx0XHQoMTBcdWM5YzRcdWJjOTU6IDkyMTEgJnJhcnI7ICg8c3Ryb25nPk08XC9zdHJvbmc+ID0gMTApICZyYXJyOyA0MjczOTk1Nzg0KTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4yIDxzdHJvbmc+IEsgTDxcL3N0cm9uZz48XC90ZD5cclxuXHRcdFx0PHRkPlx1YjgwOFx1YzljMFx1YzJhNFx1ZDEzMCA8c3Ryb25nPks8XC9zdHJvbmc+XHVjNjQwIDxzdHJvbmc+TDxcL3N0cm9uZz5cdWM1ZDAgXHVjODAwXHVjN2E1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjMTJcdWM3NDQgWE9SXHVjMmRjXHVkMGE4IFx1YjJlNFx1Yzc0YywgXHVjMmRjXHVjMmE0XHVkMTVjIFx1YmM4NFx1YzJhNFx1Yjg1YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDAwMDAwMDAwMDAwMDAwMDAwMDAwMDExMTEwMDAxMTEgWE9SIDAwMDAwMDAwMDAwMDAxMTExMTAwMDAwMDAwMDAwMTExID0gMDAwMDAwMDAwMDAwMDExMTExMDAwMDExMTEwMDAwMDA8YnIgXC8+XHJcblx0XHRcdCgxMFx1YzljNFx1YmM5NTogOTY3IFhPUiA1MDc5MTEgPSA1MDg4NjQpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWJjZjRcdWMxMmRcdWM3NzRcdWIyOTQgXHVjNzc0XHViYmY4IFx1ZDUwNFx1Yjg1Y1x1YzEzOFx1YzExY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzAwXHVjN2E1IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWM1ZjBcdWMwYjBcdWM3NzggXHViODA4XHVjOWMwXHVjMmE0XHVkMTMwXHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWFjMTJcdWM3NDQgXHVjNzdkXHViMjk0IFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0XHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWM1NGNcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWQyYjlcdWM4MTUgXHViODA4XHVjOWMwXHVjMmE0XHVkMTMwXHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWFjMTJcdWM3NDQgXHVjNTRjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCAxXHViYzg4XHVhY2ZjIDJcdWJjODggXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWMyMThcdWQ1ODlcdWQ1NzRcdWMxMWMgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1YmMxNlx1YzVkMCBcdWM1YzZcdWIyZTQuIFx1YmNmNFx1YzEyZFx1Yzc3NFx1YWMwMCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjMjE4XHVkNTg5XHVjMmRjXHVkMGE4IFx1YzIxY1x1YzExY1x1YzY0MCAyXHViYzg4IFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWNkOWNcdWI4MjVcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YjgwOFx1YzljMFx1YzJhNFx1ZDEzMFx1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkLCBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWM3NTggXHVjZDA4XHVhZTMwXHVhYzEyXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0XHViYTc0LCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVkNTA0XHViODVjXHVjMTM4XHVjMTFjXHVhYzAwIFx1YzIxOFx1ZDU4OVx1ZDU1YyBcdWJhODVcdWI4MzlcdWM3NTggXHVjMjE4IEVcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxICZsZTsgRSAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTA0XHViODVjXHVjMTM4XHVjMTFjXHVhYzAwIFx1YzIxOFx1ZDU4OVx1ZDU1YyBcdWM1ZjBcdWMwYjBcdWM3NzQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YmE4NVx1YjgzOVx1Yzc0MCBcdWM2MmNcdWJjMTRcdWI5NzggXHViYTg1XHViODM5XHVjNzc0XHVhY2UwIDEgJmxlOyBLLCBMICZsZTsgTiwgMCAmbGU7IE0gJmx0OyAzMlx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuIDJcdWJjODggXHViYTg1XHViODM5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZGNcdWMyYTRcdWQxNWMgXHViYzg0XHVjMmE0XHVhYzAwIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWFjYjBcdWFjZmNcdWFjMDAgMTBcdWM5YzRcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWMxYyBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWM3NTggXHVjZDA4XHVhZTMwXHVhYzEyXHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgMVx1YmM4OCBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWJkODBcdWQxMzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QsIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YjgwOFx1YzljMFx1YzJhNFx1ZDEzMFx1Yzc1OCBcdWNkMDhcdWFlMzBcdWFjMTJcdWM3NzQgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA4MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBST0NFU09SIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgcmVjZWl2ZWQgYW4gaW50ZXJlc3RpbmcgaG9tZXdvcmsgYXNzaWdubWVudDogdG8gZGVzaWduIGhpcyBvd24gbGl0dGxlIHByb2Nlc3NvciAoTWlya29wcm9jZXNzb3IpLiBUaGUgcHJvY2Vzc29yIGhhcyBOIHJlZ2lzdGVycyB3aXRoIGluZGljZXMgZnJvbSAxIHRvIE4sIGFuZCBlYWNoIHJlZ2lzdGVyIGhvbGRzIG9uZSB1bnNpZ25lZCAzMi1iaXQgaW50ZWdlciBpbiB0aGUgdXN1YWwgYmluYXJ5IGZvcm1hdCAodGhlIHBvc3NpYmxlIHZhbHVlcyByYW5nZSBmcm9tIDAgdG8gMjxzdXA+MzI8XC9zdXA+IC0gMSkuPFwvcD5cclxuXHJcbjxwPlRoZSBwcm9jZXNzb3IgaXMgY2FwYWJsZSBvZiBleGVjdXRpbmcgdGhlIGZvbGxvd2luZyBpbnN0cnVjdGlvbiB0eXBlczo8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjEwMCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEwJVwiPkluc3RydWN0aW9uIHR5cGU8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MjUlXCI+RGVzY3JpcHRpb248XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6NjUlXCI+RXhhbXBsZTxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MSA8c3Ryb25nPksgTTxcL3N0cm9uZz48XC90ZD5cclxuXHRcdFx0PHRkPlJvdGF0ZSB0aGUgYml0cyBvZiByZWdpc3RlciBLIGJ5IE0gcG9zaXRpb25zIHRvIHRoZSByaWdodDsgd3JpdGUgdGhlIHJlc3VsdCBiYWNrIHRvIHJlZ2lzdGVyIEsuPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMDAwMDAwMDAwMDAwMDAwMDAxMDAwMTExMTExMTAxMSAmcmFycjsgKDxzdHJvbmc+TTxcL3N0cm9uZz4gPSAxMDEwKSAmcmFycjsgMTExMTExMTAxMTAwMDAwMDAwMDAwMDAwMDAwMDEwMDA8YnIgXC8+XHJcblx0XHRcdChpbiBiYXNlIDEwOiA5MjExICZyYXJyOyAoPHN0cm9uZz5NPFwvc3Ryb25nPiA9IDEwKSAmcmFycjsgNDI3Mzk5NTc4NCk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MiA8c3Ryb25nPiBLIEw8XC9zdHJvbmc+PFwvdGQ+XHJcblx0XHRcdDx0ZD5Db21wdXRlIHRoZSBiaXR3aXNlIFhPUiBvZiByZWdpc3RlcnMgSyBhbmQgTDsgb3V0cHV0IHRoZSByZXN1bHQgdG8gdGhlIHN5c3RlbSBidXMuPFwvdGQ+XHJcblx0XHRcdDx0ZD4wMDAwMDAwMDAwMDAwMDAwMDAwMDAwMTExMTAwMDExMSBYT1IgMDAwMDAwMDAwMDAwMDExMTExMDAwMDAwMDAwMDAxMTEgPSAwMDAwMDAwMDAwMDAwMTExMTEwMDAwMTExMTAwMDAwMDxiciBcLz5cclxuXHRcdFx0KGluIGJhc2UgMTA6IDk2NyBYT1IgNTA3OTExID0gNTA4ODY0KTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+TWlya28gaGFzIGFscmVhZHkgYnVpbHQgYSBtb2RlbCBvZiB0aGUgcHJvY2Vzc29yLCBhbmQgb25seSB0aGVuIHJlYWxpemVkIHRoYXQgaGUmIzM5O2QgZm9yZ290dGVuIHRvIGluY2x1ZGUgYW4gb3BlcmF0aW9uIHRvIHJlYWQgdGhlIGNvbnRlbnRzIG9mIGEgcmVnaXN0ZXIuIE5vdywgaGlzIG9ubHkgb3B0aW9uIGlzIHRvIGV4ZWN1dGUgYSBsYXJnZSBudW1iZXIgb2YgdHlwZSAxIGFuZCB0eXBlIDIgaW5zdHJ1Y3Rpb25zIGFuZCBpbmZlciB0aGUgcmVnaXN0ZXIgY29udGVudHMgZnJvbSB0aGUgcmVzdWx0cy4gSGF2aW5nIGV4ZWN1dGVkIGEgc2VxdWVuY2Ugb2YgY29tbWFuZHMsIGhlIGhhcyBhc2tlZCB5b3UgdG8gaGVscCBoaW0gZGVyaXZlIHRoZSBpbml0aWFsIHJlZ2lzdGVyIGNvbnRlbnRzIGNvbnNpc3RlbnQgd2l0aCB0aGUgb2J0YWluZWQgcmVzdWx0cy48XC9wPlxyXG5cclxuPHA+SWYgdGhlcmUgYXJlIG11bHRpcGxlIHBvc3NpYmlsaXRpZXMgZm9yIHRoZSBpbml0aWFsIHJlZ2lzdGVyIHN0YXRlIGNvbWJpbmF0aW9uLCBmaW5kIHRoZSBsZXhpY29ncmFwaGljYWxseSBzbWFsbGVzdCBvbmUuIChJZiB0d28gY29tYmluYXRpb25zIGhhdmUgZXF1YWwgdmFsdWVzIGluIHRoZSBmaXJzdCBLICZuZGFzaDsgMSByZWdpc3RlcnMgYW5kIGRpZmZlcmVudCB2YWx1ZXMgaW4gcmVnaXN0ZXIgSywgdGhlIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXIgY29tYmluYXRpb24gaXMgdGhlIG9uZSB3aXRoIHRoZSBzbWFsbGVyIHZhbHVlIGluIHJlZ2lzdGVyIEsuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzOiBOICgyICZsZTsgTiAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHJlZ2lzdGVycywgYW5kIEUgKDEgJmxlOyBFICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgZXhlY3V0ZWQgaW5zdHJ1Y3Rpb25zLjxcL3A+XHJcblxyXG48cD5UaGUgcmVtYWluaW5nIGlucHV0IGxpbmVzIGRlc2NyaWJlIHRoZSBpbnN0cnVjdGlvbnMgaW4gdGhlIG9yZGVyIHRoYXQgdGhleSB3ZXJlIGV4ZWN1dGVkIGJ5IE1pcmtvcHJvY2Vzc29yLCBmb3JtYXR0ZWQgYXMgZGVzY3JpYmVkIGluIHRoZSB0YWJsZSBhYm92ZSwgb25lIHBlciBsaW5lLiBBbGwgaW5zdHJ1Y3Rpb25zIGFyZSBsZWdhbCAodGhlIGZvbGxvd2luZyBjb25kaXRpb25zIGhvbGQ6IDEgJmxlOyBLLCBMICZsZTsgTiwgMCAmbGU7IE0gJmx0OyAzMikuIEVhY2ggaW5zdHJ1Y3Rpb24gb2YgdHlwZSAyIGlzIGZvbGxvd2VkIGJ5IGFub3RoZXIgbGluZSBjb250YWluaW5nIGEgcG9zaXRpdmUgaW50ZWdlciBiZXR3ZWVuIDAgYW5kIDI8c3VwPjMyPFwvc3VwPiAmbmRhc2g7IDEsIGluY2x1c2l2ZSAmbmRhc2g7IHRoZSByZXN1bHQgb2YgdGhhdCBvcGVyYXRpb24gKHRoZSBiaXR3aXNlIFhPUiB2YWx1ZSkgaW4gYmFzZSAxMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBOIHJlZ2lzdGVyIHZhbHVlcywgc2VwYXJhdGVkIGJ5IHNwYWNlcy48XC9wPlxyXG5cclxuPHA+SWYgdGhlcmUgaXMgbm8gcG9zc2libGUgY29tYmluYXRpb24gb2YgaW5pdGlhbCB2YWx1ZXMgY29uc2lzdGVudCB3aXRoIGlucHV0LCBvdXRwdXQgb25seSB0aGUgbnVtYmVyIC0xLCB0byBub3RpZnkgTWlya28gdGhhdCBoaXMgcHJvY2Vzc29yIGhhcyBhIGJ1Zy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #3 6번