문제
때는 소기 0년, 소들은 드디어 시간 여행 기술을 개발했다. 소들은 그 기념으로 이번 해를 소기 0년이라고 부르기로 했다.
소들은 과거로 시간여행을 하면 평행세계가 생기도록 제조하여, 타임 패러독스를 해결하였다.
시간 여행을 하기 위해서는 타임머신을 타야하며, 지정된 공항에서만 타고 내려야만 한다. 공항은 총 N개가 있으며 1~N까지 번호가 부여되어 있다.
또한 타임머신 운행편이 M개가 있으며 1~M개의 번호가 부여되어 있다. (1 ≤ N,M ≤ 200000)
j번 운행편은 출발 공항 cj, 출발 년도 rj, 도착 공항 dj, 도착 년도 sj (0 ≤ rj,sj ≤ 109, sj < rj 가능) 4개의 정보로 이루어져 있다.
소들은 타임머신에서 내린 다음 곧바로 타임머신을 탈 수 없고, 최소한의 휴식이 필요하다. 휴식 시간은 도착 공항마다 다르다.
즉, i번 공항은 ai년을 쉬어야 한다. (1 ≤ ai ≤ 109)
따라서, i번 공항에 s년에 도착했다면, r년에 떠나는 다른 운행편을 타기 위해서는 r ≥ s+ai 를 만족해야 한다.
소기 0년, 소가 1번 도시에서 타임머신을 타려고 한다.
1 ~ N번 공항에 도착하는 가장 빠른 년도를 구하라.
입력
첫 번째 줄에 N과 M이 주어진다.
다음 M개의 줄에 운행편이 주어진다.
운행편의 j번째 줄에 cj, rj, dj, sj가 순서로 주어진다.(1 ≤ cj, dj ≤ N, 0 ≤ rj, sj ≤ 109)
다음 줄에 N개의 공항에 대한 휴식 시간이 주어진다.
N개의 숫자가 공백을 구분으로 a1, …, an 형식으로 주어진다.
출력
N줄에 걸쳐 1~N 번 공항에 도착하는 가장 빠른 년도를 출력한다.
만약 i번째 공항에 도착할 수 없다면 i번째 줄에는 -1을 출력한다.
예제 #1
3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10
0
0
20
예제 #2
3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10
0
10
-1
로그인해야 코드를 작성할 수 있어요.