No tag edit access

E. Mahmoud and Ehab and the function

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDr. 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.

Input

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.

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 .

Example

Input

5 6 3

1 2 3 4 5

1 2 3 4 5 6

1 1 10

1 1 -9

1 5 -1

Output

0

9

0

0

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.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2019 05:26:21 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|