Journeys

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

一个星球上有 $n$ 个国家，编号为 $1$ 到 $n$。道路是双向的，但数量太多，因此每条道路描述用四个整数 $a,b,c,d$ 压缩表示：对于任意满足 $a\le x\le b$、$c\le y\le d$ 的两个国家 $x,y$，国家 $x$ 与国家 $y$ 之间都有一条道路。

首都位于国家 $P$。请对每个国家求从 $P$ 出发最少需要经过多少条道路。输入保证从 $P$ 可以到达所有国家。

输入格式

第一行输入三个整数 $n,m,P$，分别表示国家数、压缩道路描述数和首都编号。

接下来 $m$ 行，每行输入四个整数 $a,b,c,d$，表示区间 $[a,b]$ 与区间 $[c,d]$ 之间存在完全二分的双向道路。

输出格式

输出 $n$ 行，第 $i$ 行输出从国家 $P$ 到国家 $i$ 最少需要经过的道路数。

样例输入 1

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

样例输出 1

1
1
2
0
1

数据范围

对于所有数据，$1\le n\le 5\times 10^5$，$1\le m\le 10^5$，$1\le P\le n$，$1\le a\le b\le n$，$1\le c\le d\le n$。输入保证首都可以到达所有国家。