시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjI0MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIxOFx1YzJlZFx1YjE0NFx1YWMwNCBcdWMxOGNcdWQ1MDRcdWQyYjhcdWM2ZThcdWM1YjQgXHVjNWQ0XHVjOWMwXHViMmM4XHVjNWI0XHViODVjIFx1Yzc3Y1x1ZDU3NFx1YzYyOCBcdWJjMzFcdWMyYjlcdWQ2NThcdWM3NDAgXHVjNzc0XHVjODFjIFx1YzgwNFx1ZDYwMCBcdWIyZTRcdWI5NzggXHVjNzdjXHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YjI5NCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzAgXHVjNzdjXHVjNzkwXHViOWFjXHViOTdjIFx1YzBiNFx1ZDNiNFx1YmNmNFx1YWNlMCBcdWM3ODhcdWM1YzhcdWFjZTAsIFx1YzJiOVx1ZDY1OFx1Yzc3NFx1Yzc1OCBcdWIyMDhcdWM3NDQgXHVjMGFjXHViODVjXHVjN2ExXHVjNzQwIFx1YzljMVx1YzVjNVx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjNzg4XHVjNWM4XHVjNzNjXHViMmM4JmhlbGxpcDsgXHVhZGY4XHVhYzgzXHVjNzQwIFx1YzU5MVx1YzJkZFx1YzVjNVx1Yzc3NFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViMjk4XHVjNzQwIFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YWMwMCBcdWNkOWNcdWFkZmNcdWQ1NWMgXHVjY2FiIFx1YjBhMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmI5XHVkNjU4XHVjNzc0XHVjNzU4IFx1YzBjMVx1YzBhYyBcdWFkZGNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVjNzc0XHViYmY4IFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YWMwMCBcdWQ1NjAgXHVjNzdjXHVjNzQ0IFx1YzgxNVx1ZDU3NFx1YjE5M1x1YzU1OFx1YjJlNC4gXHVjMmI5XHVkNjU4XHVjNzc0XHViMjk0IFx1YzgwMFx1YzIxOFx1YzljMCBcdWQ1NThcdWIwOThcdWI5N2MgXHViMmU0XHViOTc4IFx1YWM4M1x1YjRlNFx1Yjg1YyBcdWJkODBcdWQxMzAgXHVhY2E5XHViOWFjXHVjMmRjXHVjZjFjXHVjNTdjIFx1ZDU1Y1x1YjJlNC5cdWIyZTRcdWM3NGNcdWM3NDAgXHVjMmI5XHVkNjU4XHVjNzc0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWM4MDBcdWMyMThcdWM5YzBcdWIyOTQgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjg1Y1x1Yjg1YyBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzIxOFx1Yjg1Y1x1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWJiMzhcdWM3NzQgXHViYWE4XHViNDUwIFx1YzVmNFx1YjgyNFx1Yzc4OFx1YzczY1x1YmE3NCwgXHVjMjE4XHViODVjXHViMjk0IFx1YzVmNFx1YjgyNFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViMmViXHVkNjAwXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViYjM4XHVjNzQwIFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjg1YyBcdWM3OTFcdWIzZDlcdWQ1NWNcdWIyZTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NTggXHViYjM4XHVjNzQ0IFx1Yzc5MVx1YjNkOVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHVjOWMwXHViOWNjLCBcdWFjMDFcdWFjMDFcdWM3NTggXHViYjM4XHVjNzQwIFx1YzYyNFx1YzljMSBcdWIyZTggXHVkNTU4XHViMDk4XHVjNzU4IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjg1Y1x1YjljYyBcdWM3OTFcdWIzZDlcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHViMDk4XHVjNzU4IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjg1YyBcdWM1YjRcdWI1YTQgXHVjMjE4XHViODVjXHVjNzU4IFx1YjQ1MCBcdWJiMzhcdWM3NDQgXHVjNzkxXHViM2Q5IFx1YzJkY1x1ZDBhNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIwOTgsIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM3OTFcdWIzZDlcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3NzQmbmJzcDtcdWM1YzZcdWIyOTQgXHVhYzgzXHViM2M0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNDxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIGhlaWdodD1cIjM4OVwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA1XC9TY3JlZW4gc2hvdCAyMDExLTA1LTA5IGF0IDExXzQ5XzA2IFBNLnBuZ1wiIHdpZHRoPVwiMjk3XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogbGVmdDtcIj5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNzQwIDNcdWFjMWNcdWM3NTggXHVjMjE4XHViODVjXHVjNjQwIDJcdWFjMWNcdWM3NTggXHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJhNFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWIyZTRcdWM3NGMgXHViNDUwIFx1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTUgXHVjOTExXHVjNzU4IFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHViYjM4XHVjNzQ0IFx1Yzc5MVx1YjNkOSBcdWMyZGNcdWQwYThcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1Y2YxY1x1YzgzOFx1Yzc4OFx1YzczY1x1YmE3NCwgXHViYjM4XHVjNzc0IFx1YzVmNFx1YjgyNFx1Yzc4OFx1YWNlMCwgXHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1YWViY1x1YzgzOFx1Yzc4OFx1YzczY1x1YmE3NCwgXHViYjM4XHVjNzc0IFx1YjJlYlx1ZDYwMFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1Y2YxY1x1YzgzOFx1Yzc4OFx1YzczY1x1YmE3NCwgXHViYjM4XHVjNzc0IFx1YjJlYlx1ZDYwMFx1Yzc4OFx1YWNlMCwgXHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1YWViY1x1YzgzOFx1Yzc4OFx1YzczY1x1YmE3NCwgXHViYjM4XHVjNzc0IFx1YzVmNFx1YjgyNFx1Yzc4OFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGxlZnQ7XCI+XHVjMmI5XHVkNjU4XHVjNzc0XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjODcwXHVhZTA4IFx1YjE4MFx1YjJlNFx1YWMwMCwgXHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1YzIxOFx1YzJlZFx1YjE0NFx1YWMwNCBcdWM3N2NcdWQ1NzRcdWM2MjggXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1YzJhNFx1ZDBhY1x1Yzc0NCBcdWM1ZWNcdWFlMzBcdWM1ZDAgXHVjODAxXHVjNmE5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YzU1OFx1YjJlNC4gXHViYjM4XHVhY2ZjIFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWMwNFx1Yzc1OCBcdWM1ZjBcdWFjYjAgXHVjMTI0XHVjODE1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWMyMThcdWI4NWNcdWI5N2MgXHViMmViXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NWNcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjljY1x1YzU3ZCwgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0LCBcdWFjMDEgXHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1Y2YxY1x1YzgzOFx1YzU3Y1x1ZDU1OFx1YjI5NFx1YzljMCwgXHVhZWJjXHVjODM4XHVjNTdjXHVkNTU4XHViMjk0XHVjOWMwLCBcdWMwYzFcdWQwZGNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMThcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDEgJmxlOyBOICZsZTsgMjUwLDAwMClcdWFjZmMgXHVjMmE0XHVjNzA0XHVjZTU4XHVjNzU4IFx1YWMxY1x1YzIxOCBNICgxICZsZTsgTSAmbGU7IDUwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDEgXHVjMjE4XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzIxOFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgNFx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgYSwgczxzdWI+YTxcL3N1Yj4sIGIsIHM8c3ViPmI8XC9zdWI+XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gYVx1YzY0MCBiICgxICZsZTsgYSwgYiAmbGU7IG0pXHVjNzQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWJiMzhcdWM3NDQgXHVjNzkxXHViM2Q5XHVjMmRjXHVkMGE0XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yzc3NFx1YjJlNC4gczxzdWI+YTxcL3N1Yj5cdWM2NDAgczxzdWI+YjxcL3N1Yj5cdWIyOTQgMFx1YWNmYyAxIFx1YzkxMVx1Yzc1OCBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuIHM8c3ViPmk8XC9zdWI+XHVhYzAwIDBcdWM3NzRcdWJhNzQsIFx1YzJhNFx1YzcwNFx1Y2U1OCBpXHVhYzAwIFx1YWViY1x1YzgzOFx1YzU3YyBcdWJiMzhcdWM3NzQgXHViMmViXHVkNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCwgczxzdWI+aTxcL3N1Yj5cdWFjMDAgMVx1Yzc3NFx1YmE3NCwgXHVjMmE0XHVjNzA0XHVjZTU4IGlcdWFjMDAgXHVjZjFjXHVjODM4XHVjNTdjIFx1YmIzOFx1Yzc3NCBcdWIyZWJcdWQ3ODhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmFhOFx1YjRlMCBcdWMyMThcdWI4NWNcdWI5N2MgXHViMmViXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzQsIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwLCBcdWFjMDEgXHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1YWViY1x1YzgzOFx1YzU3YyBcdWQ1NThcdWJhNzQgMFx1Yzc0NCwgXHVjZjFjXHVjODM4XHVjNTdjIFx1ZDU1OFx1YmE3NCAxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3NCwgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWMyMThcdWI4NWNcdWI5N2MgXHViMmViXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQsIElNUE9TU0lCTEVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHYXRlcyIsImRlc2NyaXB0aW9uIjoiPHA+QWZ0ZXIgbWFueSB5ZWFycyBvZiB3b3JraW5nIGFzIGEgc29mdHdhcmUgZGV2ZWxvcGVyIHlvdSBoYXZlIGRlY2lkZWQgdG8gdHJ5IHNvbWV0aGluZyBlbnRpcmVseSBkaVx1ZmIwMGVyZW50LCBhbmQgc3RhcnRlZCBsb29raW5nIGF0IHJhbmRvbSBqb2Igb1x1ZmIwMGVycy4gVGhlIG9uZSB0aGF0IHJlYWxseSBjYXVnaHQgeW91ciBleWUgd2FzIGEgam9iIGluIFx1ZmIwMXNoIGZhcm1pbmcgKGEgZm9ybSBvZiBhcXVhY3VsdHVyZSkuICZyc3F1bztDb29sISZyc3F1bzssIHlvdSB0aG91Z2h0LCBhbmQgYmVzaWRlcywgXHVmYjAxc2ggYXJlIG5pY2UgY3JlYXR1cmVzLiBTbyB5b3UgYXBwbGllZCwgZ290IGFjY2VwdGVkLCBhbmQgdG9kYXkgaXMgeW91ciBcdWZiMDFyc3QgZGF5IGF0IHdvcmsuPFwvcD5cclxuXHJcbjxwPllvdXIgYm9zcyBoYXMgYWxyZWFkeSBhc3NpZ25lZCB5b3UgYSB0YXNrLiBZb3UgaGF2ZSB0byBpc29sYXRlIG9uZSB3YXRlciByZXNlcnZvaXIgZnJvbSBhbm90aGVyLiBBZnRlciBsb29raW5nIGF0IHNvbWUgc2NoZW1lcyB5b3UmcnNxdW87dmUgYmVlbiBnaXZlbiwgaGVyZSZyc3F1bztzIHdoYXQgeW91JnJzcXVvO3ZlIFx1ZmIwMWd1cmVkIG91dC48XC9wPlxyXG5cclxuPHA+VGhlIHR3byB3YXRlciByZXNlcnZvaXJzIGFyZSBjb25uZWN0ZWQgYnkgc2V2ZXJhbCBjaGFubmVscy4gRWFjaCBjaGFubmVsIGhhcyB0d28gZ2F0ZXMuIFRoZSBjaGFubmVsIGlzIG9wZW4gd2hlbiBib3RoIGdhdGVzIGFyZSBvcGVuLCBhbmQgaXMgY2xvc2VkIG90aGVyd2lzZS4gVGhlIGdhdGVzIGFyZSBjb250cm9sbGVkIHVzaW5nIHN3aXRjaGVzLiBUaGUgc2FtZSBzd2l0Y2ggbWF5IG9wZXJhdGUgc2V2ZXJhbCBnYXRlcywgYnV0IGVhY2ggZ2F0ZSBpcyBvcGVyYXRlZCBieSBleGFjdGx5IG9uZSBzd2l0Y2guIEl0IGlzIHBvc3NpYmxlIHRoYXQgYm90aCBnYXRlcyBvbiBhIGNoYW5uZWwgYXJlIGNvbnRyb2xsZWQgYnkgdGhlIHNhbWUgc3dpdGNoIGFuZCB0aGF0IGEgc3dpdGNoIGNvbnRyb2xzIG5vIGdhdGVzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA1XC9TY3JlZW4gc2hvdCAyMDExLTA1LTA5IGF0IDExXzQ5XzA2IFBNLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjM4OXB4OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6Mjk3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIHN3aXRjaCBtYXkgb3BlcmF0ZSB0aGUgZ2F0ZSBpbiBvbmUgb2YgdHdvIHdheXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+dGhlIGdhdGUgaXMgb3BlbiB3aGVuIHRoZSBzd2l0Y2ggaXMgb24sIGFuZCBpcyBjbG9zZWQgd2hlbiB0aGUgc3dpdGNoIGlzIG9cdWZiMDAsPFwvbGk+XHJcblx0PGxpPnRoZSBnYXRlIGlzIGNsb3NlZCB3aGVuIHRoZSBzd2l0Y2ggaXMgb24sIGFuZCBpcyBvcGVuIHdoZW4gdGhlIHN3aXRjaCBpcyBvXHVmYjAwLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFmdGVyIHBsYXlpbmcgYSBiaXQgd2l0aCB0aGUgc3dpdGNoZXMgeW91IHN1ZGRlbmx5IHJlYWxpemUgdGhhdCB5b3VyIHByb2dyYW1taW5nIGV4cGVyaWVuY2Ugd2lsbCBjb21lIGluIHZlcnkgaGFuZHkuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgY29uXHVmYjAxZ3VyYXRpb24gb2YgZ2F0ZXMgYW5kIHN3aXRjaGVzLCBkZXRlcm1pbmVzIHdoZXRoZXIgaXQgaXMgcG9zc2libGUgdG8gY2xvc2UgYWxsIGNoYW5uZWxzLCBhbmQgaWYgaXQgaXMsIHRoZW4gXHVmYjAxbmRzIGEgc3RhdGUgb2YgZXZlcnkgc3dpdGNoIGluIG9uZSBzdWNoIHZhbGlkIGNvblx1ZmIwMWd1cmF0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgbiAoIDEgJmxlOyBuICZsZTsgMjUwIDAwMCkgYW5kIG0gKCAxICZsZTsgbSAmbGU7IDUwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGNoYW5uZWxzIGFuZCBzd2l0Y2hlcyByZXNwZWN0aXZlbHkuIFN3aXRjaGVzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbS4gQWRkaXRpb25hbGx5LCBpbiB0ZXN0IGNhc2VzIHdvcnRoIGF0IGxlYXN0IDMwJSBwb2ludHMsIG4gd2lsbCBub3QgZXhjZWVkIDQwIGFuZCBtIHdpbGwgbm90IGV4Y2VlZCAyMCAuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbiBsaW5lcyBkZXNjcmliZSBjaGFubmVscywgZWFjaCBjaGFubmVsIGlzIGRlc2NyaWJlZCBieSBhIHNlcGFyYXRlIGxpbmUgY29udGFpbmluZyBmb3VyIGludGVnZXJzOiBhLCBzPHN1Yj5hPFwvc3ViPiwgYiwgczxzdWI+YjxcL3N1Yj4uIE51bWJlcnMgYSBhbmQgYiByZXByZXNlbnQgc3dpdGNoZXMgKDEgJmxlOyBhLCBiICZsZTsgbSkgdGhhdCBvcGVyYXRlIGdhdGVzIG9mIHRoaXMgY2hhbm5lbC4gTnVtYmVycyBzPHN1Yj5hPFwvc3ViPiBhbmQgczxzdWI+YjxcL3N1Yj4gY2FuIGJlIGVpdGhlciAwIG9yIDEgYW5kIGNvcnJlc3BvbmQgdG8gdGhlIGRlc2NyaWJlZCBvcGVyYXRpb24gbW9kZXM6IHM8c3ViPmk8XC9zdWI+ID0gMCBtZWFucyB0aGF0IHRoZSBnYXRlIGlzIGNsb3NlZCBpZiBhbmQgb25seSBpZiB0aGUgc3dpdGNoIGkgaXMgb1x1ZmIwMCBhbmQgczxzdWI+aTxcL3N1Yj4gPSAxIG1lYW5zIHRoYXQgdGhlIGdhdGUgaXMgY2xvc2VkIGlmIGFuZCBvbmx5IGlmIHRoZSBzd2l0Y2ggaSBpcyBvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiBpdCBpcyBwb3NzaWJsZSB0byBjbG9zZSBhbGwgdGhlIGNoYW5uZWxzLCB0aGUgc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb250YWluIG0gbGluZXMuIExpbmUgaSBzaG91bGQgY29udGFpbiAwICwgaWYgc3dpdGNoIGkgc2hvdWxkIGJlIG9cdWZiMDAsIGFuZCAxIGlmIHN3aXRjaCBpIHNob3VsZCBiZSBvbi4gSWYgdGhlcmUgYXJlIG1hbnkgcG9zc2libGUgc29sdXRpb25zLCB5b3VyIHByb2dyYW0gbWF5IG91dHB1dCBhbnkgb2YgdGhlbS48XC9wPlxyXG5cclxuPHA+SWYgaXQgaXMgaW1wb3NzaWJsZSB0byBjbG9zZSBhbGwgY2hhbm5lbHMsIHlvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IG9uZSBsaW5lLCBjb250YWluaW5nIGEgc2luZ2xlIHdvcmQgSU1QT1NTSUJMRS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 3번

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