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 MahmoudEhabFunction {

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

        public float nextFloat() {
            return Float.parseFloat(next());
        }

        public double nextDouble() {
            return Float.parseFloat(next());
        }

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

    static class CPMath {
        static int add(int a, int b) {
            a += b;

            if (a >= mod) a -= mod;

            return a;
        }

        static int sub(int a, int b) {
            a -= b;
            if (a < 0) a += mod;
            return a;
        }

        static int multiply(int a, long b) {
            b = a * b;
            return (int) (b % mod);
        }

        static int divide(int a, int b) {
            return multiply(a, inverse(b));
        }

        static int inverse(int a) {
            return power(a, mod - 2);
        }

        static int power(int a, int b) {
            int r = 1;

            while (b > 0) {
                if (b % 2 == 1) {
                    r = multiply(r, a);
                }

                a = multiply(a, a);
                b /= 2;
            }

            return r;
        }
    }

    static InputReader sc;
    static PrintWriter pw;

    static int mod = (int) (1e9 + 7);

    public static void main(String[] args) throws Exception {
        sc = new InputReader(System.in);
        pw = new PrintWriter(System.out);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();

        long sum = 0;

        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            if (i % 2 == 1) val = -val;
            sum += val;
        }

        int[] b_elements = new int[m];

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

        TreeSet<Long> treeSet = new TreeSet<>();

        long b_sum = 0;

        for (int j = 0; j < n; j++) {
            int val = b_elements[j];
            if (j % 2 == 0) val = -val;
            b_sum += val;
        }

        treeSet.add(b_sum);

        for (int i = 0; i < m - n; i++) {

            b_sum = -b_sum;
            b_sum -= b_elements[i];

            int new_val = b_elements[n + i];

            if ((n - 1) % 2 == 0) {
                new_val = -new_val;
            }

            b_sum += new_val;
            treeSet.add(b_sum);
        }

        long min = Long.MAX_VALUE;

        if (treeSet.ceiling(-sum) != null) {
            long closest_val_above = treeSet.ceiling(-sum);
            min = Math.min(min, Math.abs(closest_val_above + sum));
        }

        if (treeSet.floor(-sum) != null) {
            long closest_val_below = treeSet.floor(-sum);
            min = Math.min(min, Math.abs(closest_val_below + sum));
        }

        pw.println(min);

        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int x = sc.nextInt();

            if (l % 2 == 1 && r % 2 == 1) {
                sum += x;
            }

            else if (l % 2 == 0 && r % 2 == 0) {
                sum -= x;
            }

            min = Long.MAX_VALUE;

            if (treeSet.ceiling(-sum) != null) {
                long closest_val_above = treeSet.ceiling(-sum);
                min = Math.min(min, Math.abs(closest_val_above + sum));
            }

            if (treeSet.floor(-sum) != null) {
                long closest_val_below = treeSet.floor(-sum);
                min = Math.min(min, Math.abs(closest_val_below + sum));
            }

            pw.println(min);
        }

        pw.close();
    }
}