← 返回题目列表

Codeforces · 1148/E

E. 地风火

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

有 $$$n$$$ 石头排列在轴上。最初,第 $$$i$$$ 块石头位于坐标 $$$s_i$$$ 处。一个地方可能有不止一块石头。

您可以执行零个或多个以下类型的操作:

- 取两颗索引为 $$$i$$$ 和 $$$j$$$ 的棋子,使得 $$$s_i \leq s_j$$$,选择一个整数 $$$d$$$ ($$$0 \leq 2 \cdot d \leq s_j - s_i$$$),并将坐标 $$$s_i$$$ 替换为 $$$(s_i + d)$$$ 并将坐标 $$$s_j$$$ 替换为 $$$(s_j - d)$$$。换句话说,让石头彼此靠近。

您想要移动棋子,使它们位于位置 $$$t_1, t_2, \ldots, t_n$$$。棋子的顺序并不重要——您只需要棋子结果位置的多重集与 $$$t_1, t_2, \ldots, t_n$$$ 的多重集相同。

检测是否可以用这种方式移动石头,如果可以,则构造一种方法来这样做。您不需要最小化移动次数。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) – 石头的数量。

第二行包含整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — 棋子的初始位置。

第二行包含整数 $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le 10^9$$$) — 棋子的目标位置。

输出

如果无法通过这种方式移动棋子,请打印“NO”。

否则,在第一行打印“YES”,在第二行打印所需的操作数 $$$m$$$ ($$$0 \le m \le 5 \cdot n$$$)。您不必最小化操作次数。

然后打印 $$$m$$$ 行,每行包含整数 $$$i, j, d$$$ ($$$1 \le i, j \le n$$$, $$$s_i \le s_j$$$, $$$0 \leq 2 \cdot d \leq s_j - s_i$$$),定义操作。

可以证明,如果存在答案,则存在一个需要不超过 $$$5 \cdot n$$$ 操作的答案。

示例

输入 #1

5
2 2 7 4 9
5 4 5 5 5

输出 #1

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

输入 #2

3
1 5 10
3 5 7

输出 #2

NO

注意

考虑第一个例子。

- 第一次移动后,棋子的位置为 $$$[2, 2, 6, 5, 9]$$$。
- 第二次移动后,棋子的位置为 $$$[2, 3, 5, 5, 9]$$$。
- 第三次移动后,棋子的位置为 $$$[2, 5, 5, 5, 7]$$$。
- 最后一步移动后,棋子的位置为 $$$[4, 5, 5, 5, 5]$$$。