Description

On a planet, there are $n$ countries and many bidirectional roads. The countries are numbered from $1$ to $n$.

However, there are too many roads to describe in the usual way. So we describe the roads as follows: $(a,b),(c,d)$ means that for any two countries $x,y$, if $a \le x \le b$ and $c \le y \le d$, then there is a road between $x$ and $y$.

The capital is located in country $P$. You want to know the minimum number of roads that must be taken to travel from country $P$ to any country. It is guaranteed that country $P$ can reach every country.

Input Format

The first line contains three integers $n,m,P$.

Then follow $m$ lines, each containing four integers $a,b,c,d$.

Output Format

Output $n$ lines. The $i$-th line should contain the minimum number of roads that must be taken to travel from country $P$ to country $i$.

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

1
1
2
0
1

Hint

For all testdata, it is guaranteed that $1 \le n \le 5 \times 10^5$, $1 \le m \le 10^5$, $1 \le a \le b \le n$, $1 \le c \le d \le n$.

Translated by ChatGPT 5