markdown

B. 遗产

里克和他的同事们研制出了一种新的放射性配方，许多坏蛋正在追捕他们。因此，里克希望在坏蛋抓住他们之前，把自己的遗产交给莫蒂。

在他们的宇宙中有 $n$ 颗行星，编号从 $1$ 到 $n$。里克在编号为 $s$ 的行星（地球）上，但他不知道莫蒂在哪里。众所周知，里克拥有一把传送枪。使用这把枪，他可以从当前所在的行星打开一条单向传送门到任何其他行星（包括当前行星）。但由于他还在使用免费试用版，这把枪有一些限制。

默认情况下，他无法用这把枪打开任何传送门。售卖这把枪的网站上提供了 $q$ 种方案。每次购买一种方案，你只能使用一次，但如果想多次使用，可以再次购买。

网站上的方案分为三种类型：

• 类型 $1$：使用这种方案，你可以从行星 $v$ 打开一条传送门到行星 $u$。
• 类型 $2$：使用这种方案，你可以从行星 $v$ 打开一条传送门到任意编号在 $[l, r]$ 范围内的行星。
• 类型 $3$：使用这种方案，你可以从任意编号在 $[l, r]$ 范围内的行星打开一条传送门到行星 $v$。

里克不知道莫蒂在哪里，但 Unity 会通知他，他希望做好准备，一旦找到莫蒂就能立即开始旅程。因此，对于每一颗行星（包括地球本身），他想知道从地球到达该行星所需的最少花费。

输入

第一行包含三个整数 $n$、$q$ 和 $s$（$1 \le n, q \le 10^5$，$1 \le s \le n$）—— 分别表示行星的数量、方案的数量以及地球的编号。

接下来的 $q$ 行包含这些方案。每行以一个数字 $t$ 开头，表示该方案的类型（$1 \le t \le 3$）。如果 $t = 1$，则后面跟着三个整数 $v$、$u$ 和 $w$，其中 $w$ 是该方案的花费（$1 \le v, u \le n$，$1 \le w \le 10^9$）。否则，后面跟着四个整数 $v$、$l$、$r$ 和 $w$，其中 $w$ 是该方案的花费（$1 \le v \le n$，$1 \le l \le r \le n$，$1 \le w \le 10^9$）。

输出

在唯一的一行输出中，打印 $n$ 个整数，用空格分隔。第 $i$ 个数应为从地球到达第 $i$ 颗行星所需的最少花费，如果无法到达该行星，则输出 $-1$。

样例

样例输入 1

3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17

样例输出 1

0 28 12

样例输入 2

4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16

样例输出 2

0 -1 -1 12

注释

在第一个样例中，里克可以先购买第 $4$ 种方案一次，再购买第 $2$ 种方案，从而到达第 $2$ 颗行星。