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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.Random;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EMahmoudAndEhabAndTheFunction solver = new EMahmoudAndEhabAndTheFunction();
        solver.solve(1, in, out);
        out.close();
    }

    static class EMahmoudAndEhabAndTheFunction {
        public int findOdd(int l, int r) {
            if (l % 2 != 1) l++;
            if (r % 2 != 1) r--;
            if (l > r) return 0;
            return (r - l) / 2 + 1;
        }

        public int findEven(int l, int r) {
            if (l % 2 != 0) l++;
            if (r % 2 != 0) r--;
            if (l > r) return 0;
            return (r - l) / 2 + 1;
        }

        public long solveIt(long[] values, long sum) {
            long ans = Long.MAX_VALUE;
            int low = 0;
            int high = values.length - 1;
            while (low <= high) {
                int mid1 = low + (high - low) / 3;
                int mid2 = high - (high - low) / 3;
                if (Math.abs(sum + values[mid1]) >= Math.abs(sum + values[mid2])) {
                    ans = Math.min(ans, Math.abs(sum + values[mid1]));
                    low = mid1 + 1;
                } else {
                    ans = Math.min(ans, Math.abs(sum + values[mid2]));
                    high = mid2 - 1;
                }
            }
            //    for (long v : values) ans = Math.min(ans, Math.abs(v + sum));
            return ans;
        }

        long[] removeIt(long[] ar) {
            int size = 0;
            for (int i = 0; i < ar.length; ) {
                long temp = ar[i];
                while (i < ar.length && ar[i] == temp) i++;
                size++;
            }
            long[] temp = new long[size];
            size = 0;
            for (int i = 0; i < ar.length; ) {
                temp[size] = ar[i];
                while (i < ar.length && ar[i] == temp[size]) i++;
                size++;
            }
            return temp;
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int m = in.scanInt();
            int q = in.scanInt();
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) a[i] = in.scanInt();
            int[] b = new int[m + 1];
            for (int i = 1; i <= m; i++) b[i] = in.scanInt();
            long[] prefix_Odd = new long[m + 1];
            long[] prefix_Even = new long[m + 1];
            for (int i = 1; i <= m; i++) {
                if (i % 2 == 0) prefix_Even[i] += b[i];
                else prefix_Odd[i] += b[i];
                prefix_Even[i] += prefix_Even[i - 1];
                prefix_Odd[i] += prefix_Odd[i - 1];
            }
            long[] values = new long[m - n + 1];
            for (int i = n; i <= m; i++) {
                long temp;
                if ((i - n + 1) % 2 == 0) {
                    temp = -(prefix_Even[i] - prefix_Even[i - n]) + (prefix_Odd[i] - prefix_Odd[i - n]);
                } else {
                    temp = (prefix_Even[i] - prefix_Even[i - n]) - (prefix_Odd[i] - prefix_Odd[i - n]);
                }
                values[i - n] = temp;
            }
            CodeHash.shuffle(values);
            Arrays.sort(values);
            values = removeIt(values);
            long sum = 0;
            for (int i = 1; i <= n; i++)
                if (i % 2 == 1) sum += a[i];
                else sum -= a[i];
            out.println(solveIt(values, sum));

            while (q-- > 0) {
                int l = in.scanInt();
                int r = in.scanInt();
                long x = in.scanInt();
                sum += (findOdd(l, r) * x);
                sum -= (findEven(l, r) * x);
                out.println(solveIt(values, sum));

            }
        }

    }

    static class CodeHash {
        public static void shuffle(long[] ar) {
            Random rd = new Random(new Random().nextInt());
            for (int i = 0; i < ar.length; i++) {
                int index = rd.nextInt(ar.length);
                long tt = ar[i];
                ar[i] = ar[index];
                ar[index] = tt;
            }
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

