시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1024 MB 53 13 12 70.588%

문제

정보과학을 잘하는 사람만 거주할 수 있다는 국가, '경곽국'의 존재를 아는가? 경곽국은 총 N개의 도시로 이루어져 있으며, 각각 1번부터 N번까지 번호가 부여되어 있다.

경곽국에서 도시간의 이동수단은 비행기가 유일하다. 모든 도시쌍에 대하여 그 두 도시 사이를 경유하는 비행기가 존재한다. 다만, 비행기를 탑승하기 위해서는 '비행기 표'가 필요하다. 경곽국에서 구매할 수 있는 비행기 표는 총 M개가 있으며, 각각 1번부터 M번까지 번호가 부여되어 있다. i번 표는 가격이 Ai원이며, 비행기의 출발 도시의 번호가 Bi 이상 Ci 이하, 도착 도시의 번호가 Di 이상 Ei 이하일 때에만 사용할 수 있다(1 ≤ i ≤ M).

모든 M개의 표는 일회용이며 한 번만 구매할 수 있다.

교준이의 집은 K번 도시에 있다. 현재 교준이는 집에서 놀고 있다.

교준이가 집을 나와 X번 도시로 가기 위해 구매해야 하는 표 값의 합의 최솟값을 WX라 하자(1 ≤ X ≤ N). 단, 교준이는 집을 나오기 전에, 필요한 모든 비행기 표를 구매한다. 만일 어떻게 표를 사서 이동하더라도 X번 도시에 이동할 수 없다면, WX = -1로 정의한다.

W1, ···, WN의 값을 모두 구하는 프로그램을 작성하시오.

입력

첫번째 줄에 경곽국의 도시의 개수를 의미하는 자연수 N, 비행기 표의 총 개수를 의미하는 자연수 M, 교준이의 집이 있는 도시의 번호 K가 사이에 공백을 두고 주어진다.

두번째 줄부터 M개의 줄에 걸쳐, M개의 비행기 표의 정보가 주어진다. (i+1)번째 줄에는 i번 표의 정보를 나타내는 다섯 개의 정수 Ai, Bi, Ci, Di, Ei가 사이에 공백을 두고 주어진다(1 ≤ iM).

출력

첫번째 줄에 N개의 정수 W1, ···, WN를 사이에 공백을 두고 차례대로 출력한다.

WK = 0임에 유의하라.

제한

모든 입력 데이터는 다음 조건을 만족한다.

  • 1 ≤ N ≤ 250,000
  • 1 ≤ M ≤ 250,000
  • 1 ≤ KN
  • 0 ≤ Ai ≤ 109 (1 ≤ i ≤ M)
  • 1 ≤ Bi ≤ Ci ≤ N (1 ≤ i ≤ M)
  • 1 ≤ Di ≤ Ei ≤ N (1 ≤ i ≤ M)

예제 입력 1

1 1 1
0 1 1 1 1

예제 출력 1

0

예제 입력 2

3 1 1
10 1 2 3 3

예제 출력 2

0 -1 10

예제 입력 3

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

예제 출력 3

0 5 -1 10 10

출처

High School > 경기과학고등학교 > 나는코더다 2019 송년대회 I번

  • 데이터를 만든 사람: TAMREF
  • 문제를 만든 사람: yclock