시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 117 9 9 23.684%

문제

서울 내의 고속도로 도로망의 이용 요금이 빠르게 증가하고 있다. 때문에 최적의 경로를 찾는 것이 실제 문제로 제기되고 있다. 고속도로 도로망은 두 도시간의 양방향 도로들로 구성되어 있다. 각각의 도로에 대해 도로 이용요금과 도로를 지나가는데 걸리는 시간이 알려져 있다.

경로는 여행하는데 이용하는 도로들을 나열한 것을 의미한다. 경로상의 총 이동시간은 경로상의 도로들을 지나가는데 걸리는 시간의 합을 의미한다. 또한 경로상의 총 요금은 이동하는 도로들의 이용요금의 총합을 말한다. 그리고 경로상의 총 이용시간이 적을수록, 이용요금이 적을수록 더 좋은 경로가 된다. 즉, 어떤 경로가 다른 경로보다 좋다는 말은 이 경로가 다른 경로보다 빠르고 이용요금이 적다는 것을 의미한다. 우리는 어떠한 경로가 다른 어떤 경로보다도 좋은 경로일 때 이를 최적의 경로라 부른다. 하지만 항상 이러한 최적의 경로가 존재하는 것은 아니다.

예를 들어, 아래의 그림과 같은 고속도로 도로망이 있다고 하자. 각각의 도로는 요금과 이동하는데 걸리는 시간을 나타내는 한 쌍의 숫자로 구성되어진다,

그리고 도시 1에서 도시 4로 가는데는 총 4가지 경로가 존재한다. 4가지 경로에 대해 총 이동시간과 요금을 계산하여 보면 1-2-4(요금 4, 시간 5), 1-3-4(요금 4, 시간 5), 1-2-3-4(요금 6, 시간 4), 1-3-2-4(요금 4, 비용 10)이 된다.

그리고 여기서 경로 1-3-4와 1-2-4가 경로 1-3-2-4보다 좋은 것을 알 수 있다. 이 도로망에서는 효율적인 요금-시간 쌍이 두 가지 존재한다. 요금 4, 시간 5(경로 1-2-4, 1-3-4), 요금 6, 시간 4(경로 1-2-3-4). 만약 요금을 많이 내더라도 빠른 길을 원한다면 경로 1-2-3-4를 선택하면 되고 반대로 시간은 조금 더 걸리더라도 요금을 적게 내고 싶으면 경로 1-3-4 또는 1-2-4를 선택하면 된다.

문제는 고속도로 도로망에 대한 정보가 주어지면 시작 도시에서 끝 도시까지 연결하는 효율적인 경로를 계산하는 것이다. 우리는 단지 서로 다른 효율적인 비용-시간 쌍의 개수만 출력하면 된다.

문제는 지역들이 노드로 구성된 그래프가 주어졌을 때 원샘이 원하는 지역 간의 거리를 신속히 알려주는 것이다.

입력

첫째 줄에 도시의 개수 n(1≤n≤100), 도로의 개수 m(1≤m≤300), 시작 도시 s, 도착 도시 e가 주어진다. (1≤s,e≤n, s≠e) 그 다음부터 m개의 줄에 도로에 대한 정보가 주어지는데 한 줄에 한 도로의 양 끝점 p, r(1≤p,r≤n, p≠r)과 요금 c(0≤c≤100), 그리고 시간 t(0≤t≤100)이 주어진다. 두 개 도시 사이에는 한 개 이상의 도로가 존재할 수 있다.

출력

첫 줄에 서로 다른 효율적인 비용-시간 쌍의 개수를 출력한다.

예제 입력 1

4 5 1 4
2 1 2 1
3 4 3 1
2 3 1 2
3 1 1 4
2 4 2 4

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE3MDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzExY1x1YzZiOCBcdWIwYjRcdWM3NTggXHVhY2UwXHVjMThkXHViM2M0XHViODVjIFx1YjNjNFx1Yjg1Y1x1YjlkZFx1Yzc1OCBcdWM3NzRcdWM2YTkgXHVjNjk0XHVhZTA4XHVjNzc0IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWM5OWRcdWFjMDBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YzJlNFx1YzgxYyBcdWJiMzhcdWM4MWNcdWI4NWMgXHVjODFjXHVhZTMwXHViNDE4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhY2UwXHVjMThkXHViM2M0XHViODVjIFx1YjNjNFx1Yjg1Y1x1YjlkZFx1Yzc0MCBcdWI0NTAgXHViM2M0XHVjMmRjXHVhYzA0XHVjNzU4IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWI0ZTRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHViM2M0XHViODVjIFx1Yzc3NFx1YzZhOVx1YzY5NFx1YWUwOFx1YWNmYyBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjNTRjXHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2JkXHViODVjXHViMjk0IFx1YzVlY1x1ZDU4OVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWM3NzRcdWM2YTlcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHViNGU0XHVjNzQ0IFx1YjA5OFx1YzVmNFx1ZDU1YyBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWFjYmRcdWI4NWNcdWMwYzFcdWM3NTggXHVjZDFkIFx1Yzc3NFx1YjNkOVx1YzJkY1x1YWMwNFx1Yzc0MCBcdWFjYmRcdWI4NWNcdWMwYzFcdWM3NTggXHViM2M0XHViODVjXHViNGU0XHVjNzQ0IFx1YzljMFx1YjA5OFx1YWMwMFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyZuYnNwO1x1YWNiZFx1Yjg1Y1x1YzBjMVx1Yzc1OCBcdWNkMWQgXHVjNjk0XHVhZTA4XHVjNzQwIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWIzYzRcdWI4NWNcdWI0ZTRcdWM3NTggXHVjNzc0XHVjNmE5XHVjNjk0XHVhZTA4XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFjYmRcdWI4NWNcdWMwYzFcdWM3NTggXHVjZDFkIFx1Yzc3NFx1YzZhOVx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM4MDFcdWM3NDRcdWMyMThcdWI4NWQsIFx1Yzc3NFx1YzZhOVx1YzY5NFx1YWUwOFx1Yzc3NCBcdWM4MDFcdWM3NDRcdWMyMThcdWI4NWQgXHViMzU0IFx1Yzg4Ylx1Yzc0MCBcdWFjYmRcdWI4NWNcdWFjMDAgXHViNDFjXHViMmU0LiBcdWM5ODksIFx1YzViNFx1YjVhNCBcdWFjYmRcdWI4NWNcdWFjMDAgXHViMmU0XHViOTc4IFx1YWNiZFx1Yjg1Y1x1YmNmNFx1YjJlNCBcdWM4OGJcdWIyZTRcdWIyOTQgXHViOWQwXHVjNzQwIFx1Yzc3NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHViMmU0XHViOTc4IFx1YWNiZFx1Yjg1Y1x1YmNmNFx1YjJlNCBcdWJlNjBcdWI5NzRcdWFjZTAgXHVjNzc0XHVjNmE5XHVjNjk0XHVhZTA4XHVjNzc0IFx1YzgwMVx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNWI0XHViNWEwXHVkNTVjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWIyZTRcdWI5NzggXHVjNWI0XHViNWE0IFx1YWNiZFx1Yjg1Y1x1YmNmNFx1YjJlNFx1YjNjNCBcdWM4OGJcdWM3NDAgXHVhY2JkXHViODVjXHVjNzdjIFx1YjU0YyBcdWM3NzRcdWI5N2MgXHVjZDVjXHVjODAxXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yjc3YyBcdWJkODBcdWI5NzhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWQ1NmRcdWMwYzEgXHVjNzc0XHViN2VjXHVkNTVjIFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWIzYzRcdWI4NWNcdWI5ZGRcdWM3NzQgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWM2OTRcdWFlMDhcdWFjZmMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1ZDU1YyBcdWMzMGRcdWM3NTggXHVjMjJiXHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNFx1YzljNFx1YjJlNCw8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwNVwvZ3JhZ3JhLlBOR1wiIHN0eWxlPVwiaGVpZ2h0OjE0M3B4OyB3aWR0aDoyNzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHViM2M0XHVjMmRjIDFcdWM1ZDBcdWMxMWMgXHViM2M0XHVjMmRjIDRcdWI4NWMgXHVhYzAwXHViMjk0XHViMzcwXHViMjk0IFx1Y2QxZCA0XHVhYzAwXHVjOWMwIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIDRcdWFjMDBcdWM5YzAgXHVhY2JkXHViODVjXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWNkMWQgXHVjNzc0XHViM2Q5XHVjMmRjXHVhYzA0XHVhY2ZjIFx1YzY5NFx1YWUwOFx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWM1ZWMgXHViY2Y0XHViYTc0IDEtMi00KFx1YzY5NFx1YWUwOCA0LCBcdWMyZGNcdWFjMDQgNSksIDEtMy00KFx1YzY5NFx1YWUwOCA0LCBcdWMyZGNcdWFjMDQgNSksIDEtMi0zLTQoXHVjNjk0XHVhZTA4IDYsIFx1YzJkY1x1YWMwNCA0KSwgMS0zLTItNChcdWM2OTRcdWFlMDggNCwgXHViZTQ0XHVjNmE5IDEwKVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVhY2JkXHViODVjIDEtMy00XHVjNjQwIDEtMi00XHVhYzAwIFx1YWNiZFx1Yjg1YyAxLTMtMi00XHViY2Y0XHViMmU0IFx1Yzg4Ylx1Yzc0MCBcdWFjODNcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI5ZGRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVkNmE4XHVjNzI4XHVjODAxXHVjNzc4IFx1YzY5NFx1YWUwOC1cdWMyZGNcdWFjMDQgXHVjMzBkXHVjNzc0IFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWM2OTRcdWFlMDggNCwgXHVjMmRjXHVhYzA0IDUoXHVhY2JkXHViODVjIDEtMi00LCAxLTMtNCksIFx1YzY5NFx1YWUwOCA2LCBcdWMyZGNcdWFjMDQgNChcdWFjYmRcdWI4NWMgMS0yLTMtNCkuIFx1YjljY1x1YzU3ZCBcdWM2OTRcdWFlMDhcdWM3NDQgXHViOWNlXHVjNzc0IFx1YjBiNFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWJlNjBcdWI5NzggXHVhZTM4XHVjNzQ0IFx1YzZkMFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWFjYmRcdWI4NWMgMS0yLTMtNFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgXHViNDE4XHVhY2UwIFx1YmMxOFx1YjMwMFx1Yjg1YyBcdWMyZGNcdWFjMDRcdWM3NDAgXHVjODcwXHVhZTA4IFx1YjM1NCBcdWFjNzhcdWI5YWNcdWIzNTRcdWI3N2NcdWIzYzQgXHVjNjk0XHVhZTA4XHVjNzQ0IFx1YzgwMVx1YWM4YyBcdWIwYjRcdWFjZTAgXHVjMmY2XHVjNzNjXHViYTc0IFx1YWNiZFx1Yjg1YyAxLTMtNCBcdWI2MTBcdWIyOTQgMS0yLTRcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWIzYzRcdWI4NWNcdWI5ZGRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQgXHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWIwNWQgXHViM2M0XHVjMmRjXHVhZTRjXHVjOWMwIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3NzggXHVhY2JkXHViODVjXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWIyZThcdWM5YzAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3NzggXHViZTQ0XHVjNmE5LVx1YzJkY1x1YWMwNCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1YjI5NCBcdWM5YzBcdWM1ZWRcdWI0ZTRcdWM3NzQgXHViMTc4XHViNGRjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWM2ZDBcdWMwZDhcdWM3NzQgXHVjNmQwXHVkNTU4XHViMjk0IFx1YzljMFx1YzVlZCBcdWFjMDRcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1YzJlMFx1YzE4ZFx1ZDc4OCBcdWM1NGNcdWI4MjRcdWM4ZmNcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWMyZGNcdWM3NTggXHVhYzFjXHVjMjE4IG4oMSZsZTtuJmxlOzEwMCksIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMTggbSgxJmxlO20mbGU7MzAwKSwgXHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkYyBzLCBcdWIzYzRcdWNjMjkgXHViM2M0XHVjMmRjIGVcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsZTtzLGUmbGU7biwgcyZuZTtlKSBcdWFkZjggXHViMmU0XHVjNzRjXHViZDgwXHVkMTMwIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1YyBcdWIzYzRcdWI4NWNcdWM3NTggXHVjNTkxIFx1YjA1ZFx1YzgxMCBwLCByKDEmbGU7cCxyJmxlO24sIHAmbmU7cilcdWFjZmMgXHVjNjk0XHVhZTA4IGMoMCZsZTtjJmxlOzEwMCksIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWMyZGNcdWFjMDQgdCgwJmxlO3QmbGU7MTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWFjMWMgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWQ1NWMgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1ZDZhOFx1YzcyOFx1YzgwMVx1Yzc3OCBcdWJlNDRcdWM2YTktXHVjMmRjXHVhYzA0IFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE3MDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCaWNyaXRlcmlhbCByb3V0aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbmV0d29yayBvZiBwYXkgaGlnaHdheXMgaW4gQnl0ZWxhbmQgaXMgZ3Jvd2luZyB1cCB2ZXJ5IHJhcGlkbHkuIEl0IGhhcyBiZWNvbWUgc28gZGVuc2UsIHRoYXQgdGhlIGNob2ljZSBvZiB0aGUgYmVzdCByb3V0ZSBpcyBhIHJlYWwgcHJvYmxlbS4gVGhlIG5ldHdvcmsgb2YgaGlnaHdheXMgY29uc2lzdHMgb2YgYmlkaXJlY3Rpb25hbCByb2FkcyBjb25uZWN0aW5nIGNpdGllcy4gRWFjaCBzdWNoIHJvYWQgaXMgY2hhcmFjdGVyaXplZCBieSB0aGUgdHJhdmVsaW5nIHRpbWUgYW5kIHRoZSB0b2xsIHRvIGJlIHBhaWQuPFwvcD5cclxuXHJcbjxwPlRoZSByb3V0ZSBpcyBjb21wb3NlZCBvZiBjb25zZWN1dGl2ZSByb2FkcyB0byBiZSB0cmF2ZWxlZC4gVGhlIHRvdGFsIHRpbWUgbmVlZGVkIHRvIHRyYXZlbCB0aGUgcm91dGUgaXMgZXF1YWwgdG8gdGhlIHN1bSBvZiB0cmF2ZWxpbmcgdGltZXMgb2YgdGhlIHJvYWRzIGNvbnN0aXR1dGluZyB0aGUgcm91dGUuIFRoZSB0b3RhbCBmZWUgZm9yIHRoZSByb3V0ZSBpcyBlcXVhbCB0byB0aGUgc3VtIG9mIHRvbGxzIGZvciB0aGUgcm9hZHMgb2Ygd2hpY2ggdGhlIHJvdXRlIGNvbnNpc3RzLiBUaGUgZmFzdGVyIG9uZSBjYW4gdHJhdmVsIHRoZSByb3V0ZSBhbmQgdGhlIGxvd2VyIHRoZSBmZWUsIHRoZSBiZXR0ZXIgdGhlIHJvdXRlLiBTdHJpY3RseSBzcGVha2luZywgb25lIHJvdXRlIGlzIGJldHRlciB0aGFuIHRoZSBvdGhlciBpZiBvbmUgY2FuIHRyYXZlbCBpdCBmYXN0ZXIgYW5kIGRvZXMgbm90IGhhdmUgdG8gcGF5IG1vcmUsIG9yIHZpY2UgdmVyc2E6IG9uZSBjYW4gcGF5IGxlc3MgYW5kIGNhbiB0cmF2ZWwgaXQgbm90IHNsb3dlciB0aGFuIHRoZSBvdGhlciBvbmUuIFdlIHdpbGwgY2FsbCBhIHJvdXRlIGNvbm5lY3RpbmcgdHdvIGNpdGllcyBtaW5pbWFsIGlmIHRoZXJlIGlzIG5vIGJldHRlciByb3V0ZSBjb25uZWN0aW5nIHRoZXNlIGNpdGllcy4gVW5mb3J0dW5hdGVseSwgbm90IGFsd2F5cyBleGlzdHMgb25lIG1pbmltYWwgcm91dGUgJm5kYXNoOyB0aGVyZSBjYW4gYmUgc2V2ZXJhbCBpbmNvbXBhcmFibGUgcm91dGVzIG9yIHRoZXJlIGNhbiBiZSBubyByb3V0ZSBhdCBhbGwuPFwvcD5cclxuXHJcbjxwPlRoZSBwaWN0dXJlIGJlbG93IHByZXNlbnRzIGFuIGV4YW1wbGUgbmV0d29yayBvZiBoaWdod2F5cy4gRWFjaCByb2FkIGlzIGFjY29tcGFuaWVkIGJ5IGEgcGFpciBvZiBudW1iZXJzOiB0aGUgdG9sbCBhbmQgdGhlIHRyYXZlbGluZyB0aW1lLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2hpZ2gucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjMycHg7IHdpZHRoOjQ4OXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkxldCB1cyBjb25zaWRlciBmb3VyIGRpZmZlcmVudCByb3V0ZXMgZnJvbSBjaXR5IDEgdG8gY2l0eSA0LCB0b2dldGhlciB3aXRoIHRoZWlyIGZlZXMgYW5kIHRyYXZlbGluZyB0aW1lczogMSAyIDQgKGZlZSA0LCB0aW1lIDUpLCAxIDMgNCAoZmVlIDQsIHRpbWUgNSksIDEgMiAzIDQgKGZlZSA2LCB0aW1lIDQpIGFuZCAxIDMgMiA0IChmZWUgNCwgdGltZSAxMCkuPFwvcD5cclxuXHJcbjxwPlJvdXRlcyAxIDMgNCBhbmQgMSAyIDQgYXJlIGJldHRlciB0aGFuIDEgMyAyIDQuIFRoZXJlIGFyZSB0d28gbWluaW1hbCBwYWlycyBmZWUgdGltZTogZmVlIDQsIHRpbWUgNSAocm9vdHMgMSAyIDQgYW5kIDEgMyA0KSBhbmQgZmVlIDYsIHRpbWUgNCAocm9vdCAxIDIgMyA0KS4gV2hlbiBjaG9vc2luZyB0aGUgcm91dGUgd2UgaGF2ZSB0byBkZWNpZGUgd2hldGhlciB3ZSBwcmVmZXIgdG8gdHJhdmVsIGZhc3RlciBidXQgd2UgbXVzdCBwYXkgbW9yZSAocm91dGUgMSAyIDMgNCksIG9yIHdlIHdvdWxkIHJhdGhlciB0cmF2ZWwgc2xvd2VyIGJ1dCBjaGVhcGVyIChyb3V0ZSAxIDMgNCBvciAxIDIgNCkuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0sIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlJlYWRzIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGUgaGlnaHdheSBuZXR3b3JrIGFuZCBzdGFydGluZyBhbmQgZW5kaW5nIGNpdGllcyBvZiB0aGUgcm91dGUgZm9ybSB0aGUgdGV4dCBmaWxlIGJpYy5pbi48XC9saT5cclxuXHQ8bGk+Q29tcHV0ZXMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgbWluaW1hbCByb3V0ZXMgY29ubmVjdGluZyB0aGUgc3RhcnRpbmcgYW5kIGVuZGluZyBjaXR5LCBob3dldmVyIGFsbCB0aGUgcm91dGVzIGNoYXJhY3Rlcml6ZWQgYnkgdGhlIHNhbWUgZmVlIGFuZCB0cmF2ZWxpbmcgdGltZSBjb3VudCBhcyBqdXN0IG9uZSByb3V0ZTsgd2UgYXJlIGludGVyZXN0ZWQganVzdCBpbiB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBtaW5pbWFsIHBhaXJzIGZlZSB0aW1lLjxcL2xpPlxyXG5cdDxsaT5Xcml0ZXMgdGhlIHJlc3VsdCB0byB0aGUgb3V0cHV0IGZpbGUgYmljLm91dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgYXJlIGZvdXIgaW50ZWdlcnMsIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLCBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgdGV4dCBmaWxlIGJpYy5pbjogbnVtYmVyIG9mIGNpdGllcyBuICh0aGV5IGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbiksIDEgJmxlOyBuICZsZTsgMTAwLCBudW1iZXIgb2Ygcm9hZHMgbSwgMCAmbGU7IG0gJmxlOyAzMDAsIHN0YXJ0aW5nIGNpdHkgcyBhbmQgZW5kaW5nIGNpdHkgZSBvZiB0aGUgcm91dGUsIDEgJmxlOyBzLCBlICZsZTsgbiwgcyAmbmU7IGUuIFRoZSBjb25zZWN1dGl2ZSBtIGxpbmVzIGRlc2NyaWJlIHRoZSByb2Fkcywgb25lIHJvYWQgcGVyIGxpbmUuIEVhY2ggb2YgdGhlc2UgbGluZXMgY29udGFpbnMgZm91ciBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlczogdHdvIGVuZHMgb2YgYSByb2FkIHAgYW5kIHIsIDEgJmxlOyBwLCByICZsZTsgbiwgcCAmbmU7IHIsIHRoZSB0b2xsIGMsIDAgJmxlOyBjICZsZTsgMTAwLCBhbmQgdGhlIHRyYXZlbGluZyB0aW1lIHQsIDAgJmxlOyB0ICZsZTsgMTAwLiBUd28gY2l0aWVzIGNhbiBiZSBjb25uZWN0ZWQgYnkgbW9yZSB0aGFuIG9uZSByb2FkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgd3JpdGUgb25lIGludGVnZXIsIG51bWJlciBvZiBkaWZmZXJlbnQgbWluaW1hbCBwYWlycyBmZWUgdGltZSBmb3Igcm91dGVzIGZyb20gcyB0byBlLCBpbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgdGV4dCBmaWxlIGJpYy5vdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2002 4번