English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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 .
[samples]
## Note
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.
Dr. Evil 对数学和函数感兴趣，因此他给了 Mahmoud 和 Ehab 一个长度为 $n$ 的数组 $a$ 和一个长度为 $m$ 的数组 $b$。他定义了一个函数 $f(j)$，该函数针对满足 $0 ≤ j ≤ m - n$ 的整数 $j$。设 $c_i = a_i - b_{i + j}$，则 $f(j) = |c_1 - c_2 + c_3 - c_4 + \dots + (-1)^{n+1} c_n|$。更形式化地，
Dr. Evil 希望 Mahmoud 和 Ehab 计算该函数在所有合法 $j$ 上的最小值。他们觉得这太简单了，于是 Dr. Evil 加大了难度：他会给出 $q$ 个更新查询。在每次更新中，他们需要将一个整数 $x_i$ 加到数组 $a$ 的区间 $[l_i; r_i]$ 中的所有元素上，即对 $a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$ 都加上 $x_i$，然后计算所有合法 $j$ 对应的 $f(j)$ 的最小值。
请帮助 Mahmoud 和 Ehab。
第一行包含三个整数 $n$, $m$ 和 $q$ ($1 ≤ n ≤ m ≤ 10^5$, $1 ≤ q ≤ 10^5$) —— 分别表示数组 $a$ 的元素个数、数组 $b$ 的元素个数和查询次数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 ≤ a_i ≤ 10^9$) —— 数组 $a$ 的元素。
第三行包含 $m$ 个整数 $b_1, b_2, \dots, 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$) —— 表示更新的区间和要加的值。
第一行应输出在任何更新之前函数 $f$ 的最小值。
然后输出 $q$ 行，第 $i$ 行应输出执行第 $i$ 次更新后函数 $f$ 的最小值。
对于第一个例子，在任何更新前，最优选择是 $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$。
## Input
第一行包含三个整数 $n$, $m$ 和 $q$ ($1 ≤ n ≤ m ≤ 10^5$, $1 ≤ q ≤ 10^5$) —— 分别表示数组 $a$ 的元素个数、数组 $b$ 的元素个数和查询次数。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 ≤ a_i ≤ 10^9$) —— 数组 $a$ 的元素。第三行包含 $m$ 个整数 $b_1, b_2, \dots, 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$) —— 表示更新的区间和要加的值。
## Output
第一行应输出在任何更新之前函数 $f$ 的最小值。然后输出 $q$ 行，第 $i$ 行应输出执行第 $i$ 次更新后函数 $f$ 的最小值。
[samples]
## Note
对于第一个例子，在任何更新前，最优选择是 $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$。
**Definitions**
Let $ n, m, q \in \mathbb{Z}^+ $ with $ 1 \leq n \leq m \leq 10^5 $, $ 1 \leq q \leq 10^5 $.
Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $, $ B = (b_1, b_2, \dots, b_m) \in \mathbb{Z}^m $.
For $ j \in \{0, 1, \dots, m - n\} $, define the sequence $ C_j = (c_{j,1}, c_{j,2}, \dots, c_{j,n}) $ where $ c_{j,i} = a_i - b_{i+j} $.
Define the function:
$$
f(j) = \left| \sum_{i=1}^{n} (-1)^{i-1} c_{j,i} \right| = \left| \sum_{i=1}^{n} (-1)^{i-1} (a_i - b_{i+j}) \right|
$$
**Constraints**
1. $ 1 \leq n \leq m \leq 10^5 $
2. $ 1 \leq q \leq 10^5 $
3. $ -10^9 \leq a_i, b_i \leq 10^9 $
4. Each update: $ 1 \leq l_i \leq r_i \leq n $, $ -10^9 \leq x_i \leq 10^9 $; add $ x_i $ to $ a_{l_i}, a_{l_i+1}, \dots, a_{r_i} $
**Objective**
Compute $ \min_{j \in \{0, 1, \dots, m - n\}} f(j) $ before any updates, and after each of the $ q $ updates.
API Response (JSON)
{
"problem": {
"name": "E. Mahmoud and Ehab and the function",
"description": {
"content": "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_, whic",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF862E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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_, whic...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Dr. Evil 对数学和函数感兴趣，因此他给了 Mahmoud 和 Ehab 一个长度为 $n$ 的数组 $a$ 和一个长度为 $m$ 的数组 $b$。他定义了一个函数 $f(j)$，该函数针对满足 $0 ≤ j ≤ m - n$ 的整数 $j$。设 $c_i = a_i - b_{i + j}$，则 $f(j) = |c_1 - c_2 + c_3 - c_4 + \\dots + (-1)^{...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq m \\leq 10^5 $, $ 1 \\leq q \\leq 10^5 $. \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $, $ B = (b_1, b_2, \\dots, b_m) \\in \\...",
"is_translate": false,
"language": "Formal"
}
]
}