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.util.*;
import java.io.*;

public class JyMaYa {
    static class Edge implements Comparable<Edge>{
        int start,node;
        long val;
        Edge(int a,int b,long c){
            start=a;
            node=b;
            val=c;
        }

        @Override
        public int compareTo(Edge edge) {
            return Long.compare(val,edge.val);
        }
        public String toString(){
            return start+" "+node+" "+val;
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        int[]a=new int[n];
        int[]b=new int[m];
        long val=0;
        for (int i =0;i<n;i++){
            a[i]=sc.nextInt();
            if (i%2==0)val+=a[i];
            else val-=a[i];
        }
        long[]preodd=new long[m+1];
        long[]preeven=new long[m+1];
        for (int i =0;i<m;i++){
            b[i]=sc.nextInt();
            if (i%2==0)preeven[i]+=b[i];
            else preodd[i]+=b[i];
            if (i>0){
                preeven[i]+=preeven[i-1];
                preodd[i]+=preodd[i-1];
            }
        }
        TreeSet<Long>pos=new TreeSet<>();
        TreeSet<Long>neg=new TreeSet<>();
        for (int i =0;i<=m-n;i++){
            long v= 0;
            if (i%2==0){
                v-=preeven[i+n-1]-(i==0?0:preeven[i-1]);
                v+=preodd[i+n-1]-(i==0?0:preodd[i-1]);
            }
            else {
                v-=preodd[i+n-1]-(i==0?0:preodd[i-1]);
                v+=preeven[i+n-1]-(i==0?0:preeven[i-1]);
            }
            if (v<0)neg.add(Math.abs(v));
            else pos.add(v);
        }
        long s=10000000000000000l;
        if (val<0){
            if (!neg.isEmpty())s=Math.abs(val-neg.first());
            Long x = pos.ceiling(Math.abs(val));
            Long z = pos.floor(Math.abs(val));
            if (x!=null)s=Math.min(s,Math.abs(val+x));
            if (z!=null)s=Math.min(s,Math.abs(val+z));
        }
        else {
            if (!pos.isEmpty())s=Math.abs(val+pos.first());
            Long x = neg.ceiling(val);
            Long z = neg.floor(val);
            if (x!=null)s=Math.min(s,Math.abs(val-x));
            if (z!=null)s=Math.min(s,val-z);
        }
        pw.println(s);
        while (q-->0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            int c = sc.nextInt();
            if ((r-l)%2==0){
                if (l%2==1)val+=c;
                else val-=c;
            }
            long res=100000000000000000l;
            if (val<0){
                if (!neg.isEmpty())res=Math.abs(val-neg.first());
                Long x = pos.ceiling(Math.abs(val));
                Long z = pos.floor(Math.abs(val));
                if (x!=null)res=Math.min(res,Math.abs(val+x));
                if (z!=null)res=Math.min(res,Math.abs(val+z));
            }
            else {
                if (!pos.isEmpty())res=Math.abs(val+pos.first());
                Long x = neg.ceiling(val);
                Long z = neg.floor(val);
                if (x!=null)res=Math.min(res,Math.abs(val-x));
                if (z!=null)res=Math.min(res,val-z);
            }
            pw.println(res);
        }
        pw.flush();
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        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();
        }
    }

    static class Pair {
        int idx, val;

        Pair(int a, int b) {
            val = a;
            idx = b;
        }
    }


}