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

public class Solution {


    static MyScanner sc;
    private static PrintWriter out;
    static long M = 1000000007;


    public static void main(String[] s) throws Exception {
        StringBuilder stringBuilder = new StringBuilder();

//
//        stringBuilder.append("100 100 50 ");
//        Random r = new Random();
//        for (int t = 0; t < 200; t++) {
//            stringBuilder.append(r.nextInt(999999) + " ");
//        }
//        for (int i = 0; i < 50; i++) {
//            int l = r.nextInt(50) + 1;
//            int rr = r.nextInt(30) + 2 + l;
//            stringBuilder.append(l + " " + rr + " " + r.nextInt(999999) + " ");
//        }

//        stringBuilder.append("5 10 3\n" +
//                "-45345344 -23552345 999549999 9999999 9999999 \n" +
//                "99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999999 99999999 \n" +
//                "1 3 9999999\n" +
//                "2 4 99999399\n" +
//                "3 5 -9999999");


        if (stringBuilder.length() == 0) {
            sc = new MyScanner(System.in);
        } else {
            sc = new MyScanner(new BufferedReader(new StringReader(stringBuilder.toString())));
        }

        out = new PrintWriter(new OutputStreamWriter(System.out));

        initData();
        solve();
        out.flush();
    //    solveN(stringBuilder.toString());
        out.flush();
    }

    private static void solveN(String s) {
        sc = new MyScanner(new BufferedReader(new StringReader(s)));
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        long[] a = sc.nl(n);
        long[] b = sc.nl(m);
        out.println(naive(a, b));
        for (int i = 0; i < q; i++) {
            int f = sc.nextInt();
            int t = sc.nextInt();
            int r = sc.nextInt();
            for (int ll = f - 1; ll < t; ll++) {
                a[ll] += r;
            }
            out.println(naive(a, b));
        }


    }

    private static long naive(long[] a, long[] b) {
        long min = Long.MAX_VALUE;
        for (int qq = 0; qq <= b.length - a.length; qq++) {
            long lr = 0;
            for (int i = 0; i < a.length; i++) {
                lr += (i % 2 == 0) ? (a[i] - b[qq + i]) : -(a[i] - b[qq + i]);
            }
            min = Math.min(min, Math.abs(lr));
        }
        return min;
    }

    private static void initData() {
    }

    private static void solve() throws IOException {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        int[] a = sc.na(n);
        int[] b = sc.na(m);
        long x = 0;
        for (int i = 0; i < n; i += 2) {
            x += a[i];
        }
        for (int i = 1; i < n; i += 2) {
            x -= a[i];
        }

        long ppp = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                ppp -= b[i];
            } else {
                ppp += b[i];
            }
        }
        TreeSet<Long> res = new TreeSet<>();
        res.add(ppp);
        for (int i = n; i < m; i++) {
            ppp += b[i - n];
            ppp = -ppp;
            if (n % 2 == 0) {
                ppp += b[i];
            } else {
                ppp -= b[i];
            }
            res.add(ppp);
        }
        out.println(xx(res, x));
        for (int l = 0; l < q; l++) {
            int f = sc.nextInt();
            int t = sc.nextInt();
            int v = sc.nextInt();
            if ((t - f) % 2 == 0) {
                if (f % 2 == 1) {
                    x += v;
                } else {
                    x -= v;
                }
            }

            out.println(xx(res, x));
        }


    }

    private static long xx(TreeSet<Long> res, long x) {
        Long x1 = res.ceiling(-x);
        Long x2 = res.floor(-x);

        long min = Long.MAX_VALUE;

        if (x1 != null) {
            min = Math.abs(x1 + x);
        }

        return x2 != null ? Math.min(min, Math.abs(x + x2)) : min;
    }


    private static void solveT() throws IOException {
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }

    private static long gcd(long l, long l1) {
        if (l > l1) return gcd(l1, l);
        if (l == 0) return l1;
        return gcd(l1 % l, l);
    }

    private static long pow(long a, long b, long m) {
        if (b == 0) return 1;
        if (b == 1) return a;
        long pp = pow(a, b / 2, m);
        pp *= pp;
        pp %= m;
        return (pp * (b % 2 == 0 ? 1 : a)) % m;
    }


    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        MyScanner(BufferedReader br) {
            this.br = br;
        }

        public MyScanner(InputStream in) {
            this(new BufferedReader(new InputStreamReader(in)));
        }

        void findToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }

        String next() {
            findToken();
            return st.nextToken();
        }

        Integer[] nab(int n) {
            Integer[] k = new Integer[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        int[] na(int n) {
            int[] k = new int[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        long[] nl(int n) {
            long[] k = new long[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.nextLong();
            }
            return k;
        }

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

        int fi() {
            String t = next();
            int cur = 0;
            boolean n = t.charAt(0) == '-';
            for (int a = n ? 1 : 0; a < t.length(); a++) {
                cur = cur * 10 + t.charAt(a) - '0';
            }
            return n ? -cur : cur;
        }

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

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

}