题目描述

一个星球上有 $n$ 个国家和许多双向道路，国家用 $1\sim n$ 编号。

但是道路实在太多了，不能用通常的方法表示。于是我们以如下方式表示道路：$(a,b),(c,d)$ 表示，对于任意两个国家 $x,y$，如果 $a\le x\le b,c\le y\le d$，那么在 $x,y$ 之间有一条道路。

首都位于 $P$ 号国家。你想知道 $P$ 号国家到任意一个国家最少需要经过几条道路。保证 $P$ 号国家能到任意一个国家。

输入格式

第一行三个整数 $n,m,P$。

之后 $m$ 行，每行 $4$ 个整数 $a,b,c,d$。

输出格式

$n$ 行，第 $i$ 行表示 $P$ 号国家到第 $i$ 个国家最少需要经过几条路。

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

1
1
2
0
1

提示

对于所有测试点，保证 $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$。