瑞克和他的同事制作了一种新的放射性配方,许多坏人正在追捕他们。所以瑞克想在坏人抓住莫蒂之前把他的遗产交给莫蒂。
他们的宇宙中有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 号行星。