CF862E.Mahmoud and Ehab and the function

Dr. Evil is interested in math and functions, so he gave Mahmoud and Ehab array a of length n and array b of length m. He introduced a function f(j) which is defined for integers j, which satisfy 0 ≤ j ≤ m - n. Suppose, c__i = a__i - b__i + j. Then f(j) = |_c_1 - _c_2 + _c_3 - _c_4... c__n|. More formally, .

Dr. Evil wants Mahmoud and Ehab to calculate the minimum value of this function over all valid j. They found it a bit easy, so Dr. Evil made their task harder. He will give them q update queries. During each update they should add an integer x__i to all elements in a in range [l__i;r__i] i.e. they should add x__i to a__l__i, a__l__i + 1, ... , a__r__i and then they should calculate the minimum value of f(j) for all valid j.

Please help Mahmoud and Ehab.

邪恶博士对数学和函数很感兴趣，因此他给了马哈茂德和埃哈布一个长度为 $ n $ 的数组 $ a $ 和一个长度为 $ m $ 的数组 $ b $。他定义了一个函数 $ f(j) $，其定义域为满足 $ 0 \leq j \leq m - n $ 的整数 $ j $。设 $ c_i = a_i - b_{i + j} $，则

$$f(j) = |c_1 - c_2 + c_3 - c_4 + \cdots \pm c_n|.$$

更形式化地，
。

邪恶博士希望马哈茂德和埃哈布计算该函数在所有合法 $ j $ 上的最小值。他们发现这题有点简单，于是邪恶博士加大了难度：他会给出 $ q $ 个更新操作。每次更新时，他们需将整数 $ x_i $ 加到数组 $ a $ 的区间 $ [l_i, r_i] $ 内的所有元素上（即对每个 $ k \in [l_i, r_i] $，执行 $ a_k \gets a_k + x_i $），然后重新计算所有合法 $ j $ 对应的 $ f(j) $ 的最小值。

请帮助马哈茂德和埃哈布解决这个问题。

The first line contains three integers n, m and q (1 ≤ n ≤ m ≤ 105, 1 ≤ q ≤ 105) — number of elements in a, number of elements in b and number of queries, respectively.

The second line contains n integers _a_1, _a_2, ..., a__n. ( - 109 ≤ a__i ≤ 109) — elements of a.

The third line contains m integers _b_1, _b_2, ..., b__m. ( - 109 ≤ b__i ≤ 109) — elements of b.

Then q lines follow describing the queries. Each of them contains three integers l__i r__i x__i (1 ≤ l__i ≤ r__i ≤ n,  - 109 ≤ x ≤ 109) — range to be updated and added value.

第一行包含三个整数 $n$、$m$ 和 $q$（$1 ≤ n ≤ m ≤ 10^5$，$1 ≤ q ≤ 10^5$），分别表示数组 $a$ 的元素个数、数组 $b$ 的元素个数以及查询次数。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（$-10^9 ≤ a_i ≤ 10^9$），表示数组 $a$ 的元素。

第三行包含 $m$ 个整数 $b_1,\,b_2,\,...,\,b_m$（$-10^9 ≤ b_i ≤ 10^9$），表示数组 $b$ 的元素。

接下来 $q$ 行，每行描述一个查询。每行包含三个整数 $l_i$、$r_i$、$x_i$（$1 ≤ l_i ≤ r_i ≤ n$，$-10^9 ≤ x_i ≤ 10^9$），表示待更新的区间及要加上的值。

The first line should contain the minimum value of the function f before any update.

Then output q lines, the i-th of them should contain the minimum value of the function f after performing the i-th update .

第一行应包含在任何更新之前函数 $f$ 的最小值。

随后输出 $q$ 行，其中第 $i$ 行应包含执行第 $i$ 次更新后函数 $f$ 的最小值。

For the first example before any updates it's optimal to choose j = 0, f(0) = |(1 - 1) - (2 - 2) + (3 - 3) - (4 - 4) + (5 - 5)| = |0| = 0.

After the first update a becomes {11, 2, 3, 4, 5} and it's optimal to choose j = 1, f(1) = |(11 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6) = |9| = 9.

After the second update a becomes {2, 2, 3, 4, 5} and it's optimal to choose j = 1, f(1) = |(2 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6)| = |0| = 0.

After the third update a becomes {1, 1, 2, 3, 4} and it's optimal to choose j = 0, f(0) = |(1 - 1) - (1 - 2) + (2 - 3) - (3 - 4) + (4 - 5)| = |0| = 0.

对于第一个样例，在任何更新之前，选择 $j = 0$ 是最优的，此时 $f(0) = |(1 - 1) - (2 - 2) + (3 - 3) - (4 - 4) + (5 - 5)| = |0| = 0$。

第一次更新后，数组 $a$ 变为 $\{11, 2, 3, 4, 5\}$，此时选择 $j = 1$ 是最优的，$f(1) = |(11 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6)| = |9| = 9$。

第二次更新后，数组 $a$ 变为 $\{2, 2, 3, 4, 5\}$，此时选择 $j = 1$ 是最优的，$f(1) = |(2 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6)| = |0| = 0$。

第三次更新后，数组 $a$ 变为 $\{1, 1, 2, 3, 4\}$，此时选择 $j = 0$ 是最优的，$f(0) = |(1 - 1) - (1 - 2) + (2 - 3) - (3 - 4) + (4 - 5)| = |0| = 0$。