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 main
{
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	//private static long mod = 1000000000 + 7;
	private static long mod=100000000;
	private static long mod1 = 1000000000 + 9;
	private static void soln()
	{
		int n=nextInt();
		int m=nextInt();
		int q=nextInt();
		long[] a=new long[n];
		long[] b=new long[m];
		long suma=0;
		for(int i=0;i<n;i++) {
			a[i]=nextLong();
			if(i%2==0) {
				suma+=a[i];
			}else
				suma-=a[i];
		}
		long sumb=0;
		TreeSet<Long> set=new TreeSet<>();
		long minb=Long.MAX_VALUE;
		long maxb=Long.MIN_VALUE;
		for(int i=0;i<m;i++) {
			b[i]=nextLong();
			if(i<n) {
				if(i%2==0) {
					sumb+=b[i];
				}else
					sumb-=b[i];
			}else {
				minb=Math.min(minb, sumb);
				maxb=Math.max(maxb, sumb);
				set.add(sumb);
				sumb-=b[i-n];
				sumb*=-1;
				if((n-1)%2==0) {
					sumb+=b[i];
				}else
					sumb-=b[i];
			}
			//System.out.println(sumb);
		}
		set.add(sumb);
		Long b1=set.ceiling(suma);
		Long b2=set.floor(suma);
		long ans=Long.MAX_VALUE;
		if(b1!=null) {
			ans=Math.min(ans, Math.abs(suma-b1));
		}
		if(b2!=null) {
			ans=Math.min(ans, Math.abs(suma-b2));
		}
		pw.println(ans);
		for(int i=0;i<q;i++) {
			int l=nextInt()-1;
			int r=nextInt()-1;
			long w=nextLong();
			int dist=(r-l+1);
			if(dist%2!=0) {
				if(l%2==0) {
					suma+=w;
				}else
					suma-=w;
			}
			b1=set.ceiling(suma);
			b2=set.floor(suma);
			ans=Long.MAX_VALUE;
			if(b1!=null) {
				ans=Math.min(ans, Math.abs(suma-b1));
			}
			if(b2!=null) {
				ans=Math.min(ans, Math.abs(suma-b2));
			}
			pw.println(ans);
		}
 	}
	private static void dfs(int cur,int prev,LinkedList<Integer>[] l,int[] arr,int c) {
		arr[cur]=c;
		Iterator<Integer> it=l[cur].listIterator();
		while(it.hasNext()) {
			int x=it.next();
			if(x!=prev) {
				dfs(x,cur,l,arr,(c+1)%2);
			}
		}
	}
	private static int[] buildSuffix(String s,int n){
		Integer[] order=new Integer[n];
		for(int i=0;i<n;i++) order[i]=n-i-1;
		Arrays.sort(order,(a,b) -> Character.compare(s.charAt(a),s.charAt(b)));
		int[] sa=new int[n];
		int[] m_tmp=new int[n];
		for(int i=0;i<n;i++){
			sa[i]=order[i];
			m_tmp[i]=s.charAt(i);
		}
		for(int len=1;len<n;len<<=1){
			int[] tmp=m_tmp.clone();
			m_tmp[sa[0]]=0;
			for(int i=1;i<n;i++){
				m_tmp[sa[i]] = (tmp[sa[i-1]]==tmp[sa[i]] && sa[i-1] + len < n && 
								tmp[(sa[i-1]+(len>>1))]==tmp[(sa[i]+(len>>1))]) ? m_tmp[sa[i-1]]:i;
			}
			int[] cnt=new int[n];
			for(int i=0;i<n;i++) cnt[i]=i;
			int[] sa_tmp=sa.clone();
			for(int i=0;i<n;i++){
				int s1=sa_tmp[i]-len;
				if(s1>=0)
					sa[cnt[m_tmp[s1]]++]=s1;
			}
		}
		return sa;
	}
	private static int[] buildLCP(int[] sa,String s,int n){
		int[] ind=new int[n];
		for(int i=0;i<n;i++)
			ind[sa[i]]=i;
		int[] lcp=new int[n];
		for(int i=0, k=0; i<n; i++)
			if(ind[i] < n-1){
				for(int j=sa[ind[i]+1]; Math.max(i,j)+k < n && s.charAt(i+k)==s.charAt(j+k);) k++;
				lcp[ind[i]]=k;
				if(k>0) k--;
			}
		return lcp;
	}
	private static class Edge{
		int u,v;
		public Edge(int a,int b) {
			u=a;v=b;
		}
	}
	private static void shortestPath(LinkedList<Edge>[] l,int n,int k,int[] masks) {
		int tot=(int) Math.pow(2,k);
		int[][] dist=new int[n][tot];
		int[][] from=new int[n][tot];
		for(int i=0;i<n;i++)
			Arrays.fill(dist[i], Integer.MAX_VALUE);
		dist[0][masks[0]]=0;
		from[0][masks[0]]=-1;
		PriorityQueue<Long> q=new PriorityQueue<>();
		q.add((long) masks[0]);
		//System.out.println(0);
		while(!q.isEmpty()) {
			long cur=q.poll();
			//System.out.println(cur);
			int u = ((int) cur)>>>10;
			int mask=(int) (cur&(tot-1));
			//System.out.println((u+1)+" "+mask+" "+dist[u][mask]);
			if((cur>>>32) != dist[u][mask])
				continue;
			//System.out.println((u+1)+" "+Integer.toBinaryString(mask)+" "+dist[u][mask]);
			Iterator<Edge> it=l[u].listIterator();
			while(it.hasNext()) {
				Edge e=it.next();
				int len=dist[u][mask]+e.v;
				if(dist[e.u][mask|masks[e.u]]>len) {
					//System.out.println((e.u+1)+" "+(mask|masks[e.u])+" "+len+" "+Long.toBinaryString(((long)len << 32)+(e.u<<10)+mask));
					dist[e.u][mask|masks[e.u]]=len;
					from[e.u][mask|masks[e.u]]=u;
					q.add(((long)len << 32)+(e.u<<10)+(mask|masks[e.u]));
				}
			}
		}
		int ans=Integer.MAX_VALUE;
		//System.out.println(Integer.toBinaryString(tot-1));
		for(int i=0;i<tot;i++) {
			for(int j=0;j<tot;j++) {
				//System.out.println(Integer.toBinaryString(i)+" "+Integer.toBinaryString(j)+" "+dist[n-1][i]+" "+dist[n-1][j]);
				if((i|j) != (tot-1))
					continue;
				//System.out.println(i+" "+j);
				ans=Math.min(ans,Math.max(dist[n-1][i],dist[n-1][j]));
			}
		}
		pw.println(ans);
	}
	private static class Pair1 implements Comparable<Pair1>{
		int dist, affected, u;
		public Pair1(int a) {
			dist=Integer.MAX_VALUE;
			affected=Integer.MAX_VALUE;
			u=a;
		}
		public int compareTo(Pair1 another) {
			return this.dist!=another.dist?this.dist-another.dist:this.affected-another.affected;
		}
	}
	static void multiply(long[][] a, long[][] b, long m)
	{
		int n = a.length;
		long[][] mul = new long[n][n];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				mul[i][j] = 0;
				for (int k = 0; k < n; k++)
					mul[i][j] = (mul[i][j] + (a[i][k] * b[k][j]) % m) % m;
			}
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				a[i][j] = mul[i][j];
	}
	private static class DSU{
		int[] parent;
		int[] rank;
		int[][] lr;
		public DSU(int n){
			parent=new int[n];
			rank=new int[n];
			lr=new int[n][2];
			//cnt=new int[n];
			for(int i=0;i<n;i++){
				parent[i]=i;
				rank[i]=1;
				lr[i][0]=lr[i][1]=i;
				//cnt[i]=1;
			}
		}
		int find(int i){
	        while(parent[i] !=i){
	        	parent[i]=parent[parent[i]];
	        	i=parent[i];
	        }
	        return i;
	    }
		int Union(int x, int y){
	        int xset = find(x);
	        int yset = find(y);
	        if(xset==yset)
	        	return 0;
	        	parent[yset]=xset;
	        	rank[xset]+=rank[yset];
	        	rank[yset]=0;
	        	lr[xset][1]=lr[yset][1];
	        	lr[yset][0]=lr[xset][0];
	        	//cnt[xset]+=cnt[yset];
	        	//cnt[yset]=0;
	        	return xset;
	    }
	}

	private static long pow(long a, long b, long c)
	{
		if (b == 0)
			return 1;
		long p = pow(a, b / 2, c);
		p = (p * p) % c;
		return (b % 2 == 0) ? p : (a * p) % c;
	}
	private static int block;
	private static class Mo implements Comparable<Mo>
	{
		int l;
		int r;
		int i;

		public Mo(int a, int b, int ind)
		{
			l = a;
			r = b;
			i = ind;
		}

		@Override
		public int compareTo(Mo arg0)
		{
			int b1 = this.l / block;
			int b2 = arg0.l / block;
			return (b1 != b2) ? (b1 - b2) : (this.r - arg0.r);
		}
	}

	private static long gcd(long n, long l)
	{
		if (l == 0)
			return n;
		return gcd(l, n % l);
	}
	public static void main(String[] args) throws Exception
	{
		new Thread(null, new Runnable()
		{
			@Override
			public void run()
			{
				/*
				 * try { InputReader(new FileInputStream(
				 * "C:\\Users\\hardik\\Desktop\\C-small-1-attempt1.in")); } catch
				 * (FileNotFoundException e) { // TODO Auto-generated catch block
				 * e.printStackTrace(); }
				 */
				InputReader(System.in);
				pw = new PrintWriter(System.out);
				/*
				 * try { pw=new PrintWriter(new
				 * FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt")); } catch
				 * (FileNotFoundException e) { // TODO Auto-generated catch block
				 * e.printStackTrace(); }
				 */
				soln();
				pw.close();
			}
		}, "1", 1 << 26).start();
	}

	public static void InputReader(InputStream stream1)
	{
		stream = stream1;
	}

	private static boolean isWhitespace(int c)
	{
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private static boolean isEndOfLine(int c)
	{
		return c == '\n' || c == '\r' || c == -1;
	}

	private static int read()
	{
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars)
		{
			curChar = 0;
			try
			{
				numChars = stream.read(buf);
			} catch (IOException e)
			{
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	private static int nextInt()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-')
		{
			sgn = -1;
			c = read();
		}
		int res = 0;
		do
		{
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static long nextLong()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-')
		{
			sgn = -1;
			c = read();
		}
		long res = 0;
		do
		{
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static String nextToken()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do
		{
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private static String nextLine()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do
		{
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	private static int[] nextIntArray(int n)
	{
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
		{
			arr[i] = nextInt();
		}
		return arr;
	}

	private static long[] nextLongArray(int n)
	{
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
		{
			arr[i] = nextLong();
		}
		return arr;
	}

	private static void pArray(int[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static void pArray(long[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static boolean isSpaceChar(int c)
	{
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private static char nextChar()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		char c1 = (char) c;
		while (!isSpaceChar(c))
			c = read();
		return c1;
	}

	private interface SpaceCharFilter
	{
		public boolean isSpaceChar(int ch);
	}
}