在二维平面上有一只飞鼠和 $N$ 根柱子。

二维平面上的一个点可以表示为 $(x, y)$。其中，$x$ 表示水平位置，$y$ 表示高度。水平位置 $x$ 增大的方向为向右，高度 $y$ 增大的方向为向上。

柱子从 $0$ 号到 $N-1$ 号依次编号。第 $i$ 根柱子的底部位于点 $(i, 0)$，高度无限。因此，第 $i$ 根柱子是从点 $(i, 0)$ 开始向上延伸的射线。每根柱子是红色或蓝色的。若 $B[i] = 0$，则第 $i$ 根柱子为红色；若 $B[i] = 1$，则第 $i$ 根柱子为蓝色。

初始时，飞鼠位于点 $(0, 0)$。飞鼠希望到达点 $(N, H)$。为此，飞鼠按如下方式移动。

在没有柱子的地方，飞鼠保持当前高度向右飞行。由于飞鼠速度极快，此时所需时间视为 $0$。

在有柱子的地方，飞鼠可以将自身高度增加 $A[i]$，或者什么也不做。具体而言，在第 $i$ 根柱子处（$0 \le i \le N - 1$），飞鼠必须执行以下三种行为之一：

• 直接经过柱子。飞鼠高度保持不变，并继续向右飞行。所需时间为 $0$。
• 爬柱子。仅当该柱子为红色时（$B[i] = 0$）才可执行。飞鼠的高度在该柱子处增加 $1$，然后继续向右飞行。所需时间为 $A[i]$。
• 在柱子处跳跃。仅当该柱子为蓝色时（$B[i] = 1$）才可执行。飞鼠的高度在该柱子处增加 $1$，然后继续向右飞行。所需时间为 $A[i]$。

此外，当飞鼠经过水平位置 $i + 0.5$（$0 \le i \le N - 1$）时，其高度必须满足 $L[i] \le y \le R[i]$。

当飞鼠到达水平位置 $N$ 时，其高度必须恰好为 $H$。

在满足以上所有条件并到达 $(N, H)$ 的所有方法中，若飞鼠跳跃的次数恰好为 $k$ 次，则定义所需总时间的最小值为 $T[k]$。如果不存在这样的方案，则定义 $T[k] = -1$。

请计算 $T[0], T[1], \dots, T[H]$。

实现细节

需要实现以下函数：

vector<long long> fly(int H, vector<int> A, vector<int> B, vector<int> L, vector<int> R)

• $H$：飞鼠的目标高度。
• $A, B, L, R$：大小为 $N$ 的整数数组。
• $B$：表示柱子颜色的数组。若 $B[i] = 0$，则第 $i$ 根柱子为红色；若 $B[i] = 1$，则第 $i$ 根柱子为蓝色。
• 该函数应返回一个大小为 $H + 1$ 的数组 $T$。
• 该函数只会被调用一次。

限制

• $1 \le N \le 200\,000$
• $0 \le H \le N$
• $0 \le A[i] \le 10^9 \quad (0 \le i \le N - 1)$
• $0 \le B[i] \le 1 \quad (0 \le i \le N - 1)$
• $0 \le L[i] \le R[i] \le N \quad (0 \le i \le N - 1)$

子任务

1. (3 分) $N \le 300$
2. (4 分) 对所有 $0 \le i \le N - 1$，$A[i] = B[i] = 0$
3. (25 分) 对所有 $0 \le i \le N - 1$，$B[i] = 0$
4. (20 分) $N \le 65\,000$，且对所有 $0 \le i \le N - 1$，$A[i] \le 5$
5. (29 分) $N \le 65\,000$
6. (19 分) 无额外限制

样例数据

样例 1

考虑以下调用：

fly(3, [8, 8, 2, 4], [1, 0, 1, 0], [1, 0, 2, 3], [1, 2, 2, 4])

若在第 $0$ 根柱子跳跃，并在第 $1$、$3$ 根柱子爬升，则满足条件。此时跳跃次数为 $1$，所需时间为 $20$。

若在第 $0$、$2$ 根柱子跳跃，并在第 $3$ 根柱子爬升，则满足条件。此时跳跃次数为 $2$，所需时间为 $14$。

不存在其他可行方法。因此，函数应返回 $[-1, 20, 14, -1]$。

样例 2

考虑以下调用：

fly(1, [1000000000], [0], [1], [1])

函数应返回 $[1000000000, -1]$。

样例 3

考虑以下调用：

fly(3, [4, 7, 0, 3, 8, 4, 5], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 1, 2], [5, 1, 2, 5, 5, 6, 3])

函数应返回 $[7, -1, -1, -1]$。

样例 4

考虑以下调用：

fly(7, [3, 3, 4, 1, 3, 2, 0, 1, 4, 3, 4, 0, 0, 1, 0, 4, 4, 5, 5, 0],  
[1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1],  
[0, 0, 1, 1, 2, 1, 2, 2, 1, 1, 0, 1, 1, 3, 2, 2, 1, 6, 4, 4],  
[3, 2, 3, 3, 6, 2, 2, 4, 3, 4, 4, 5, 3, 6, 6, 5, 7, 8, 8, 9])

函数应返回 $[-1, 16, 11, 10, 9, 10, 12, 15]$。

样例交互库

样例交互库的输入格式如下：

• 第 1 行：$N$ $H$
• 第 2 行：$A[0]$ $A[1]$ … $A[N - 1]$
• 第 3 行：$B[0]$ $B[1]$ … $B[N - 1]$
• 第 4 行：$L[0]$ $L[1]$ … $L[N - 1]$
• 第 5 行：$R[0]$ $R[1]$ … $R[N - 1]$

样例交互库输出格式如下：

• 第 1 行：$T[0]$ $T[1]$ … $T[H]$