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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class E {

	static final long INF = (long) 1e16;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt();
		int m = sc.nextInt();
		int q = sc.nextInt();
		long[] a = new long[n];
		long[] b = new long[m];

		long v1 = 0;
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			if(i % 2 == 0)
				v1 += a[i];
			else
				v1 -= a[i];
		}

		for (int i = 0; i < m; i++)
			b[i] = sc.nextInt();


		Long[] arr = new Long[m - n + 1];

		long v2 = 0;
		for (int i = 0; i < n; i++) {
			if(i % 2 == 0)
				v2 -= b[i];
			else
				v2 += b[i];
		}

		arr[0] = v1 + v2;
		for (int i = n; i < m; i++) {
			v2 += b[i - n];
			v2 *= -1;
			if(n % 2 == 0)
				v2 += b[i];
			else
				v2 -= b[i];
			arr[i - n + 1] = v1 + v2;
		}

		Arrays.sort(arr);

		long extra = 0;

		for (int i = 0; i <= q; i++) {
			if(i > 0){
				int l = sc.nextInt();
				int r = sc.nextInt();
				if(l % 2 == r % 2)
					if(l % 2 == 1)
						extra += sc.nextInt();
					else
						extra -= sc.nextInt();
				else
					sc.next();

			}
			int lo = 0;
			int hi = arr.length - 1;
			int ans = arr.length;

			while(lo <= hi) {
				int mid = (lo + hi) / 2;

				if(arr[mid] + extra >= 0) {
					ans = mid;
					hi = mid - 1;
				}else {
					lo = mid + 1;
				}

			}
			long v = INF;
			if(ans < arr.length)
				v = arr[ans] + extra;
			if(ans > 0)
				v = Math.min(v, -(arr[ans - 1] + extra));

			out.println(v);

		}

		out.flush();
		out.close();
	}





	static class Scanner 



	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
		public Scanner(String file) throws FileNotFoundException{	br = new BufferedReader(new FileReader(file));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}

		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}


		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if(x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for(int i = start; i < x.length(); i++)
				if(x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				}
				else
				{
					sb.append(x.charAt(i));
					if(dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}

		public boolean ready() throws IOException {return br.ready();}



	}


}