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, ci = ai - bi + j. Then f(j) = |c1 - c2 + c3 - c4... cn|. More formally, <image>. 

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 xi to all elements in a in range [li;ri] i.e. they should add xi to ali, ali + 1, ... , ari 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 ≤ 105, 1 ≤ q ≤ 105) — number of elements in a, number of elements in b and number of queries, respectively.

The second line contains n integers a1, a2, ..., an. ( - 109 ≤ ai ≤ 109) — elements of a.

The third line contains m integers b1, b2, ..., bm. ( - 109 ≤ bi ≤ 109) — elements of b.

Then q lines follow describing the queries. Each of them contains three integers li ri xi (1 ≤ li ≤ ri ≤ n,  - 109 ≤ x ≤ 109) — 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.
import java.io.*;
import java.util.*;

public class Codeforces862E {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sp = br.readLine().split(" ");
		//Scanner input = new Scanner(System.in);
		int n = Integer.parseInt(sp[0]);
		int m = Integer.parseInt(sp[1]);
		int q = Integer.parseInt(sp[2]);
		
		sp = br.readLine().split(" ");
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sp[i]);
		}
		sp = br.readLine().split(" ");
		int[] b = new int[m];
		for (int i = 0; i < m; i++) {
			b[i] = Integer.parseInt(sp[i]);
		}
		
		long asum = (long) a[n-1];
		for (int i = n-2; i >= 0; i--) {
			asum = (long) a[i] - asum;
		}
		
		long[][] bsum = new long[m-n+1][2];
		bsum[0][1] = (long) b[n-1];
		for (int i = n-2; i >= 0; i--) {
			bsum[0][1] = (long) b[i] - bsum[0][1];
		}
		
		if (n%2 == 1) {
			for (int i = 1; i < m-n+1; i++) {
				bsum[i][1] = (long) b[i-1] + (long) b[i+n-1] - bsum[i-1][1];
			}
		}
		else {
			for (int i = 1; i < m-n+1; i++) {
				bsum[i][1] = (long) b[i-1] - (long) b[i+n-1] - (long) bsum[i-1][1];
			}
		}
		
		for (int i = 0; i < m-n+1; i++) {
			bsum[i][0] = i;
		}
		
		keysort(bsum, 1);
		
		long[] bSum = new long[m-n+1];
		for (int i = 0; i < m-n+1; i++) {
			bSum[i] = bsum[i][1];
		}
		int k = findIndex(asum, bSum);
		if (k == m-n+1) {
			System.out.println(Math.abs(bsum[m-n][1]-asum));
		}
		else if (k == 0) {
			System.out.println(Math.abs(bsum[0][1]-asum));
		}
		else {
			System.out.println(Math.min(Math.abs(bsum[k][1]-asum), Math.abs(bsum[k-1][1]-asum)));
		}
		
		for (int i = 0; i < q; i++) {
			sp = br.readLine().split(" ");
			int l = Integer.parseInt(sp[0]);
			int r = Integer.parseInt(sp[1]);
			int x = Integer.parseInt(sp[2]);
			if ((r-l)%2 == 0) {
				if (r%2 == 0) {
					asum -= x;
				}
				else {
					asum += x;
				}
			}
			k = findIndex(asum, bSum);
			if (k == m-n+1) {
				System.out.println(Math.abs(bsum[m-n][1]-asum));
			}
			else if (k == 0) {
				System.out.println(Math.abs(bsum[0][1]-asum));
			}
			else {
				System.out.println(Math.min(Math.abs(bsum[k][1]-asum), Math.abs(bsum[k-1][1]-asum)));
			}
		}
		
	}
	
	public static void keysort(long[][] array, int index) {
    	int N = array.length;
    	if (N != 1) {
    		long[][] firstHalf = Arrays.copyOfRange(array, 0, N/2);
    		keysort(firstHalf, index);
        	long[][] secondHalf = Arrays.copyOfRange(array, N/2, N);
        	keysort(secondHalf, index);
        	int firstCounter = 0;
        	int secondCounter = 0;
        	for (int i = 0; i < N; i++) {
        		if (firstCounter == N/2) {
        			array[firstCounter+secondCounter] = secondHalf[secondCounter];
        			secondCounter++;
        		}
        		else if ((secondCounter == N-N/2) || firstHalf[firstCounter][index] <= secondHalf[secondCounter][index]) {
        			array[firstCounter+secondCounter] = firstHalf[firstCounter];
        			firstCounter++;
        		}
        		else {
        			array[firstCounter+secondCounter] = secondHalf[secondCounter];
        			secondCounter++;
        		}
        	}
    	}	
    }
	
	//return smallest index which is at least n in sorted list of distinct elements
	public static int findIndex(long n, long[] list) {
		int r = list.length;
		if (n > list[r-1])
			return r;
		else if (r == 1) {
			return 0;
		}
		else {
			int low = 0;
			int high = r-1;
			int val = 0;
			while (low < high) {
				val = (low+high)/2;
				if (list[val] == n)
					return val;
				else if (list[val] > n)
					high = val;
				else
					low = val+1;
			}
			return high;
		}
	}
}