Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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* _{ 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* ≤ 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-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/16/2020 15:55:01 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|