Mahmoud and Ehab and the function

## 题目描述 给出长度为 $n$ 的数组 $a$ 和长度为 $m$ 的数组 $b$，定义函数 $f(j)$ ($0$ $≤$ $j$ $≤$ $m$ −$n$) 如图所示（未翻译的题面中的图），共有 $q$ 次更新，每次更新将 $a$ 数组中下标为 $l $\~$ r$ 中的每个数加上 $x$，对于原数组和每次更新后的数组，求 $f(j)$ 的最小值 ## 输入格式 第一行包含三个整数 $n$ ，$m$ ，$q$ $(1<=n<=m<=10^{5},1<=q<=10^{5})$ 第二行 $n$ 个整数，即数组 $a$ 第三行 $m$ 个整数，即数组 $b$ 接下来 $q$ 行，每行三个整数 $l$ ，$r$ ，$x$ ## 输出格式 第一行一个整数，即原数组的 $f(j)$ 的最小值 接下来 $q$ 行，每行一个整数，即每次更新后的数组的 $f(j)$ 最小值

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_{li},a_{li}+1,...\ ,a_{ri} $ and then they should calculate the minimum value of $ f(j) $ for all valid $ j $ . Please help Mahmoud and Ehab.

The first line contains three integers $ n,m $ and $ q $ ( $ 1<=n<=m<=10^{5} $ , $ 1<=q<=10^{5} $ ) — 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} $ . ( $ -10^{9}<=a_{i}<=10^{9} $ ) — elements of $ a $ . The third line contains $ m $ integers $ b_{1},b_{2},...,b_{m} $ . ( $ -10^{9}<=b_{i}<=10^{9} $ ) — 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 $ , $ -10^{9}<=x<=10^{9} $ ) — range to be updated and added value.

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 .

5 6 3
1 2 3 4 5
1 2 3 4 5 6
1 1 10
1 1 -9
1 5 -1

0
9
0
0

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 $ .