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.IOException;
import java.io.InputStreamReader;
import java.util.NavigableSet;
import java.util.TreeSet;
import java.util.function.Function;

import static java.lang.Long.*;
import static java.lang.Long.min;
import static java.lang.Math.*;

public class ProblemE4 {
    BufferedReader rd;

    ProblemE4() throws IOException {
        rd = new BufferedReader(new InputStreamReader(System.in));
        compute();
    }

    void compute() throws IOException {
        int q = intarr()[2];
        long[] a = longarr();
        long[] b = longarr();
        int[][] queries = new int[q][];
        for(int i=0;i<q;i++) {
            queries[i] = intarr();
            queries[i][0]--;
            queries[i][1]--;
        }

        long[] res = solve(a, b, queries);

        StringBuilder buf = new StringBuilder();
        for(long x: res) {
            if(buf.length() > 0) {
                buf.append('\n');
            }
            buf.append(x);
        }
        out(buf);
    }

    private long[] solve(long[] a, long[] b, int[][] queries) {
        int n = a.length;
        int m = b.length;
        int q = queries.length;
        NavigableSet<Long> bVal = new TreeSet<>();
        int limit = m > n?1:0;
        for(int r=0;r<=limit;r++) {
            long sum = 0;
            long p = -1;
            for (int i = r; i < n+r; i++) {
                sum += b[i] * p;
                p = -p;
            }
            long p2 = -1;
            boolean even = true;
            for (int i = n+r; i <= m; i++) {
                if(even) {
                    bVal.add(sum);
                }
                if (i < m) {
                    sum += b[i] * p;
                    sum -= b[i - n] * p2;
                    p = -p;
                    p2 = -p2;
                    even = !even;
                }
            }
        }

        EvenOdd evenOdd = new EvenOdd(a);

        long[] res = new long[q+1];
        res[0] = best(evenOdd, bVal);

        for(int i=0;i<q;i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int x = queries[i][2];

            evenOdd.add(l, r, x);
            res[i+1] = best(evenOdd, bVal);
        }
        return res;
    }

    private long best(EvenOdd evenOdd, NavigableSet<Long> bVal) {
        long s = evenOdd.sum();
        Function<Long, Long> f = x -> (x != null)?abs(x + s):MAX_VALUE;
        return min(f.apply(bVal.floor(-s)), f.apply(bVal.higher(-s)));
    }

    class EvenOdd {
        final int n;
        SegmentTreeWithLazyPropagation even;
        SegmentTreeWithLazyPropagation odd;

        EvenOdd(long[] a) {
            n = a.length;

            long[] evenArr = new long[n/2+1];
            long[] oddArr = new long[n/2+1];
            for(int i=0;i<n;i++) {
                if(i%2==0) {
                    evenArr[i / 2] = a[i];
                } else {
                    oddArr[i/2] = a[i];
                }
            }

            even = new SegmentTreeWithLazyPropagation(evenArr);
            odd = new SegmentTreeWithLazyPropagation(oddArr);
        }

        void add(int from, int to, long x) {
            int evenFrom = ceilingEven(from);
            int evenTo = floorEven(to);
            if(evenFrom <= evenTo) {
                even.add(evenFrom / 2,evenTo /2, x);
            }
            int oddFrom = ceilingOdd(from);
            int oddTo = floorOdd(to);
            if(oddFrom <= oddTo) {
                odd.add(oddFrom / 2, oddTo / 2, x);
            }
        }

        private int ceilingEven(int x) {
            return x + (x%2);
        }

        private int floorEven(int x) {
            return x - (x%2);
        }

        private int ceilingOdd(int x) {
            return x + 1 - (x%2);
        }

        private int floorOdd(int x) {
            return x - 1 + (x%2);
        }

        long sum() {
            long evenSum = even.sum(0, n/2);
            long oddSum = odd.sum(0, n/2);
            return evenSum - oddSum;
        }
    }

    class SegmentTreeWithLazyPropagation {
        private int n;
        private long[] a;
        private long[] sum;
        private long[] lazy;

        public SegmentTreeWithLazyPropagation(long[] a) {
            this.a = a;
            n = a.length;
            sum = new long[4*n];
            lazy = new long[4*n];
            build(1, 0, n-1);
        }

        private void build(int id, int l, int r) {
            if(l == r) {
                sum[id] = a[l];
                return;
            }
            int m = (l+r)/2;
            build(id*2, l, m);
            build(id*2+1, m+1, r);
            sum[id] = sum[id*2] + sum[id*2+1];
        }

        private void upd(int id, int l, int r, long x) {
            sum[id] += (r-l+1)*x;
            lazy[id] += x;
        }

        private void shift(int id, int l, int r) {
            int m = (l+r)/2;
            upd(id*2,l,m,lazy[id]);
            upd(id*2+1,m+1,r,lazy[id]);
            lazy[id] = 0;
        }

        public void add(int from, int to, long x) {
            add(from, to, x, 1, 0, n-1);
        }

        private void add(int from, int to, long x, int id, int l, int r) {
            if(from > r || to < l) {
                return;
            }
            if(from <= l && to >= r) {
                upd(id, l, r, x);
                return;
            }
            shift(id, l, r);
            int m = (l+r)/2;
            add(from, to, x, id*2, l, m);
            add(from, to, x, id*2 + 1, m+1, r);
            sum[id] = sum[id*2] + sum[id*2+1];
        }

        public long sum(int from, int to) {
            return sum(from, to, 1, 0, n-1);
        }

        private long sum(int from, int to, int id, int l, int r) {
            if(from > r || to < l) {
                return 0;
            }
            if(from <= l && to >= r) {
                return sum[id];
            }
            shift(id, l, r);
            int m = (l+r)/2;
            return sum(from, to, id*2, l, m) + sum(from, to, id*2+1, m+1, r);
        }
    }



    private long[] longarr() throws IOException {
        return longarr(rd.readLine());
    }

    private long[] longarr(String s) {
        String[] q = split(s);
        int n = q.length;
        long[] a = new long[n];
        for(int i=0;i<n;i++) {
            a[i] = Long.parseLong(q[i]);
        }
        return a;
    }

    private int[] intarr() throws IOException {
        return intarr(rd.readLine());
    }

    private int[] intarr(String s) {
        String[] q = split(s);
        int n = q.length;
        int[] a = new int[n];
        for(int i=0;i<n;i++) {
            a[i] = Integer.parseInt(q[i]);
        }
        return a;
    }

    private String[] split(String s) {
        if(s == null) {
            return new String[0];
        }
        int n = s.length();
        int start = -1;
        int end = 0;
        int sp = 0;
        boolean lastWhitespace = true;
        for(int i=0;i<n;i++) {
            char c = s.charAt(i);
            if(isWhitespace(c)) {
                lastWhitespace = true;
            } else {
                if(lastWhitespace) {
                    sp++;
                }
                if(start == -1) {
                    start = i;
                }
                end = i;
                lastWhitespace = false;
            }
        }
        if(start == -1) {
            return new String[0];
        }
        String[] res = new String[sp];
        int last = start;
        int x = 0;
        lastWhitespace = true;
        for(int i=start;i<=end;i++) {
            char c = s.charAt(i);
            boolean w = isWhitespace(c);
            if(w && !lastWhitespace) {
                res[x++] = s.substring(last,i);
            } else if(!w && lastWhitespace) {
                last = i;
            }
            lastWhitespace = w;
        }
        res[x] = s.substring(last,end+1);
        return res;
    }

    private boolean isWhitespace(char c) {
        return c==' ' || c=='\t';
    }

    private static void out(Object x) {
        System.out.println(x);
    }

    public static void main(String[] args) throws IOException {
        new ProblemE4();
    }
}
