시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 256 MB49212711732.773%

문제

린셰핑(Linköping)의 수도 시설은 복잡하다. 린셰핑 근교에는 지하수를 뽑는 수원지가 몇개 있다. 지하수는 파이프를 통해서 전달되는데, 파이프는 직선으로 한 수원지와 한 도시의 지점을 잇는다.

파이프의 지하 깊이는 모두 같아서. 두 파이프가 교차하면 교차점을 만든다. 교차점에서는 정확히 두개의 파이프만이 만남을 보장한다. 수원지는 교차점으로 치지 않으며, 수원지에서는 0개 이상의 파이프가 출발할 수 있다.

교차점에는 가끔 이물질이 막히는데, 이러한 이물질은 파이프에 큰 부담을 주어서 싱크홀 현상을 만든다. 최근 캠릿브지 대학의 연구에 의하면, 이러한 싱크홀을 본 린셰핑의 대학생들은 보통 인생의 회의를 느끼고, 공부를 그만두며, 결국 사회의 붕괴를 초래한다고 한다. 사회의 유지를 위해서, 린셰핑의 수도 시설 관리 기업인 Nordic Water Extraction and Redistribution Company (NWERC) 는 로봇을 설계했다. 로봇은 수원지에서 파이프로 집어넣을 수 있으며, 파이프를 한번 왔다갔다하면서 파이프에 있는 모든 교차점을 청소한다. 정부에서는, 교차점에서 로봇이 충돌하는 일을 막기 위해, 두 파이프가 만나는 교차점이 있다면, 오직 한 파이프만이 로봇을 포함할 수 있다는 규정을 만들었다.

파이프를 청소하는 동안에는 수도 시설이 닫힌다 (이것도 정부 규정이다). 고로, NWERC는 한번의 로봇 청소만으로 모든 파이프를 청소하고자 한다. 당신은, 어떠한 파이프의 부분집합에 동시에 로봇을 삽입해서, 로봇들이 모든 교차점을 청소하고, 두 로봇이 충돌하는 일이 없는지를 판별하여야 한다.

입력

입력은 다음과 같다.

  • 첫 번째 줄에는 w (1 ≤ w ≤ 1,000), p(1 ≤ p ≤ 1,000) 가 주어진다. w는 수원지의 개수, p는 파이프의 개수를 뜻한다.
  • 이후 w개의 줄에 xi and yi (−10 000 ≤ x, y ≤ 10 000) 가 주어진다. i번 수원지의 위치를 뜻한다. (수원지는 1부터 w까지 순서대로 번호가 붙어있다)
  • 이후 p개의 줄에 세 정수 s (1 ≤ s ≤ w), x, y (−10 000 ≤ x, y ≤ 10 000) 가 주어진다. 파이프가 s번 수원지에서 출발해서 (x, y)에서 종료함을 뜻한다.

각각의 파이프는 1개의 수원지(=시작점) 만을 포함하며, 3개 이상의 파이프가 만나는 모든 점은 수원지다. 두 파이프는 많아야 1개의 교점을 가지며, 교점은 파이프의 끝점에 있을 수도 있다. 모든 파이프의 길이는 0 초과이다.

출력

판별 결과에 따라 가능하면 "possible", 아니면 "impossible"을 출력한다.

예제 입력 1

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

예제 출력 1

impossible

예제 입력 2

2 3
0 0
0 10
1 5 15
1 2 15
2 10 10

예제 출력 2

possible
W3sicHJvYmxlbV9pZCI6IjExNjY4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMzBjXHVjNzc0XHVkNTA0IFx1Y2NhZFx1YzE4YyIsImRlc2NyaXB0aW9uIjoiPHA+XHViOWIwXHVjMTcwXHVkNTUxKExpbmsmb3VtbDtwaW5nKVx1Yzc1OCBcdWMyMThcdWIzYzQgXHVjMmRjXHVjMTI0XHVjNzQwIFx1YmNmNVx1YzdhMVx1ZDU1OFx1YjJlNC4gXHViOWIwXHVjMTcwXHVkNTUxIFx1YWRmY1x1YWQ1MFx1YzVkMFx1YjI5NCBcdWM5YzBcdWQ1NThcdWMyMThcdWI5N2MgXHViZjUxXHViMjk0IFx1YzIxOFx1YzZkMFx1YzljMFx1YWMwMCBcdWJhODdcdWFjMWMgXHVjNzg4XHViMmU0LiBcdWM5YzBcdWQ1NThcdWMyMThcdWIyOTQgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWM4MDRcdWIyZWNcdWI0MThcdWIyOTRcdWIzNzAsIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjI5NCBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVkNTVjIFx1YzIxOFx1YzZkMFx1YzljMFx1YzY0MCBcdWQ1NWMgXHViM2M0XHVjMmRjXHVjNzU4IFx1YzljMFx1YzgxMFx1Yzc0NCBcdWM3ODdcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWM5YzBcdWQ1NTggXHVhZTRhXHVjNzc0XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM1NDRcdWMxMWMuIFx1YjQ1MCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWFjMDAgXHVhZDUwXHVjYzI4XHVkNTU4XHViYTc0IFx1YWQ1MFx1Y2MyOFx1YzgxMFx1Yzc0NCBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YWQ1MFx1Y2MyOFx1YzgxMFx1YzVkMFx1YzExY1x1YjI5NCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViNDUwXHVhYzFjXHVjNzU4IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjljY1x1Yzc3NCBcdWI5Y2NcdWIwYThcdWM3NDQgXHViY2Y0XHVjN2E1XHVkNTVjXHViMmU0LiBcdWMyMThcdWM2ZDBcdWM5YzBcdWIyOTQgXHVhZDUwXHVjYzI4XHVjODEwXHVjNzNjXHViODVjIFx1Y2U1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YzIxOFx1YzZkMFx1YzljMFx1YzVkMFx1YzExY1x1YjI5NCAwXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWFjMDAgXHVjZDljXHViYzFjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWQ1MFx1Y2MyOFx1YzgxMFx1YzVkMFx1YjI5NCBcdWFjMDBcdWIwNTQgXHVjNzc0XHViYjNjXHVjOWM4XHVjNzc0IFx1YjljOVx1ZDc4OFx1YjI5NFx1YjM3MCwgXHVjNzc0XHViN2VjXHVkNTVjIFx1Yzc3NFx1YmIzY1x1YzljOFx1Yzc0MCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWM1ZDAgXHVkMDcwIFx1YmQ4MFx1YjJmNFx1Yzc0NCBcdWM4ZmNcdWM1YjRcdWMxMWMgXHVjMmYxXHVkMDZjXHVkNjQwIFx1ZDYwNFx1YzBjMVx1Yzc0NCBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1Y2Q1Y1x1YWRmYyBcdWNlYTBcdWI5YmZcdWJlMGNcdWM5YzAgXHViMzAwXHVkNTU5XHVjNzU4IFx1YzVmMFx1YWQ2Y1x1YzVkMCBcdWM3NThcdWQ1NThcdWJhNzQsIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWMyZjFcdWQwNmNcdWQ2NDBcdWM3NDQgXHViY2Y4IFx1YjliMFx1YzE3MFx1ZDU1MVx1Yzc1OCBcdWIzMDBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHViY2Y0XHVkMWI1IFx1Yzc3OFx1YzBkZFx1Yzc1OCBcdWQ2OGNcdWM3NThcdWI5N2MgXHViMjkwXHViMDdjXHVhY2UwLCBcdWFjZjVcdWJkODBcdWI5N2MgXHVhZGY4XHViOWNjXHViNDUwXHViYTcwLCBcdWFjYjBcdWFkNmQgXHVjMGFjXHVkNjhjXHVjNzU4IFx1YmQ5NVx1YWQzNFx1Yjk3YyBcdWNkMDhcdWI3OThcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiZuYnNwO1x1YzBhY1x1ZDY4Y1x1Yzc1OCBcdWM3MjBcdWM5YzBcdWI5N2MgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWI5YjBcdWMxNzBcdWQ1NTFcdWM3NTggXHVjMjE4XHViM2M0IFx1YzJkY1x1YzEyNCBcdWFkMDBcdWI5YWMgXHVhZTMwXHVjNWM1XHVjNzc4IE5vcmRpYyBXYXRlciBFeHRyYWN0aW9uIGFuZCBSZWRpc3RyaWJ1dGlvbiBDb21wYW55IChOV0VSQykgXHViMjk0IFx1Yjg1Y1x1YmQwN1x1Yzc0NCBcdWMxMjRcdWFjYzRcdWQ1ODhcdWIyZTQuIFx1Yjg1Y1x1YmQwN1x1Yzc0MCBcdWMyMThcdWM2ZDBcdWM5YzBcdWM1ZDBcdWMxMWMgXHVkMzBjXHVjNzc0XHVkNTA0XHViODVjIFx1YzlkMVx1YzViNFx1YjEyM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI5N2MgXHVkNTVjXHViYzg4IFx1YzY1NFx1YjJlNFx1YWMxNFx1YjJlNFx1ZDU1OFx1YmE3NFx1YzExYyBcdWQzMGNcdWM3NzRcdWQ1MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWFkNTBcdWNjMjhcdWM4MTBcdWM3NDQgXHVjY2FkXHVjMThjXHVkNTVjXHViMmU0LiBcdWM4MTVcdWJkODBcdWM1ZDBcdWMxMWNcdWIyOTQsIFx1YWQ1MFx1Y2MyOFx1YzgxMFx1YzVkMFx1YzExYyBcdWI4NWNcdWJkMDdcdWM3NzQgXHVjZGE5XHViM2NjXHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc0NCBcdWI5YzlcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWI0NTAgXHVkMzBjXHVjNzc0XHVkNTA0XHVhYzAwIFx1YjljY1x1YjA5OFx1YjI5NCBcdWFkNTBcdWNjMjhcdWM4MTBcdWM3NzQgXHVjNzg4XHViMmU0XHViYTc0LCBcdWM2MjRcdWM5YzEgXHVkNTVjIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjljY1x1Yzc3NCBcdWI4NWNcdWJkMDdcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhZGRjXHVjODE1XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1Y2NhZFx1YzE4Y1x1ZDU1OFx1YjI5NCBcdWIzZDlcdWM1NDhcdWM1ZDBcdWIyOTQgXHVjMjE4XHViM2M0IFx1YzJkY1x1YzEyNFx1Yzc3NCBcdWIyZWJcdWQ3OGNcdWIyZTQgKFx1Yzc3NFx1YWM4M1x1YjNjNCBcdWM4MTVcdWJkODAgXHVhZGRjXHVjODE1XHVjNzc0XHViMmU0KS4gXHVhY2UwXHViODVjLCBOV0VSQ1x1YjI5NCBcdWQ1NWNcdWJjODhcdWM3NTggXHViODVjXHViZDA3IFx1Y2NhZFx1YzE4Y1x1YjljY1x1YzczY1x1Yjg1YyBcdWJhYThcdWI0ZTAgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1Y2NhZFx1YzE4Y1x1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc0MCwgXHVjNWI0XHViNWEwXHVkNTVjIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWJkODBcdWJkODRcdWM5ZDFcdWQ1NjlcdWM1ZDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1Yjg1Y1x1YmQwN1x1Yzc0NCBcdWMwYmRcdWM3ODVcdWQ1NzRcdWMxMWMsIFx1Yjg1Y1x1YmQwN1x1YjRlNFx1Yzc3NCBcdWJhYThcdWI0ZTAgXHVhZDUwXHVjYzI4XHVjODEwXHVjNzQ0IFx1Y2NhZFx1YzE4Y1x1ZDU1OFx1YWNlMCwgXHViNDUwIFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWNkYTlcdWIzY2NcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzc0IFx1YzVjNlx1YjI5NFx1YzljMFx1Yjk3YyBcdWQzMTBcdWJjYzRcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgdyAoMSAmbGU7IHcgJmxlOyAxLDAwMCksIHAoMSAmbGU7IHAgJmxlOyAxLDAwMCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gd1x1YjI5NCBcdWMyMThcdWM2ZDBcdWM5YzBcdWM3NTggXHVhYzFjXHVjMjE4LCBwXHViMjk0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWQ2YzQgd1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgeDxzdWI+aTxcL3N1Yj4gYW5kIHk8c3ViPmk8XC9zdWI+ICgmbWludXM7MTAgMDAwICZsZTsgeCwgeSAmbGU7IDEwIDAwMCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaVx1YmM4OCBcdWMyMThcdWM2ZDBcdWM5YzBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YjczYlx1ZDU1Y1x1YjJlNC4gKFx1YzIxOFx1YzZkMFx1YzljMFx1YjI5NCAxXHViZDgwXHVkMTMwIHdcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyZTQpPFwvbGk+XHJcblx0PGxpPlx1Yzc3NFx1ZDZjNCBwXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4IHMgKDEgJmxlOyBzICZsZTsgdyksIHgsIHkgKCZtaW51czsxMCAwMDAgJmxlOyB4LCB5ICZsZTsgMTAgMDAwKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQzMGNcdWM3NzRcdWQ1MDRcdWFjMDAgc1x1YmM4OCBcdWMyMThcdWM2ZDBcdWM5YzBcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTc0XHVjMTFjICh4LCB5KVx1YzVkMFx1YzExYyBcdWM4ODVcdWI4Y2NcdWQ1NjhcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWIyOTQgMVx1YWMxY1x1Yzc1OCBcdWMyMThcdWM2ZDBcdWM5YzAoPVx1YzJkY1x1Yzc5MVx1YzgxMCkgXHViOWNjXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YmE3MCwgM1x1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVkMzBjXHVjNzc0XHVkNTA0XHVhYzAwIFx1YjljY1x1YjA5OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODEwXHVjNzQwIFx1YzIxOFx1YzZkMFx1YzljMFx1YjJlNC4gXHViNDUwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjI5NCBcdWI5Y2VcdWM1NDRcdWM1N2MgMVx1YWMxY1x1Yzc1OCBcdWFkNTBcdWM4MTBcdWM3NDQgXHVhYzAwXHVjOWMwXHViYTcwLCBcdWFkNTBcdWM4MTBcdWM3NDAgXHVkMzBjXHVjNzc0XHVkNTA0XHVjNzU4IFx1YjA1ZFx1YzgxMFx1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMCBcdWNkMDhcdWFjZmNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMzEwXHViY2M0IFx1YWNiMFx1YWNmY1x1YzVkMCBcdWI1MzBcdWI3N2MgXHVhYzAwXHViMmE1XHVkNTU4XHViYTc0ICZxdW90O3Bvc3NpYmxlJnF1b3Q7LCBcdWM1NDRcdWIyYzhcdWJhNzQgJnF1b3Q7aW1wb3NzaWJsZSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTE2NjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDbGVhbmluZyBQaXBlcyIsImRlc2NyaXB0aW9uIjoiPHA+TGluayZvdW1sO3BpbmcgaGFzIGEgcXVpdGUgY29tcGxleCB3YXRlciB0cmFuc3BvcnQgc3lzdGVtLiBBcm91bmQgTGluayZvdW1sO3BpbmcgdGhlcmUgYXJlIHNldmVyYWwgd2VsbHMgZnJvbSB3aGljaCB3YXRlciBpcyBkcmF3bi4gVGhlIHdhdGVyIGlzIHRoZW4gdHJhbnNwb3J0ZWQgdG8gb3RoZXIgbG9jYXRpb25zIHVzaW5nIHBpcGVzLiBFYWNoIHBpcGUgaXMgYSBzdHJhaWdodCBjYW5hbCBmcm9tIG9uZSBvZiB0aGUgd2VsbHMgdG8gc29tZSBsb2NhdGlvbiBpbiB0aGUgY2l0eS48XC9wPlxyXG5cclxuPHA+QWxsIHRoZSBwaXBlcyBhcmUgYXQgdGhlIHNhbWUgZGVwdGggdW5kZXIgZ3JvdW5kLiBUaGVyZWZvcmUsIHdoZW5ldmVyIHR3byBwaXBlcyBjcm9zcywgdGhleSBmb3JtIGFuIGludGVyc2VjdGlvbi4gTHVja2lseSB0aGUgcGlwZSBzeXN0ZW0gd2FzIGNvbnN0cnVjdGVkIGluIHN1Y2ggYSB3YXkgdGhhdCBleGFjdGx5IHR3byBwaXBlcyBtZWV0IGF0IGVhY2ggc3VjaCBpbnRlcnNlY3Rpb24uIFRoZSB3ZWxscyBkbyBub3QgY291bnQgYXMgaW50ZXJzZWN0aW9ucy4gQW55IG51bWJlciBvZiBwaXBlcyAoaW5jbHVkaW5nIHplcm8gb3IgbW9yZSB0aGFuIHR3bykgbWF5IG9yaWdpbmF0ZSBhdCBlYWNoIHdlbGwuPFwvcD5cclxuXHJcbjxwPlRoZSBpbnRlcnNlY3Rpb25zIHBvc2UgYSBwcm9ibGVtLCBzaW5jZSBkaXJ0IChhIG1peHR1cmUgb2YgbGltZSBhbmQgb3RoZXIgJmxkcXVvO3JlbWFpbnMmcmRxdW87KSB0ZW5kcyB0byBnZXQgc3R1Y2sgdGhlcmUuIFRoaXMgZGlydCBjYXVzZXMgdGhlIHBpcGVzIHRvIGRlZ3JhZGUgYW5kIGNvbGxhcHNlLCBsZWFkaW5nIHRvIHRoZSBmb3JtYXRpb24gb2YgbGFyZ2Ugc2luayBob2xlcy4gU3VjaCBzaW5rIGhvbGVzIGhhdmUgYSBtZXNtZXJpc2luZyBlZmZlY3Qgb24gdGhlIHN0dWRlbnRzIGluIExpbmsmb3VtbDtwaW5nLCBjYXVzaW5nIHRoZW0gdG8gbmVnbGVjdCB0aGVpciBzdHVkaWVzIGFuZCByZW1haW4gdW5lZHVjYXRlZCwgd2hpY2ggaW4gdGhlIGxvbmcgcnVuIHdpbGwgbGVhZCB0byBhIGNvbGxhcHNlIG9mIG5vdCBqdXN0IHRoZSBwaXBlIHN5c3RlbSBidXQgb2YgdGhlIHZlcnkgZmFicmljIG9mIHNvY2lldHkuIFRoZXJlZm9yZSBpdCBpcyBpbXBlcmF0aXZlIHRoYXQgdGhlIHBpcGVzIGFyZSByZWd1bGFybHkgY2xlYW5lZC4gVGhlIE5vcmRpYyBXYXRlciBFeHRyYWN0aW9uIGFuZCBSZWRpc3RyaWJ1dGlvbiBDb21wYW55IChOV0VSQykgJm5kYXNoOyB3aGljaCBpcyBpbiBjaGFyZ2Ugb2YgTGluayZvdW1sO3BpbmcmcnNxdW87cyB3YXRlcnBpcGVzICZuZGFzaDsgaGFzIGFuIGFtcGxlIGZsZWV0IG9mIHJvYm90cyB0byBwZXJmb3JtIHRoaXMgdGFzay4gQSByb2JvdCBjYW4gYmUgaW5zZXJ0ZWQgaW50byBhIHBpcGUgYXQgdGhlIHdlbGwgd2hlcmUgdGhlIHBpcGUgYmVnaW5zLiBUaGUgcm9ib3QgdGhlbiBnb2VzIHRocm91Z2ggdGhlIHBpcGUgYWxsIHRoZSB3YXkgdG8gaXRzIGVuZCBhbmQgY2xlYW5zIGFsbCBpbnRlcnNlY3Rpb25zIGFsb25nIHRoZSB3YXkuIEFmdGVyIHJlYWNoaW5nIHRoZSBlbmQsIHRoZSByb2JvdCB0dXJucyBhcm91bmQgYW5kIHJldHVybnMgYmFjayB0byB0aGUgd2VsbCB3aGVyZSBpdCBzdGFydGVkLiBJbiBvcmRlciB0byBwcmV2ZW50IHJvYm90IGNvbGxpc2lvbnMsIGdvdmVybm1lbnQgcmVndWxhdGlvbnMgc3RpcHVsYXRlIHRoYXQgd2hlbmV2ZXIgdHdvIHBpcGVzIGludGVyc2VjdCwgYXQgbW9zdCBvbmUgb2YgdGhlbSBtYXkgY29udGFpbiBhIHJvYm90LjxcL3A+XHJcblxyXG48cD5TaW5jZSB0aGUgd2hvbGUgd2F0ZXIgc3lzdGVtIGhhcyB0byBiZSBzaHV0IGRvd24gd2hpbGUgaXQgaXMgYmVpbmcgY2xlYW5lZCAoYW5vdGhlciBnb3Zlcm5tZW50IHJlZ3VsYXRpb24pLCB0aGUgTldFUkMgd291bGQgbGlrZSB0byBkbyB0aGUgY2xlYW5pbmcgcXVpY2tseSwgYnkgdXNpbmcgYSBzaW5nbGUgYmF0Y2ggb2YgY2xlYW5pbmcgcm9ib3RzLCBhbGwgc3RhcnRlZCBhdCB0aGUgc2FtZSB0aW1lLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gdmVyaWZ5IHdoZXRoZXIgdGhpcyBjYW4gYmUgZG9uZSAmbmRhc2g7IGkuZS4sIHdoZXRoZXIgd2UgY2FuIHNpbXVsdGFuZW91c2x5IGluc2VydCByb2JvdHMgaW50byBhIHN1YnNldCBvZiB0aGUgcGlwZXMgaW4gc3VjaCBhIHdheSB0aGF0IHRoZSByb2JvdHMgd2lsbCBjbGVhbiBhbGwgaW50ZXJzZWN0aW9ucyBhbmQgdGhlcmUgd2lsbCBiZSBubyByaXNrIG9mIHR3byByb2JvdHMgY29sbGlkaW5nLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIHcgKDEgJmxlOyB3ICZsZTsgMSAwMDApLCB0aGUgbnVtYmVyIG9mIHdlbGxzLCBhbmQgcCAoMSAmbGU7IHAgJmxlOyAxIDAwMCksIHRoZSBudW1iZXIgb2YgcGlwZXM7PFwvbGk+XHJcblx0PGxpPncgbGluZXMsIHRoZSBpdGggb2Ygd2hpY2ggY29udGFpbnMgdHdvIGludGVnZXJzIHg8c3ViPmk8XC9zdWI+IGFuZCB5PHN1Yj5pPFwvc3ViPiAoJm1pbnVzOzEwIDAwMCAmbGU7IHgsIHkgJmxlOyAxMCAwMDApLCB0aGUgcG9zaXRpb24gb2Ygd2VsbCBudW1iZXIgaSAodGhlIHdlbGxzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gdyk7PFwvbGk+XHJcblx0PGxpPnAgbGluZXMgZWFjaCB3aXRoIHRocmVlIGludGVnZXJzIHMgKDEgJmxlOyBzICZsZTsgdyksIHRoZSB3ZWxsIGF0IHdoaWNoIHRoZSBwaXBlIHN0YXJ0cywgYW5kIHggYW5kIHkgKCZtaW51czsxMCAwMDAgJmxlOyB4LCB5ICZsZTsgMTAgMDAwKSwgdGhlIHBvc2l0aW9uIGF0IHdoaWNoIHRoZSBwaXBlIGVuZHMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RWFjaCBwaXBlIHdpbGwgY29udGFpbiBleGFjdGx5IG9uZSB3ZWxsLCB0aGUgb25lIGF0IHdoaWNoIGl0IHN0YXJ0cy4gQW55IHBvaW50IHNoYXJlZCBieSBtb3JlIHRoYW4gdHdvIHBpcGVzIHdpbGwgYmUgYSB3ZWxsLiBBbnkgdHdvIHBpcGVzIHNoYXJlIGF0IG1vc3Qgb25lIGNvbW1vbiBwb2ludC4gVGhlIGNvbW1vbiBwb2ludCBvZiB0d28gcGlwZXMgbWF5IGJlIHRoZSBlbmRwb2ludCBvZiBvbmUgb3IgYm90aCBvZiB0aGVtLiBBbGwgcGlwZXMgaGF2ZSBwb3NpdGl2ZSBsZW5ndGguPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgaXQgaXMgcG9zc2libGUgdG8gY2xlYW4gYWxsIGludGVyc2VjdGlvbnMgYXMgZGVzY3JpYmVkIGFib3ZlLCBvdXRwdXQgJmxkcXVvO3Bvc3NpYmxlJnJkcXVvOy4gT3RoZXJ3aXNlLCBvdXRwdXQgJmxkcXVvO2ltcG9zc2libGUmcmRxdW87LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2015 C번

  • 문제를 번역한 사람: koosaga
  • 데이터를 추가한 사람: mym0404
  • 문제를 만든 사람: Gregor Behnke