시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 106 16 9 20.000%

문제

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

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

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

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

위의 그림은 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
W3sicHJvYmxlbV9pZCI6IjI0MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIxOFx1YzJlZFx1YjE0NFx1YWMwNCBcdWMxOGNcdWQ1MDRcdWQyYjhcdWM2ZThcdWM1YjQgXHVjNWQ0XHVjOWMwXHViMmM4XHVjNWI0XHViODVjIFx1Yzc3Y1x1ZDU3NFx1YzYyOCBcdWJjMzFcdWMyYjlcdWQ2NThcdWM3NDAgXHVjNzc0XHVjODFjIFx1YzgwNFx1ZDYwMCBcdWIyZTRcdWI5NzggXHVjNzdjXHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1Yzc3Y1x1Yzc5MFx1YjlhY1x1Yjk3YyBcdWMwYjRcdWQzYjRcdWJjZjRcdWFjZTAgXHVjNzg4XHVjNWM4XHVhY2UwLCBcdWMyYjlcdWQ2NThcdWM3NzRcdWM3NTggXHViMjA4XHVjNzQ0IFx1YzBhY1x1Yjg1Y1x1YzdhMVx1Yzc0MCBcdWM5YzFcdWM1YzVcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YzVjOFx1YzczY1x1YjJjOCZoZWxsaXA7IFx1YWRmOFx1YWM4M1x1Yzc0MCBcdWM1OTFcdWMyZGRcdWM1YzVcdWM3NzRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYyNFx1YjI5OFx1Yzc0MCBcdWMyYjlcdWQ2NThcdWM3NzRcdWFjMDAgXHVjZDljXHVhZGZjXHVkNTVjIFx1Y2NhYiBcdWIwYTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJiOVx1ZDY1OFx1Yzc3NFx1Yzc1OCBcdWMwYzFcdWMwYWMgXHVhZGRjXHVkNjA0XHVjNzc0XHViMjk0IFx1Yzc3NFx1YmJmOCBcdWMyYjlcdWQ2NThcdWM3NzRcdWFjMDAgXHVkNTYwIFx1Yzc3Y1x1Yzc0NCBcdWM4MTVcdWQ1NzRcdWIxOTNcdWM1NThcdWIyZTQuIFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YjI5NCBcdWM4MDBcdWMyMThcdWM5YzAgXHVkNTU4XHViMDk4XHViOTdjIFx1YjJlNFx1Yjk3OCBcdWFjODNcdWI0ZTRcdWI4NWMgXHViZDgwXHVkMTMwIFx1YWNhOVx1YjlhY1x1YzJkY1x1Y2YxY1x1YzU3YyBcdWQ1NWNcdWIyZTQuXHViMmU0XHVjNzRjXHVjNzQwIFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjODAwXHVjMjE4XHVjOWMwXHViMjk0IFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWMyMThcdWI4NWNcdWI4NWMgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWMyMThcdWI4NWNcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWI0NTAgXHViYjM4XHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YzIxOFx1Yjg1Y1x1YjI5NCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YjJlYlx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmIzOFx1Yzc0MCBcdWMyYTRcdWM3MDRcdWNlNThcdWI4NWMgXHVjNzkxXHViM2Q5XHVkNTVjXHViMmU0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWIyOTQgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc0NCBcdWM3OTFcdWIzZDlcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYywgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1Yzc0MCBcdWM2MjRcdWM5YzEgXHViMmU4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWI4NWNcdWI5Y2MgXHVjNzkxXHViM2Q5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWI4NWMgXHVjNWI0XHViNWE0IFx1YzIxOFx1Yjg1Y1x1Yzc1OCBcdWI0NTAgXHViYjM4XHVjNzQ0IFx1Yzc5MVx1YjNkOSBcdWMyZGNcdWQwYTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMDk4LCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzkxXHViM2Q5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzc0Jm5ic3A7XHVjNWM2XHViMjk0IFx1YWM4M1x1YjNjNCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQ8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBoZWlnaHQ9XCIzODlcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwNVwvU2NyZWVuIHNob3QgMjAxMS0wNS0wOSBhdCAxMV80OV8wNiBQTS5wbmdcIiB3aWR0aD1cIjI5N1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGxlZnQ7XCI+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCAzXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjg1Y1x1YzY0MCAyXHVhYzFjXHVjNzU4IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyYTRcdWM3MDRcdWNlNThcdWIyOTQgXHViMmU0XHVjNzRjIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1IFx1YzkxMVx1Yzc1OCBcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YmIzOFx1Yzc0NCBcdWM3OTFcdWIzZDkgXHVjMmRjXHVkMGE4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWNmMWNcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YmIzOFx1Yzc3NCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWFjZTAsIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFlYmNcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YmIzOFx1Yzc3NCBcdWIyZWJcdWQ2MDBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWNmMWNcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YmIzOFx1Yzc3NCBcdWIyZWJcdWQ2MDBcdWM3ODhcdWFjZTAsIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFlYmNcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YmIzOFx1Yzc3NCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBsZWZ0O1wiPlx1YzJiOVx1ZDY1OFx1Yzc3NFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzg3MFx1YWUwOCBcdWIxODBcdWIyZTRcdWFjMDAsIFx1YzljMFx1YWUwOFx1YWU0Y1x1YzljMCBcdWMyMThcdWMyZWRcdWIxNDRcdWFjMDQgXHVjNzdjXHVkNTc0XHVjNjI4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWMyYTRcdWQwYWNcdWM3NDQgXHVjNWVjXHVhZTMwXHVjNWQwIFx1YzgwMVx1YzZhOVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWM1NGNcdWM1NThcdWIyZTQuIFx1YmIzOFx1YWNmYyBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDRcdWM3NTggXHVjNWYwXHVhY2IwIFx1YzEyNFx1YzgxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjMjE4XHViODVjXHViOTdjIFx1YjJlYlx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTVjXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI5Y2NcdWM1N2QsIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgXHVhYzAxIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWNmMWNcdWM4MzhcdWM1N2NcdWQ1NThcdWIyOTRcdWM5YzAsIFx1YWViY1x1YzgzOFx1YzU3Y1x1ZDU1OFx1YjI5NFx1YzljMCwgXHVjMGMxXHVkMGRjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOCBOICgxICZsZTsgTiAmbGU7IDI1MCwwMDApXHVhY2ZjIFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMTggTSAoMSAmbGU7IE0gJmxlOyA1MDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YzIxOFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMThcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IDRcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIGEsIHM8c3ViPmE8XC9zdWI+LCBiLCBzPHN1Yj5iPFwvc3ViPlx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIGFcdWM2NDAgYiAoMSAmbGU7IGEsIGIgJmxlOyBtKVx1Yzc0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHViYjM4XHVjNzQ0IFx1Yzc5MVx1YjNkOVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWM3NzRcdWIyZTQuIHM8c3ViPmE8XC9zdWI+XHVjNjQwIHM8c3ViPmI8XC9zdWI+XHViMjk0IDBcdWFjZmMgMSBcdWM5MTFcdWM3NTggXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LiBzPHN1Yj5pPFwvc3ViPlx1YWMwMCAwXHVjNzc0XHViYTc0LCBcdWMyYTRcdWM3MDRcdWNlNTggaVx1YWMwMCBcdWFlYmNcdWM4MzhcdWM1N2MgXHViYjM4XHVjNzc0IFx1YjJlYlx1ZDc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWFjZTAsIHM8c3ViPmk8XC9zdWI+XHVhYzAwIDFcdWM3NzRcdWJhNzQsIFx1YzJhNFx1YzcwNFx1Y2U1OCBpXHVhYzAwIFx1Y2YxY1x1YzgzOFx1YzU3YyBcdWJiMzhcdWM3NzQgXHViMmViXHVkNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJhYThcdWI0ZTAgXHVjMjE4XHViODVjXHViOTdjIFx1YjJlYlx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViYTc0LCBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCwgXHVhYzAxIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFlYmNcdWM4MzhcdWM1N2MgXHVkNTU4XHViYTc0IDBcdWM3NDQsIFx1Y2YxY1x1YzgzOFx1YzU3YyBcdWQ1NThcdWJhNzQgMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTc0LCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzIxOFx1Yjg1Y1x1Yjk3YyBcdWIyZWJcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgSU1QT1NTSUJMRVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQxNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhdGVzIiwiZGVzY3JpcHRpb24iOiI8cD5BZnRlciBtYW55IHllYXJzIG9mIHdvcmtpbmcgYXMgYSBzb2Z0d2FyZSBkZXZlbG9wZXIgeW91IGhhdmUgZGVjaWRlZCB0byB0cnkgc29tZXRoaW5nIGVudGlyZWx5IGRpXHVmYjAwZXJlbnQsIGFuZCBzdGFydGVkIGxvb2tpbmcgYXQgcmFuZG9tIGpvYiBvXHVmYjAwZXJzLiBUaGUgb25lIHRoYXQgcmVhbGx5IGNhdWdodCB5b3VyIGV5ZSB3YXMgYSBqb2IgaW4gXHVmYjAxc2ggZmFybWluZyAoYSBmb3JtIG9mIGFxdWFjdWx0dXJlKS4gJnJzcXVvO0Nvb2whJnJzcXVvOywgeW91IHRob3VnaHQsIGFuZCBiZXNpZGVzLCBcdWZiMDFzaCBhcmUgbmljZSBjcmVhdHVyZXMuIFNvIHlvdSBhcHBsaWVkLCBnb3QgYWNjZXB0ZWQsIGFuZCB0b2RheSBpcyB5b3VyIFx1ZmIwMXJzdCBkYXkgYXQgd29yay48XC9wPlxyXG5cclxuPHA+WW91ciBib3NzIGhhcyBhbHJlYWR5IGFzc2lnbmVkIHlvdSBhIHRhc2suIFlvdSBoYXZlIHRvIGlzb2xhdGUgb25lIHdhdGVyIHJlc2Vydm9pciBmcm9tIGFub3RoZXIuIEFmdGVyIGxvb2tpbmcgYXQgc29tZSBzY2hlbWVzIHlvdSZyc3F1bzt2ZSBiZWVuIGdpdmVuLCBoZXJlJnJzcXVvO3Mgd2hhdCB5b3UmcnNxdW87dmUgXHVmYjAxZ3VyZWQgb3V0LjxcL3A+XHJcblxyXG48cD5UaGUgdHdvIHdhdGVyIHJlc2Vydm9pcnMgYXJlIGNvbm5lY3RlZCBieSBzZXZlcmFsIGNoYW5uZWxzLiBFYWNoIGNoYW5uZWwgaGFzIHR3byBnYXRlcy4gVGhlIGNoYW5uZWwgaXMgb3BlbiB3aGVuIGJvdGggZ2F0ZXMgYXJlIG9wZW4sIGFuZCBpcyBjbG9zZWQgb3RoZXJ3aXNlLiBUaGUgZ2F0ZXMgYXJlIGNvbnRyb2xsZWQgdXNpbmcgc3dpdGNoZXMuIFRoZSBzYW1lIHN3aXRjaCBtYXkgb3BlcmF0ZSBzZXZlcmFsIGdhdGVzLCBidXQgZWFjaCBnYXRlIGlzIG9wZXJhdGVkIGJ5IGV4YWN0bHkgb25lIHN3aXRjaC4gSXQgaXMgcG9zc2libGUgdGhhdCBib3RoIGdhdGVzIG9uIGEgY2hhbm5lbCBhcmUgY29udHJvbGxlZCBieSB0aGUgc2FtZSBzd2l0Y2ggYW5kIHRoYXQgYSBzd2l0Y2ggY29udHJvbHMgbm8gZ2F0ZXMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDVcL1NjcmVlbiBzaG90IDIwMTEtMDUtMDkgYXQgMTFfNDlfMDYgUE0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6Mzg5cHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDoyOTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgc3dpdGNoIG1heSBvcGVyYXRlIHRoZSBnYXRlIGluIG9uZSBvZiB0d28gd2F5czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT50aGUgZ2F0ZSBpcyBvcGVuIHdoZW4gdGhlIHN3aXRjaCBpcyBvbiwgYW5kIGlzIGNsb3NlZCB3aGVuIHRoZSBzd2l0Y2ggaXMgb1x1ZmIwMCw8XC9saT5cclxuXHQ8bGk+dGhlIGdhdGUgaXMgY2xvc2VkIHdoZW4gdGhlIHN3aXRjaCBpcyBvbiwgYW5kIGlzIG9wZW4gd2hlbiB0aGUgc3dpdGNoIGlzIG9cdWZiMDAuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QWZ0ZXIgcGxheWluZyBhIGJpdCB3aXRoIHRoZSBzd2l0Y2hlcyB5b3Ugc3VkZGVubHkgcmVhbGl6ZSB0aGF0IHlvdXIgcHJvZ3JhbW1pbmcgZXhwZXJpZW5jZSB3aWxsIGNvbWUgaW4gdmVyeSBoYW5keS4gV3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSBjb25cdWZiMDFndXJhdGlvbiBvZiBnYXRlcyBhbmQgc3dpdGNoZXMsIGRldGVybWluZXMgd2hldGhlciBpdCBpcyBwb3NzaWJsZSB0byBjbG9zZSBhbGwgY2hhbm5lbHMsIGFuZCBpZiBpdCBpcywgdGhlbiBcdWZiMDFuZHMgYSBzdGF0ZSBvZiBldmVyeSBzd2l0Y2ggaW4gb25lIHN1Y2ggdmFsaWQgY29uXHVmYjAxZ3VyYXRpb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBuICggMSAmbGU7IG4gJmxlOyAyNTAgMDAwKSBhbmQgbSAoIDEgJmxlOyBtICZsZTsgNTAwIDAwMCksIHRoZSBudW1iZXIgb2YgY2hhbm5lbHMgYW5kIHN3aXRjaGVzIHJlc3BlY3RpdmVseS4gU3dpdGNoZXMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBtLiBBZGRpdGlvbmFsbHksIGluIHRlc3QgY2FzZXMgd29ydGggYXQgbGVhc3QgMzAlIHBvaW50cywgbiB3aWxsIG5vdCBleGNlZWQgNDAgYW5kIG0gd2lsbCBub3QgZXhjZWVkIDIwIC48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBuIGxpbmVzIGRlc2NyaWJlIGNoYW5uZWxzLCBlYWNoIGNoYW5uZWwgaXMgZGVzY3JpYmVkIGJ5IGEgc2VwYXJhdGUgbGluZSBjb250YWluaW5nIGZvdXIgaW50ZWdlcnM6IGEsIHM8c3ViPmE8XC9zdWI+LCBiLCBzPHN1Yj5iPFwvc3ViPi4gTnVtYmVycyBhIGFuZCBiIHJlcHJlc2VudCBzd2l0Y2hlcyAoMSAmbGU7IGEsIGIgJmxlOyBtKSB0aGF0IG9wZXJhdGUgZ2F0ZXMgb2YgdGhpcyBjaGFubmVsLiBOdW1iZXJzIHM8c3ViPmE8XC9zdWI+IGFuZCBzPHN1Yj5iPFwvc3ViPiBjYW4gYmUgZWl0aGVyIDAgb3IgMSBhbmQgY29ycmVzcG9uZCB0byB0aGUgZGVzY3JpYmVkIG9wZXJhdGlvbiBtb2RlczogczxzdWI+aTxcL3N1Yj4gPSAwIG1lYW5zIHRoYXQgdGhlIGdhdGUgaXMgY2xvc2VkIGlmIGFuZCBvbmx5IGlmIHRoZSBzd2l0Y2ggaSBpcyBvXHVmYjAwIGFuZCBzPHN1Yj5pPFwvc3ViPiA9IDEgbWVhbnMgdGhhdCB0aGUgZ2F0ZSBpcyBjbG9zZWQgaWYgYW5kIG9ubHkgaWYgdGhlIHN3aXRjaCBpIGlzIG9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIGl0IGlzIHBvc3NpYmxlIHRvIGNsb3NlIGFsbCB0aGUgY2hhbm5lbHMsIHRoZSBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gbSBsaW5lcy4gTGluZSBpIHNob3VsZCBjb250YWluIDAgLCBpZiBzd2l0Y2ggaSBzaG91bGQgYmUgb1x1ZmIwMCwgYW5kIDEgaWYgc3dpdGNoIGkgc2hvdWxkIGJlIG9uLiBJZiB0aGVyZSBhcmUgbWFueSBwb3NzaWJsZSBzb2x1dGlvbnMsIHlvdXIgcHJvZ3JhbSBtYXkgb3V0cHV0IGFueSBvZiB0aGVtLjxcL3A+XHJcblxyXG48cD5JZiBpdCBpcyBpbXBvc3NpYmxlIHRvIGNsb3NlIGFsbCBjaGFubmVscywgeW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgb25lIGxpbmUsIGNvbnRhaW5pbmcgYSBzaW5nbGUgd29yZCBJTVBPU1NJQkxFLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 3번

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