Byteotia 有 $n$ 个城镇，编号为 $1$ 到 $n$。该国的高速公路修建频率不高；但一旦修建，通常会成批进行。目前已经修建了 $m$ 批高速公路，第 $i$ 批公路连接所有编号在 $[a_{i}, b_{i}]$ 范围内的城镇与编号在 $[c_{i}, d_{i}]$ 范围内的城镇。这些高速公路仅在城镇处交叉，但可能通过隧道或高架桥跨越。利用高速公路网络，可以在 Byteotia 的任意两个城镇之间通行。通过一条高速公路的费用恰好为 1 Bytean dollar。

Byteasar 在国外度过了过去几年。今年他决定回到祖国，并在首都 Bitcity 买一栋房子。他计划拜访他所有的老熟人，他们现在居住在 Byteotia 的许多不同城镇中。他想知道从 Bitcity 到 Byteotia 其他任何城镇的最廉价路线（仅使用高速公路网络）。请帮助他找出这些路线。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $p$ ($2 \le n \le 500\,000$, $1 \le m \le 100\,000$, $1 \le p \le n$)，分别代表 Byteotia 的城镇数量、已修建的高速公路批次数以及 Byteasar 居住的城镇编号（即 Bitcity）。接下来的 $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}, \ldots, b_{i}$ 中的每一个城镇，都有一条双向高速公路通往城镇 $c_{i}, \ldots, d_{i}$ 中的每一个城镇。每条高速公路最多出现在一批中。

输出格式

程序应向标准输出写入 $n$ 行。第 $i$ 行应包含从 Bitcity 到 Byteotia 第 $i$ 个城镇的最小通行费用（以 Bytean dollars 为单位）。这些行中的第 $p$ 行应包含数字 0。

样例

输入 1

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

输出 1

1
1
2
0
1