Migrated from Lutece 2972 欢迎来到基沃托斯

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

”欢迎来到鸡窝脱丝，sensei！“

现在，你作为桃井和小绿的老师，需要指导她们如何作战。战场可以看作一个二维坐标系，有很多 $2\times 2$ 或 $3\times 3$ 大小的正方形平台放在上面（没有两个大小完全一样且重合的平台），第 $i$ 个平台会有个时间流速因子 $v_i$，如果两个正方形平台有重叠区域，那么就可以从一个平台移动到另外一个平台，设重叠面积大小为 $S$，如果两个平台是同种平台，那么移动花费时间为 $S\times (v_i + v_j)$，如果两个平台大小不一样，也就是说不是同种平台，那么移动花费时间为 $S\times |v_i-v_j|$。

现在，你知道了整个战场的地图，还有桃井和小绿初始所在的平台编号 $s$，你需要快速告诉她们，从初始平台到其他所有平台所需的最短时间，如果无法到达则告诉她们 nye。

Input

第一行两个数字 $n,s$ 表示正方形平台个数和初始所在平台编号（编号从 $1$ 开始）。

接下来一行 $n$ 个数字表示平台时间流速因子 $v_i$。

接下来 $n$ 行，每行三个整数 $x,y,c$，表示该正方形平台的左下角坐标和大小（$c\in\{2,3\}$）。

Output

输出 $n$ 行，第 $i$ 行表示从 $s$ 初始平台到第 $i$ 号平台所需时间，无法到达则输出一个字符串 nye。

Samples

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

0 
1
nye
3
7

Constraints

$$1\leq n\leq 10^5,1\leq s\leq n\\ 1\leq v_i\leq 10^5\\ 1\leq x\leq 1000,1\leq y\leq 10^9\\ c\in\{2,3\} $$

保证所有的时间流速因子不同。

Note

样例如图所示，最后简化的路径图也如上。

Resources

2023 UESTC ICPC Training for Graph