← 返回题目列表

Codeforces · 786/B

B. 遗产

中文机器翻译题面 查看原题

瑞克和他的同事制作了一种新的放射性配方,许多坏人正在追捕他们。所以瑞克想在坏人抓住莫蒂之前把他的遗产交给莫蒂。

他们的宇宙中有n颗行星,编号从1到n。瑞克在 s 号行星(地球),他不知道莫蒂在哪里。众所周知,瑞克拥有一把传送枪。使用这把枪,他可以打开从他所在的行星到任何其他行星(包括该行星)的单向门户。但这把枪还是有限制的,因为他还在使用免费试用。

默认情况下,他无法用这把枪打开任何传送门。销售这些枪的网站上有 q 计划。每次购买套餐时,您只能使用一次,但如果您想更多地使用它,可以再次购买。

网站上的计划分为三种类型:

1. 通过这种类型的计划,你可以打开从行星 v 到行星 u 的传送门。
2. 通过这种类型的计划,你可以打开从行星 v 到任何索引在 [l, r] 范围内的行星的传送门。
3. 通过这种类型的计划,你可以从任何索引在 [l, r] 范围内的行星到 v 行星打开门户。

Rick 不知道 Morty 在哪里,但 Unity 会通知他,他希望在找到 Morty 时做好准备并立即开始他的旅程。因此,对于每个星球(包括地球本身),他想知道从地球到那个星球需要的最低金额。

输入

输入的第一行包含三个整数 n、q 和 s (1 ≤ n, q ≤ 105, 1 ≤ s ≤ n)——分别是行星数量、计划数量和地球索引。

接下来的 q 行包含计划。每行以数字 t 开头,即该计划的类型 (1 ≤ t ≤ 3)。如果 t = 1,则后面跟着三个整数 v、u 和 w,其中 w 是该计划的成本 (1 ≤ v、u ≤ n、1 ≤ w ≤ 109)。否则后面跟着四个整数 v、l、r 和 w,其中 w 是该计划的成本 (1 ≤ v ≤ n、1 ≤ l ≤ r ≤ n、1 ≤ w ≤ 109)。

输出

在输出的第一行也是唯一一行中打印 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

注意

在第一个示例测试用例中,Rick 可以购买第 4 个计划一次,然后购买第 2 个计划,以便到达 2 号行星。