A11225 | 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_{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 .