时空限制

1S/512M

题目描述

给定两个长度为 $n$ 的数组 $A$ 和 $B$（下标从 $1$ 开始）。你希望通过若干次操作，使得 $A$ 与 $B$ 完全相同。

允许执行以下两种基础操作任意次：

• 操作 $1$：选择下标 $i$（$1 \le i < n$），将 $A_i$ 减少 $1$，$A_{i+1}$ 增加 $1$。
• 操作 $2$：选择下标 $i$（$1 \le i < n$），将 $A_i$ 增加 $1$，$A_{i+1}$ 减少 $1$。

接下来你需要处理 $q$ 次查询。每次查询给出三个参数：type, i, k，表示对当前数组 $A$ 进行一次修改，然后回答问题。

修改规则如下：

• 若 type = 1，则将 $A_i$ 减少 $k$，$A_{i+1}$ 增加 $k$；
• 若 type = 2，则将 $A_i$ 增加 $k$，$A_{i+1}$ 减少 $k$。

注意：每次查询的修改是永久性的，后续查询基于之前修改后的数组 $A$ 进行。

在每次查询执行修改后，请输出：将当前数组 $A$ 变为数组 $B$ 所需的最少基础操作次数。如果无法达成，则输出 $-1$。

格式

输入格式

第一行包含两个整数 $n, q$，分别表示数组的长度和查询的次数。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示数组 $A$ 的初始值。

第三行包含 $n$ 个整数 $B_1, B_2, \dots, B_n$，表示数组 $B$ 的初始值 。

接下来 $q$ 行，每行包含三个整数 type, i, k，描述一次查询。具体意义见题目描述。

输出格式

对于每次查询，输出一行。

如果可能使数组 $A$ 变成数组 $B$，则输出一个整数，表示所需的最小基础操作次数。

如果不可能，则输出 $-1$。

样例

样例输入 #1

3 2
1 2 6
3 3 3
1 1 1
2 2 2

样例输出 #1

6
4

数据规模

对于 $50\%$ 的数据，$2 \leq n ,q\leq 1000$。

对于 $100\%$ 的数据，$2 \leq n, q \leq 2 \times 10^5$，查询时的 $1 \leq i < n$，$1 \leq A_i, B_i, k \leq 10^6$。