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* ≤ 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 .

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