여정

바이트국(Byteotia)에는 $1$번부터 $n$번까지 번호가 매겨진 도시 $n$개가 있다. 고속도로는 자주 놓이지 않지만, 한 번 놓일 때는 큰 묶음 단위로 건설된다. 지금까지 모두 $m$개의 묶음이 건설되었으며, $i$번째 묶음은 번호가 $[a_i, b_i]$에 속하는 도시와 번호가 $[c_i, d_i]$에 속하는 도시를 잇는 모든 고속도로로 이루어진다. 고속도로는 도시에서만 서로 만나며, 터널이나 고가도로를 통해 서로를 지나칠 수 있다. 이 고속도로망을 이용하면 임의의 두 도시 사이를 오갈 수 있다. 고속도로 하나를 타는 데는 정확히 $1$달러가 든다.

바이트아사르(Byteasar)는 고향으로 돌아와 수도인 비트시티(Bitcity), 곧 $p$번 도시에 정착하려 한다. 여러 도시에 흩어져 사는 옛 친구들을 모두 방문하고 싶은 그는, 고속도로망만 이용해 비트시티에서 다른 모든 도시로 가는 최소 비용을 알고 싶어 한다. 이 값을 구하여라.

첫째 줄에 세 정수 $n$, $m$, $p$가 주어진다 ($2 \le n \le 500000$, $1 \le m \le 100000$, $1 \le p \le n$). 각각 도시의 수, 고속도로 묶음의 수, 그리고 바이트아사르가 사는 도시(비트시티)의 번호이다.

이어지는 $m$개의 줄에는 각 묶음의 정보가 한 줄에 하나씩, 네 정수 $a_i$, $b_i$, $c_i$, $d_i$로 주어진다 ($1 \le a_i \le b_i \le n$, $1 \le c_i \le d_i \le n$, $[a_i, b_i] \cap [c_i, d_i] = \varnothing$). 이는 $[a_i, b_i]$에 속하는 모든 도시가 $[c_i, d_i]$에 속하는 모든 도시와 양방향 고속도로로 연결됨을 뜻한다. 각 고속도로는 많아야 한 묶음에만 속한다.

$n$개의 줄을 출력한다. $i$번째 줄에는 비트시티에서 $i$번 도시까지 가는 최소 비용(달러)을 출력한다. 따라서 $p$번째 줄의 값은 $0$이다.