시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB390846024.096%

문제

수십년간 소프트웨어 엔지니어로 일해온 백승환은 이제 전혀 다른 일을 시작하기로 했다. 승환이는 여러 가지 일자리를 살펴보고 있었고, 승환이의 눈을 사로잡은 직업이 하나 있었으니… 그것은 양식업이었다.

오늘은 승환이가 출근한 첫 날이다.

승환이의 상사 규현이는 이미 승환이가 할 일을 정해놓았다. 승환이는 저수지 하나를 다른 것들로 부터 격리시켜야 한다.다음은 승환이가 생각한 방법이다.

두 저수지는 여러개의 수로로 서로 연결되어 있다. 각 수로에는 두 개의 문이 있다. 두 문이 모두 열려있으면, 수로는 열려있는 것이고, 그렇지 않으면 닫혀있는 것이다. 문은 스위치로 작동한다 하나의 스위치는 여러개의 문을 작동시킬 수 있지만, 각각의 문은 오직 단 하나의 스위치로만 작동시킬 수 있다. 하나의 스위치로 어떤 수로의 두 문을 작동 시키는 것이나, 스위치가 작동시킬 수 있는 문이 없는 것도 가능하다

위의 그림은 3개의 수로와 2개의 스위치가 있는 예이다.

스위치는 다음 두 가지 방법 중의 한 방법으로 문을 작동 시킨다.

  • 스위치가 켜져있으면, 문이 열려있고, 스위치가 꺼져있으면, 문이 닫혀있다.
  • 스위치가 켜져있으면, 문이 닫혀있고, 스위치가 꺼져있으면, 문이 열려있다.

승환이는 스위치를 가지고 조금 놀다가, 지금까지 수십년간 일해온 프로그래밍 스킬을 여기에 적용시킬 수 있다는 사실을 알았다. 문과 스위치간의 연결 설정이 주어졌을 때, 모든 수로를 닫는 것이 가능한지 구하는 프로그램을 작성하시오. 만약, 가능하다면, 각 스위치가 켜져야하는지, 꺼져야하는지, 상태를 출력한다.

입력

첫째 줄에 수로의 개수 N (1 ≤ N ≤ 250,000)과 스위치의 개수 M (1 ≤ M ≤ 500,000)이 주어진다. 둘째 줄부터 N개의 줄에 각 수로의 정보가 주어진다. 수로의 정보는 4개의 숫자로 이루어져 있고, a, sa, b, sb라고 한다. a와 b (1 ≤ a, b ≤ m)은 연결되어 문을 작동시키는 스위치이다. sa와 sb는 0과 1 중의 하나이다. si가 0이면, 스위치 i가 꺼져야 문이 닫히는 것이고, si가 1이면, 스위치 i가 켜져야 문이 닫히는 것이다.

출력

모든 수로를 닫는 것이 가능하면, m개의 줄에, 각 스위치가 꺼져야 하면 0을, 켜져야 하면 1을 출력한다. 여러 가지가 있으면, 아무거나 출력해도 된다.

모든 수로를 닫는 것이 불가능하다면, IMPOSSIBLE을 출력한다.

예제 입력 1

3 2
1 0 2 1
1 0 2 0
1 1 2 1

예제 출력 1

0
1

예제 입력 2

2 1
1 0 1 0
1 1 1 1

예제 출력 2

IMPOSSIBLE
W3sicHJvYmxlbV9pZCI6IjI0MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIxOFx1YzJlZFx1YjE0NFx1YWMwNCBcdWMxOGNcdWQ1MDRcdWQyYjhcdWM2ZThcdWM1YjQgXHVjNWQ0XHVjOWMwXHViMmM4XHVjNWI0XHViODVjIFx1Yzc3Y1x1ZDU3NFx1YzYyOCBcdWJjMzFcdWMyYjlcdWQ2NThcdWM3NDAgXHVjNzc0XHVjODFjIFx1YzgwNFx1ZDYwMCBcdWIyZTRcdWI5NzggXHVjNzdjXHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1Yzc3Y1x1Yzc5MFx1YjlhY1x1Yjk3YyBcdWMwYjRcdWQzYjRcdWJjZjRcdWFjZTAgXHVjNzg4XHVjNWM4XHVhY2UwLCBcdWMyYjlcdWQ2NThcdWM3NzRcdWM3NTggXHViMjA4XHVjNzQ0IFx1YzBhY1x1Yjg1Y1x1YzdhMVx1Yzc0MCBcdWM5YzFcdWM1YzVcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YzVjOFx1YzczY1x1YjJjOCZoZWxsaXA7IFx1YWRmOFx1YWM4M1x1Yzc0MCBcdWM1OTFcdWMyZGRcdWM1YzVcdWM3NzRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYyNFx1YjI5OFx1Yzc0MCBcdWMyYjlcdWQ2NThcdWM3NzRcdWFjMDAgXHVjZDljXHVhZGZjXHVkNTVjIFx1Y2NhYiBcdWIwYTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJiOVx1ZDY1OFx1Yzc3NFx1Yzc1OCBcdWMwYzFcdWMwYWMgXHVhZGRjXHVkNjA0XHVjNzc0XHViMjk0IFx1Yzc3NFx1YmJmOCBcdWMyYjlcdWQ2NThcdWM3NzRcdWFjMDAgXHVkNTYwIFx1Yzc3Y1x1Yzc0NCBcdWM4MTVcdWQ1NzRcdWIxOTNcdWM1NThcdWIyZTQuIFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YjI5NCBcdWM4MDBcdWMyMThcdWM5YzAgXHVkNTU4XHViMDk4XHViOTdjIFx1YjJlNFx1Yjk3OCBcdWFjODNcdWI0ZTRcdWI4NWMgXHViZDgwXHVkMTMwIFx1YWNhOVx1YjlhY1x1YzJkY1x1Y2YxY1x1YzU3YyBcdWQ1NWNcdWIyZTQuXHViMmU0XHVjNzRjXHVjNzQwIFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjODAwXHVjMjE4XHVjOWMwXHViMjk0IFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWMyMThcdWI4NWNcdWI4NWMgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWMyMThcdWI4NWNcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWI0NTAgXHViYjM4XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YzIxOFx1Yjg1Y1x1YjI5NCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YjJlYlx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmIzOFx1Yzc0MCBcdWMyYTRcdWM3MDRcdWNlNThcdWI4NWMgXHVjNzkxXHViM2Q5XHVkNTVjXHViMmU0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWIyOTQgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc0NCBcdWM3OTFcdWIzZDlcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYywgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1Yzc0MCBcdWM2MjRcdWM5YzEgXHViMmU4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWI4NWNcdWI5Y2MgXHVjNzkxXHViM2Q5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWI4NWMgXHVjNWI0XHViNWE0IFx1YzIxOFx1Yjg1Y1x1Yzc1OCBcdWI0NTAgXHViYjM4XHVjNzQ0IFx1Yzc5MVx1YjNkOSBcdWMyZGNcdWQwYTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMDk4LCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzkxXHViM2Q5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzc0Jm5ic3A7XHVjNWM2XHViMjk0IFx1YWM4M1x1YjNjNCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQ8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC82OGEyOTFjOC1kNTViLTQ2MmUtODM1OC1kZDdkMGRkZjBmZTBcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDE2OHB4OyBoZWlnaHQ6IDI1NnB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGxlZnQ7XCI+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCAzXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjg1Y1x1YzY0MCAyXHVhYzFjXHVjNzU4IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyYTRcdWM3MDRcdWNlNThcdWIyOTQgXHViMmU0XHVjNzRjIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1IFx1YzkxMVx1Yzc1OCBcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YmIzOFx1Yzc0NCBcdWM3OTFcdWIzZDkgXHVjMmRjXHVkMGE4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWNmMWNcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YmIzOFx1Yzc3NCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWFjZTAsIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFlYmNcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YmIzOFx1Yzc3NCBcdWIyZWJcdWQ2MDBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWNmMWNcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YmIzOFx1Yzc3NCBcdWIyZWJcdWQ2MDBcdWM3ODhcdWFjZTAsIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFlYmNcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YmIzOFx1Yzc3NCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBsZWZ0O1wiPlx1YzJiOVx1ZDY1OFx1Yzc3NFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzg3MFx1YWUwOCBcdWIxODBcdWIyZTRcdWFjMDAsIFx1YzljMFx1YWUwOFx1YWU0Y1x1YzljMCBcdWMyMThcdWMyZWRcdWIxNDRcdWFjMDQgXHVjNzdjXHVkNTc0XHVjNjI4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWMyYTRcdWQwYWNcdWM3NDQgXHVjNWVjXHVhZTMwXHVjNWQwIFx1YzgwMVx1YzZhOVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWM1NGNcdWM1NThcdWIyZTQuIFx1YmIzOFx1YWNmYyBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDRcdWM3NTggXHVjNWYwXHVhY2IwIFx1YzEyNFx1YzgxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjMjE4XHViODVjXHViOTdjIFx1YjJlYlx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTVjXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI5Y2NcdWM1N2QsIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgXHVhYzAxIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWNmMWNcdWM4MzhcdWM1N2NcdWQ1NThcdWIyOTRcdWM5YzAsIFx1YWViY1x1YzgzOFx1YzU3Y1x1ZDU1OFx1YjI5NFx1YzljMCwgXHVjMGMxXHVkMGRjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOCBOICgxICZsZTsgTiAmbGU7IDI1MCwwMDApXHVhY2ZjIFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMTggTSAoMSAmbGU7IE0gJmxlOyA1MDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YzIxOFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMThcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IDRcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIGEsIHM8c3ViPmE8XC9zdWI+LCBiLCBzPHN1Yj5iPFwvc3ViPlx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIGFcdWM2NDAgYiAoMSAmbGU7IGEsIGIgJmxlOyBtKVx1Yzc0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHViYjM4XHVjNzQ0IFx1Yzc5MVx1YjNkOVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWM3NzRcdWIyZTQuIHM8c3ViPmE8XC9zdWI+XHVjNjQwIHM8c3ViPmI8XC9zdWI+XHViMjk0IDBcdWFjZmMgMSBcdWM5MTFcdWM3NTggXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LiBzPHN1Yj5pPFwvc3ViPlx1YWMwMCAwXHVjNzc0XHViYTc0LCBcdWMyYTRcdWM3MDRcdWNlNTggaVx1YWMwMCBcdWFlYmNcdWM4MzhcdWM1N2MgXHViYjM4XHVjNzc0IFx1YjJlYlx1ZDc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWFjZTAsIHM8c3ViPmk8XC9zdWI+XHVhYzAwIDFcdWM3NzRcdWJhNzQsIFx1YzJhNFx1YzcwNFx1Y2U1OCBpXHVhYzAwIFx1Y2YxY1x1YzgzOFx1YzU3YyBcdWJiMzhcdWM3NzQgXHViMmViXHVkNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJhYThcdWI0ZTAgXHVjMjE4XHViODVjXHViOTdjIFx1YjJlYlx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViYTc0LCBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCwgXHVhYzAxIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFlYmNcdWM4MzhcdWM1N2MgXHVkNTU4XHViYTc0IDBcdWM3NDQsIFx1Y2YxY1x1YzgzOFx1YzU3YyBcdWQ1NThcdWJhNzQgMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTc0LCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzIxOFx1Yjg1Y1x1Yjk3YyBcdWIyZWJcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgSU1QT1NTSUJMRVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjQxNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhdGVzIiwiZGVzY3JpcHRpb24iOiI8cD5BZnRlciBtYW55IHllYXJzIG9mIHdvcmtpbmcgYXMgYSBzb2Z0d2FyZSBkZXZlbG9wZXIgeW91IGhhdmUgZGVjaWRlZCB0byB0cnkgc29tZXRoaW5nIGVudGlyZWx5IGRpXHVmYjAwZXJlbnQsIGFuZCBzdGFydGVkIGxvb2tpbmcgYXQgcmFuZG9tIGpvYiBvXHVmYjAwZXJzLiBUaGUgb25lIHRoYXQgcmVhbGx5IGNhdWdodCB5b3VyIGV5ZSB3YXMgYSBqb2IgaW4gXHVmYjAxc2ggZmFybWluZyAoYSBmb3JtIG9mIGFxdWFjdWx0dXJlKS4gJnJzcXVvO0Nvb2whJnJzcXVvOywgeW91IHRob3VnaHQsIGFuZCBiZXNpZGVzLCBcdWZiMDFzaCBhcmUgbmljZSBjcmVhdHVyZXMuIFNvIHlvdSBhcHBsaWVkLCBnb3QgYWNjZXB0ZWQsIGFuZCB0b2RheSBpcyB5b3VyIFx1ZmIwMXJzdCBkYXkgYXQgd29yay48XC9wPlxyXG5cclxuPHA+WW91ciBib3NzIGhhcyBhbHJlYWR5IGFzc2lnbmVkIHlvdSBhIHRhc2suIFlvdSBoYXZlIHRvIGlzb2xhdGUgb25lIHdhdGVyIHJlc2Vydm9pciBmcm9tIGFub3RoZXIuIEFmdGVyIGxvb2tpbmcgYXQgc29tZSBzY2hlbWVzIHlvdSZyc3F1bzt2ZSBiZWVuIGdpdmVuLCBoZXJlJnJzcXVvO3Mgd2hhdCB5b3UmcnNxdW87dmUgXHVmYjAxZ3VyZWQgb3V0LjxcL3A+XHJcblxyXG48cD5UaGUgdHdvIHdhdGVyIHJlc2Vydm9pcnMgYXJlIGNvbm5lY3RlZCBieSBzZXZlcmFsIGNoYW5uZWxzLiBFYWNoIGNoYW5uZWwgaGFzIHR3byBnYXRlcy4gVGhlIGNoYW5uZWwgaXMgb3BlbiB3aGVuIGJvdGggZ2F0ZXMgYXJlIG9wZW4sIGFuZCBpcyBjbG9zZWQgb3RoZXJ3aXNlLiBUaGUgZ2F0ZXMgYXJlIGNvbnRyb2xsZWQgdXNpbmcgc3dpdGNoZXMuIFRoZSBzYW1lIHN3aXRjaCBtYXkgb3BlcmF0ZSBzZXZlcmFsIGdhdGVzLCBidXQgZWFjaCBnYXRlIGlzIG9wZXJhdGVkIGJ5IGV4YWN0bHkgb25lIHN3aXRjaC4gSXQgaXMgcG9zc2libGUgdGhhdCBib3RoIGdhdGVzIG9uIGEgY2hhbm5lbCBhcmUgY29udHJvbGxlZCBieSB0aGUgc2FtZSBzd2l0Y2ggYW5kIHRoYXQgYSBzd2l0Y2ggY29udHJvbHMgbm8gZ2F0ZXMuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNjhhMjkxYzgtZDU1Yi00NjJlLTgzNTgtZGQ3ZDBkZGYwZmUwXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAxNjhweDsgaGVpZ2h0OiAyNTZweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIHN3aXRjaCBtYXkgb3BlcmF0ZSB0aGUgZ2F0ZSBpbiBvbmUgb2YgdHdvIHdheXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+dGhlIGdhdGUgaXMgb3BlbiB3aGVuIHRoZSBzd2l0Y2ggaXMgb24sIGFuZCBpcyBjbG9zZWQgd2hlbiB0aGUgc3dpdGNoIGlzIG9cdWZiMDAsPFwvbGk+XHJcblx0PGxpPnRoZSBnYXRlIGlzIGNsb3NlZCB3aGVuIHRoZSBzd2l0Y2ggaXMgb24sIGFuZCBpcyBvcGVuIHdoZW4gdGhlIHN3aXRjaCBpcyBvXHVmYjAwLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFmdGVyIHBsYXlpbmcgYSBiaXQgd2l0aCB0aGUgc3dpdGNoZXMgeW91IHN1ZGRlbmx5IHJlYWxpemUgdGhhdCB5b3VyIHByb2dyYW1taW5nIGV4cGVyaWVuY2Ugd2lsbCBjb21lIGluIHZlcnkgaGFuZHkuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgY29uXHVmYjAxZ3VyYXRpb24gb2YgZ2F0ZXMgYW5kIHN3aXRjaGVzLCBkZXRlcm1pbmVzIHdoZXRoZXIgaXQgaXMgcG9zc2libGUgdG8gY2xvc2UgYWxsIGNoYW5uZWxzLCBhbmQgaWYgaXQgaXMsIHRoZW4gXHVmYjAxbmRzIGEgc3RhdGUgb2YgZXZlcnkgc3dpdGNoIGluIG9uZSBzdWNoIHZhbGlkIGNvblx1ZmIwMWd1cmF0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgbiAoIDEgJmxlOyBuICZsZTsgMjUwIDAwMCkgYW5kIG0gKCAxICZsZTsgbSAmbGU7IDUwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGNoYW5uZWxzIGFuZCBzd2l0Y2hlcyByZXNwZWN0aXZlbHkuIFN3aXRjaGVzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbS4gQWRkaXRpb25hbGx5LCBpbiB0ZXN0IGNhc2VzIHdvcnRoIGF0IGxlYXN0IDMwJSBwb2ludHMsIG4gd2lsbCBub3QgZXhjZWVkIDQwIGFuZCBtIHdpbGwgbm90IGV4Y2VlZCAyMCAuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbiBsaW5lcyBkZXNjcmliZSBjaGFubmVscywgZWFjaCBjaGFubmVsIGlzIGRlc2NyaWJlZCBieSBhIHNlcGFyYXRlIGxpbmUgY29udGFpbmluZyBmb3VyIGludGVnZXJzOiBhLCBzPHN1Yj5hPFwvc3ViPiwgYiwgczxzdWI+YjxcL3N1Yj4uIE51bWJlcnMgYSBhbmQgYiByZXByZXNlbnQgc3dpdGNoZXMgKDEgJmxlOyBhLCBiICZsZTsgbSkgdGhhdCBvcGVyYXRlIGdhdGVzIG9mIHRoaXMgY2hhbm5lbC4gTnVtYmVycyBzPHN1Yj5hPFwvc3ViPiBhbmQgczxzdWI+YjxcL3N1Yj4gY2FuIGJlIGVpdGhlciAwIG9yIDEgYW5kIGNvcnJlc3BvbmQgdG8gdGhlIGRlc2NyaWJlZCBvcGVyYXRpb24gbW9kZXM6IHM8c3ViPmk8XC9zdWI+ID0gMCBtZWFucyB0aGF0IHRoZSBnYXRlIGlzIGNsb3NlZCBpZiBhbmQgb25seSBpZiB0aGUgc3dpdGNoIGkgaXMgb1x1ZmIwMCBhbmQgczxzdWI+aTxcL3N1Yj4gPSAxIG1lYW5zIHRoYXQgdGhlIGdhdGUgaXMgY2xvc2VkIGlmIGFuZCBvbmx5IGlmIHRoZSBzd2l0Y2ggaSBpcyBvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiBpdCBpcyBwb3NzaWJsZSB0byBjbG9zZSBhbGwgdGhlIGNoYW5uZWxzLCB0aGUgc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb250YWluIG0gbGluZXMuIExpbmUgaSBzaG91bGQgY29udGFpbiAwICwgaWYgc3dpdGNoIGkgc2hvdWxkIGJlIG9cdWZiMDAsIGFuZCAxIGlmIHN3aXRjaCBpIHNob3VsZCBiZSBvbi4gSWYgdGhlcmUgYXJlIG1hbnkgcG9zc2libGUgc29sdXRpb25zLCB5b3VyIHByb2dyYW0gbWF5IG91dHB1dCBhbnkgb2YgdGhlbS48XC9wPlxyXG5cclxuPHA+SWYgaXQgaXMgaW1wb3NzaWJsZSB0byBjbG9zZSBhbGwgY2hhbm5lbHMsIHlvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IG9uZSBsaW5lLCBjb250YWluaW5nIGEgc2luZ2xlIHdvcmQgSU1QT1NTSUJMRS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: leejseo
  • 잘못된 데이터를 찾은 사람: WeissBlume