Journeys

There are $n$ towns in Byteotia, numbered from $1$ to $n$. Highways are built rarely, but when they are, they come in large batches. In total $m$ batches have been built. The $i$-th batch consists of every highway that connects a town numbered in $[a_i, b_i]$ with a town numbered in $[c_i, d_i]$. Highways meet only at towns, but they may pass one another through tunnels or overpasses. The highway network lets you travel between any pair of towns. Riding a single highway costs exactly $1$ dollar.

Byteasar is returning home to settle in the capital, Bitcity, which is town $p$. He wants to visit old friends scattered across the towns, so he needs the cheapest travel cost from Bitcity to every other town using only highways. Help him compute it.

The first line contains three integers $n$, $m$, and $p$ ($2 \le n \le 500000$, $1 \le m \le 100000$, $1 \le p \le n$): the number of towns, the number of highway batches, and the town where Byteasar lives (Bitcity).

Each of the next $m$ lines describes one batch with four integers $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$). It means that every town in $[a_i, b_i]$ is joined by a bidirectional highway to every town in $[c_i, d_i]$. Each highway belongs to at most one batch.

Print $n$ lines. The $i$-th line must contain the minimum cost, in dollars, of travelling from Bitcity to town $i$. The $p$-th line is therefore $0$.