시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)300605624.561%

문제

울산에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 교차로가 있고, 교차로와 교차로를 잇는 $M$개의 도로가 있다. 각 도로는 일방통행이며, 도로를 따라 이동하는 데 걸리는 시간이 정해져 있다.

윤이는 매일 현대모비스의 자율주행 시스템을 탑재한 차를 타고 집에서 회사로 출근한다. 윤이의 집은 $S$번 교차로에, 회사는 $T$번 교차로에 있다. 현대모비스의 자율주행 시스템은 항상 집에서 회사까지 최단 시간이 걸리는 주행 경로를 이용한다.

윤이는 얼마 전 울산에 새로운 도로 두 개가 건설될 것이라는 계획을 들었다. 윤이는 앞으로 회사에 더 빠르게 출근할 수 있을 거라는 기대감에 부풀어 있다. 하지만 윤이는 새 도로가 어떤 교차로를 잇는지와, 새 도로를 따라 이동하는 데 걸리는 시간이 얼마인지에 대한 내용을 듣지는 못했다. 따라서 윤이는 $Q$개의 도로 건설 시나리오를 가정하고, 각 상황에서 윤이의 자율주행차가 어떤 경로를 따라 주행할지 계산해 보기로 했다.

윤이가 가정한 $Q$개의 도로 건설 시나리오 각각에 대해, 윤이가 현대모비스 자율주행 시스템을 이용하여 집에서 회사로 출근하는 데 걸리는 시간을 구하시오.

입력

첫 번째 줄에 교차로의 수 $N$, 기존 도로의 수 $M$, 집의 교차로 번호 $S$, 회사의 교차로 번호 $T$가 공백으로 구분되어 주어진다. ($2\leq N\leq 300$; $0\leq M\leq 3\ 000$; $1\leq S,T\leq N$; $S\neq T$)

이후 $M$개의 줄에 기존 도로에 대한 정보를 나타내는 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. 시작 교차로가 $u$번, 도착 교차로가 $v$번이고 이동하는 데 $w$의 시간이 걸리는 일방통행 도로를 나타낸다. ($1\leq u,v\leq N$; $1\leq w\leq 10^6$)

그 다음 줄에 도로 건설 시나리오의 수 $Q$가 주어진다. ($1\leq Q\leq 100\ 000$)

이후 $Q$개의 줄에 새로 건설될 두 개의 도로에 대한 정보를 나타내는 정수 $a_1$, $b_1$, $c_1$, $a_2$, $b_2$, $c_2$가 공백으로 구분되어 주어진다. 시작 교차로가 $a_1$번, 도착 교차로가 $b_1$번이고 이동하는 데 $c_1$의 시간이 걸리는 일방통행 도로와, 시작 교차로가 $a_2$번, 도착 교차로가 $b_2$번이고 이동하는 데 $c_2$의 시간이 걸리는 일방통행 도로를 새롭게 건설하는 시나리오를 나타낸다. ($1\leq a_1,b_1,a_2,b_2\leq N$; $1\le c_1,c_2\le 10^6$)

같은 교차로 쌍을 잇는 도로가 여러 개 주어질 수 있으며, 시작 교차로와 도착 교차로가 동일한 도로가 주어질 수 있다.

출력

각 도로 건설 시나리오에 대해, 윤이가 집에서 회사로 출근하는 데 걸리는 시간을 $Q$개의 줄에 걸쳐 출력한다. 만약 어떤 시나리오에서 집에서 회사로 출근하는 것이 불가능하다면, 해당 줄에는 대신 $-1$을 출력한다.

예제 입력 1

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

예제 출력 1

5
7
6
7
W3sicHJvYmxlbV9pZCI6IjI2MTI1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViNDUwIFx1YjNjNFx1Yjg1YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNmI4XHVjMGIwXHVjNWQwXHViMjk0ICQxJFx1YmM4OFx1YmQ4MFx1ZDEzMCAkTiRcdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1Yzc0MCAkTiRcdWFjMWNcdWM3NTggXHVhZDUwXHVjYzI4XHViODVjXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhZDUwXHVjYzI4XHViODVjXHVjNjQwIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1Yjk3YyBcdWM3ODdcdWIyOTQgJE0kXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWIyOTQgPHN0cm9uZz5cdWM3N2NcdWJjMjlcdWQxYjVcdWQ1ODk8XC9zdHJvbmc+XHVjNzc0XHViYTcwLCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViNTMwXHViNzdjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM4MTVcdWQ1NzRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjRcdWM3NzRcdWIyOTQgXHViOWU0XHVjNzdjIFx1ZDYwNFx1YjMwMFx1YmFhOFx1YmU0NFx1YzJhNFx1Yzc1OCBcdWM3OTBcdWM3MjhcdWM4ZmNcdWQ1ODkgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNzQ0IFx1ZDBkMVx1YzdhY1x1ZDU1YyBcdWNjMjhcdWI5N2MgXHVkMGMwXHVhY2UwIFx1YzlkMVx1YzVkMFx1YzExYyBcdWQ2OGNcdWMwYWNcdWI4NWMgXHVjZDljXHVhZGZjXHVkNTVjXHViMmU0LiBcdWM3MjRcdWM3NzRcdWM3NTggXHVjOWQxXHVjNzQwICRTJFx1YmM4OCBcdWFkNTBcdWNjMjhcdWI4NWNcdWM1ZDAsIFx1ZDY4Y1x1YzBhY1x1YjI5NCAkVCRcdWJjODggXHVhZDUwXHVjYzI4XHViODVjXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVkNjA0XHViMzAwXHViYWE4XHViZTQ0XHVjMmE0XHVjNzU4IFx1Yzc5MFx1YzcyOFx1YzhmY1x1ZDU4OSBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzlkMVx1YzVkMFx1YzExYyBcdWQ2OGNcdWMwYWNcdWFlNGNcdWM5YzAgXHVjZDVjXHViMmU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjOGZjXHVkNTg5IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcyNFx1Yzc3NFx1YjI5NCBcdWM1YmNcdWI5YzggXHVjODA0IFx1YzZiOFx1YzBiMFx1YzVkMCBcdWMwYzhcdWI4NWNcdWM2YjQgXHViM2M0XHViODVjIFx1YjQ1MCBcdWFjMWNcdWFjMDAgXHVhYzc0XHVjMTI0XHViNDIwIFx1YWM4M1x1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHViNGU0XHVjNWM4XHViMmU0LiBcdWM3MjRcdWM3NzRcdWIyOTQgXHVjNTVlXHVjNzNjXHViODVjIFx1ZDY4Y1x1YzBhY1x1YzVkMCBcdWIzNTQgXHViZTYwXHViOTc0XHVhYzhjIFx1Y2Q5Y1x1YWRmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0IFx1YWM3MFx1Yjc3Y1x1YjI5NCBcdWFlMzBcdWIzMDBcdWFjMTBcdWM1ZDAgXHViZDgwXHVkNDgwXHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YzcyNFx1Yzc3NFx1YjI5NCBcdWMwYzggXHViM2M0XHViODVjXHVhYzAwIFx1YzViNFx1YjVhNCBcdWFkNTBcdWNjMjhcdWI4NWNcdWI5N2MgXHVjNzg3XHViMjk0XHVjOWMwXHVjNjQwLCBcdWMwYzggXHViM2M0XHViODVjXHViOTdjIFx1YjUzMFx1Yjc3YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjNWJjXHViOWM4XHVjNzc4XHVjOWMwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIwYjRcdWM2YTlcdWM3NDQgXHViNGUzXHVjOWMwXHViMjk0IFx1YmFiYlx1ZDU4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzcyNFx1Yzc3NFx1YjI5NCAkUSRcdWFjMWNcdWM3NTggXHViM2M0XHViODVjIFx1YWM3NFx1YzEyNCBcdWMyZGNcdWIwOThcdWI5YWNcdWM2MjRcdWI5N2MgXHVhYzAwXHVjODE1XHVkNTU4XHVhY2UwLCBcdWFjMDEgXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjIFx1YzcyNFx1Yzc3NFx1Yzc1OCBcdWM3OTBcdWM3MjhcdWM4ZmNcdWQ1ODlcdWNjMjhcdWFjMDAgXHVjNWI0XHViNWE0IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWI1MzBcdWI3N2MgXHVjOGZjXHVkNTg5XHVkNTYwXHVjOWMwIFx1YWNjNFx1YzBiMFx1ZDU3NCBcdWJjZjRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjRcdWM3NzRcdWFjMDAgXHVhYzAwXHVjODE1XHVkNTVjICRRJFx1YWMxY1x1Yzc1OCBcdWIzYzRcdWI4NWMgXHVhYzc0XHVjMTI0IFx1YzJkY1x1YjA5OFx1YjlhY1x1YzYyNCBcdWFjMDFcdWFjMDFcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWM3MjRcdWM3NzRcdWFjMDAgXHVkNjA0XHViMzAwXHViYWE4XHViZTQ0XHVjMmE0IFx1Yzc5MFx1YzcyOFx1YzhmY1x1ZDU4OSBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YzlkMVx1YzVkMFx1YzExYyBcdWQ2OGNcdWMwYWNcdWI4NWMgXHVjZDljXHVhZGZjXHVkNTU4XHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1Yzc1OCBcdWMyMTggJE4kLCBcdWFlMzBcdWM4NzQgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCAkTSQsIFx1YzlkMVx1Yzc1OCBcdWFkNTBcdWNjMjhcdWI4NWMgXHViYzg4XHVkNjM4ICRTJCwgXHVkNjhjXHVjMGFjXHVjNzU4IFx1YWQ1MFx1Y2MyOFx1Yjg1YyBcdWJjODhcdWQ2MzggJFQkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDJcXGxlcSBOXFxsZXEgMzAwJDsgJDBcXGxlcSBNXFxsZXEgM1xcIDAwMCQ7ICQxXFxsZXEgUyxUXFxsZXEgTiQ7ICRTXFxuZXEgVCQpPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCAkTSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWUzMFx1Yzg3NCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4ICR1JCwgJHYkLCAkdyRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzJkY1x1Yzc5MSBcdWFkNTBcdWNjMjhcdWI4NWNcdWFjMDAgJHUkXHViYzg4LCBcdWIzYzRcdWNjMjkgXHVhZDUwXHVjYzI4XHViODVjXHVhYzAwICR2JFx1YmM4OFx1Yzc3NFx1YWNlMCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwICR3JFx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWFjXHViMjk0IFx1Yzc3Y1x1YmMyOVx1ZDFiNVx1ZDU4OSBcdWIzYzRcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiAoJDFcXGxlcSB1LHZcXGxlcSBOJDsgJDFcXGxlcSB3XFxsZXEgMTBeNiQpPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwIFx1YjNjNFx1Yjg1YyBcdWFjNzRcdWMxMjQgXHVjMmRjXHViMDk4XHViOWFjXHVjNjI0XHVjNzU4IFx1YzIxOCAkUSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDFcXGxlcSBRXFxsZXEgMTAwXFwgMDAwJCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0ICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjMGM4XHViODVjIFx1YWM3NFx1YzEyNFx1YjQyMCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggJGFfMSQsICRiXzEkLCAkY18xJCwgJGFfMiQsICRiXzIkLCAkY18yJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMmRjXHVjNzkxIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YWMwMCAkYV8xJFx1YmM4OCwgXHViM2M0XHVjYzI5IFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YWMwMCAkYl8xJFx1YmM4OFx1Yzc3NFx1YWNlMCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwICRjXzEkXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjNzdjXHViYzI5XHVkMWI1XHVkNTg5IFx1YjNjNFx1Yjg1Y1x1YzY0MCwgXHVjMmRjXHVjNzkxIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YWMwMCAkYV8yJFx1YmM4OCwgXHViM2M0XHVjYzI5IFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YWMwMCAkYl8yJFx1YmM4OFx1Yzc3NFx1YWNlMCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwICRjXzIkXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjNzdjXHViYzI5XHVkMWI1XHVkNTg5IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWMwYzhcdWI4NmRcdWFjOGMgXHVhYzc0XHVjMTI0XHVkNTU4XHViMjk0IFx1YzJkY1x1YjA5OFx1YjlhY1x1YzYyNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuICgkMVxcbGVxIGFfMSxiXzEsYV8yLGJfMlxcbGVxIE4kOyAkMVxcbGUgY18xLGNfMlxcbGUgMTBeNiQpPFwvcD5cclxuXHJcbjxwPlx1YWMxOVx1Yzc0MCBcdWFkNTBcdWNjMjhcdWI4NWMgXHVjMzBkXHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjMmRjXHVjNzkxIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YzY0MCBcdWIzYzRcdWNjMjkgXHVhZDUwXHVjYzI4XHViODVjXHVhYzAwIFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YjNjNFx1Yjg1YyBcdWFjNzRcdWMxMjQgXHVjMmRjXHViMDk4XHViOWFjXHVjNjI0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjNzI0XHVjNzc0XHVhYzAwIFx1YzlkMVx1YzVkMFx1YzExYyBcdWQ2OGNcdWMwYWNcdWI4NWMgXHVjZDljXHVhZGZjXHVkNTU4XHViMjk0IFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0ICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzViNFx1YjVhNCBcdWMyZGNcdWIwOThcdWI5YWNcdWM2MjRcdWM1ZDBcdWMxMWMgXHVjOWQxXHVjNWQwXHVjMTFjIFx1ZDY4Y1x1YzBhY1x1Yjg1YyBcdWNkOWNcdWFkZmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgXHVkNTc0XHViMmY5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzMDBcdWMyZTAgJC0xJFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjYxMjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUd28gUm9hZHMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIFVsc2FuLCB0aGVyZSBhcmUgJE4kIGludGVyc2VjdGlvbnMgbnVtYmVyZWQgZnJvbSAkMSQgdG8gJE4kLCBhbmQgJE0kIHJvYWRzIGNvbm5lY3RpbmcgdGhlIGludGVyc2VjdGlvbnMuIEVhY2ggcm9hZCBpcyA8c3Ryb25nPm9uZS13YXk8XC9zdHJvbmc+LCB3aXRoIGEgZml4ZWQgdGltZSB0byBwYXNzIHRocm91Z2ggdGhlIHJvYWQuPFwvcD5cclxuXHJcbjxwPkV2ZXJ5IGRheSwgWXVuZWUgZ29lcyB0byB3b3JrIGZyb20gaG9tZSBieSBjYXIgd2l0aCBIeXVuZGFpIE1vYmlzIHNlbGYtZHJpdmluZyBzeXN0ZW0uIFl1bmVlJnJzcXVvO3MgaG9tZSBpcyBhdCBpbnRlcnNlY3Rpb24gJFMkLCBhbmQgdGhlIHdvcmtwbGFjZSBpcyBhdCBpbnRlcnNlY3Rpb24gJFQkLiBIeXVuZGFpIE1vYmlzIHNlbGYtZHJpdmluZyBzeXN0ZW0gYWx3YXlzIHVzZXMgYSBkcml2aW5nIHJvdXRlIHdpdGggdGhlIGxlYXN0IGFtb3VudCBvZiB0aW1lLjxcL3A+XHJcblxyXG48cD5ZdW5lZSByZWNlbnRseSBoZWFyZCB0aGF0IHR3byBtb3JlIHJvYWRzIHdpbGwgYmUgYnVpbHQgaW4gVWxzYW4uIFl1bmVlIGlzIGV4Y2l0ZWQgYmVjYXVzZSB0aGUgbmV3IHJvYWRzIG1heSBzaG9ydGVuIHRoZSB0aW1lIHRvIGdvIHRvIHdvcmsuIEhvd2V2ZXIsIFl1bmVlIGRvZXMgbm90IGtub3cgd2hpY2ggaW50ZXJzZWN0aW9ucyB0aGUgcm9hZHMgd2lsbCBjb25uZWN0IGFuZCBob3cgbG9uZyBpdCB3aWxsIHRha2UgdG8gcGFzcyB0aHJvdWdoIHRoZSByb2Fkcy4gU28gWXVuZWUgd2lsbCBhc3N1bWUgJFEkIHJvYWQgY29uc3RydWN0aW9uIHNjZW5hcmlvcywgYW5kIGNhbGN1bGF0ZSB3aGljaCBwYXRoIHRoZSBzZWxmLWRyaXZpbmcgY2FyIHdpbGwgdGFrZSBpbiBlYWNoIHNjZW5hcmlvLjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCAkUSQgc2NlbmFyaW8sIGZpbmQgaG93IGxvbmcgaXQgdGFrZXMgdG8gZ28gdG8gd29yayBmcm9tIGhvbWUgYnkgSHl1bmRhaSBNb2JpcyBzZWxmLWRyaXZpbmcgY2FyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgZ2l2ZXMgdGhlIG51bWJlciBvZiBpbnRlcnNlY3Rpb25zICROJCwgdGhlIG51bWJlciBvZiBleGlzdGluZyByb2FkcyAkTSQsIGhvbWUgbG9jYXRpb24gJFMkLCBhbmQgd29ya3BsYWNlIGxvY2F0aW9uICRUJC4gKCQyXFxsZXEgTlxcbGVxIDMwMCQ7ICQwXFxsZXEgTVxcbGVxIDNcXCAwMDAkOyAkMVxcbGVxIFMsVFxcbGVxIE4kOyAkU1xcbmVxIFQkKTxcL3A+XHJcblxyXG48cD5JbiB0aGUgbmV4dCAkTSQgbGluZXMsIHRocmVlIGludGVnZXJzICR1JCwgJHYkLCBhbmQgJHckIHJlcHJlc2VudGluZyB0aGUgZXhpc3Rpbmcgcm9hZHMgYXJlIGdpdmVuLiBJdCByZXByZXNlbnRzIGEgb25lLXdheSByb2FkIGNvbm5lY3RpbmcgZnJvbSBpbnRlcnNlY3Rpb24gJHUkIHRvICR2JCwgd2l0aCBhIHRpbWUgJHckIHRvIHBhc3MgdGhyb3VnaCB0aGUgcm9hZC4gKCQxXFxsZXEgdSx2XFxsZXEgTiQ7ICQxXFxsZXEgd1xcbGVxIDEwXjYkKTxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGdpdmVzIHRoZSBudW1iZXIgb2Ygcm9hZCBjb25zdHJ1Y3Rpb24gc2NlbmFyaW9zICRRJC4gKCQxXFxsZXEgUVxcbGVxIDEwMFxcIDAwMCQpPFwvcD5cclxuXHJcbjxwPkluIHRoZSBuZXh0ICRRJCBsaW5lcywgc2l4IGludGVnZXJzICRhXzEkLCAkYl8xJCwgJGNfMSQsICRhXzIkLCAkYl8yJCwgYW5kICRjXzIkIHJlcHJlc2VudGluZyB0aGUgdHdvIHJvYWRzIHRvIGJlIGJ1aWx0IGFyZSBnaXZlbi4gSXQgcmVwcmVzZW50cyBhIG9uZS13YXkgcm9hZCBjb25uZWN0aW5nIGZyb20gaW50ZXJzZWN0aW9uICRhXzEkIHRvICRiXzEkIHdpdGggYSB0aW1lICRjXzEkIHRvIHBhc3MgdGhyb3VnaCB0aGUgcm9hZCwgYW5kIGFub3RoZXIgb25lIGZyb20gaW50ZXJzZWN0aW9uICRhXzIkIHRvICRiXzIkIHdpdGggYSB0aW1lICRjXzIkLiAoJDFcXGxlcSBhXzEsYl8xLGFfMixiXzJcXGxlcSBOJDsgJDFcXGxlIGNfMSxjXzJcXGxlIDEwXjYkKTxcL3A+XHJcblxyXG48cD5UaGVyZSBtYXkgYmUgbXVsdGlwbGUgcm9hZHMgY29ubmVjdGluZyB0aGUgc2FtZSBwYWlyIG9mIGludGVyc2VjdGlvbnMsIGFuZCBzb21lIHJvYWRzIG1heSBjb25uZWN0IGFuIGludGVyc2VjdGlvbiB0byBpdHNlbGYuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggJFEkIHNjZW5hcmlvLCBwcmludCB0aGUgdGltZSBpdCB0YWtlcyBmb3IgWXVuZWUgdG8gZ28gdG8gd29yayBmcm9tIGhvbWUsIG9uZSBwZXIgbGluZS4gSWYgaXQgaXMgaW1wb3NzaWJsZSB0byBnbyB0byB3b3JrLCBwcmludCAkLTEkIGZvciB0aGF0IHNjZW5hcmlvIGluc3RlYWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

University > UNIST > 4th UNIST Algorithm Programming Contest Uni-CODE 2022 D번