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.math.BigInteger;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main2 {

    static long mod = 1000000007L;
    static FastScanner scanner;
    static int[] poss = new int[]{-1, -1};

    public static void main(String[] args) {
        scanner = new FastScanner();
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int q = scanner.nextInt();
        long[] a = scanner.nextLongArray(n);
        long[] b = scanner.nextLongArray(m);

        long sumA = 0;
        for (int i = 0; i < a.length; i++) {
            sumA += a[i] * (i % 2 == 0 ? 1 : -1);
        }
        long[] negSumB = new long[m - n + 1];

        for (int i = 0; i < n; i++) {
            negSumB[0] += b[i] * (i % 2 == 1 ? 1 : -1);
        }
        for (int i = 1; i < m - n + 1; i++) {
            negSumB[i] = -(negSumB[i - 1] + b[i-1]) + b[n + i - 1] * ((n - 1) % 2 == 1 ? 1 : -1);
        }

        TreeSet<Long> results = new TreeSet<>();
        for (int j = 0; j < m - n + 1; j++) {
            results.add(sumA + negSumB[j]);
        }

        long result = 0;
        StringBuilder re = new StringBuilder();
        addQuery(re, results, result);
        for (int i = 0; i < q; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            long x = scanner.nextInt();
            if ((r - l + 1) % 2 == 1) {
                boolean isPositive = (l - 1) % 2 == 0;
                result = isPositive ? result - x : result + x;
            }
            addQuery(re, results, result);
        }
        System.out.println(re.toString());
    }

    static void addQuery(StringBuilder builder, TreeSet<Long> set, long res) {
        Long left = set.floor(res);
        Long right = set.ceiling(res);
        if (left == null) {
            builder.append(Math.abs(right - res)).append("\n");
            return;
        }
        if (right == null) {
            builder.append(Math.abs(left - res)).append("\n");
            return;
        }
        builder.append(Math.min(Math.abs(left - res), Math.abs(right - res))).append("\n");

    }

    static void walk(int previous, char[] prevReq, int start, int end) {
        char[] newReqA = Arrays.copyOf(prevReq, prevReq.length);
        char[] newReqB = Arrays.copyOf(prevReq, prevReq.length);
        int mid = (start + end) / 2;
        for (int i = start; i < mid; i++) {
            newReqA[i] = inv(newReqA[i]);
        }
        for (int i = mid; i < end; i++) {
            newReqB[i] = inv(newReqB[i]);
        }
        int all = mid - start;
        int a = request(scanner, newReqA);
        if (Math.abs(previous - a) == all) {
            if (a > previous) {
                addResult(inv(newReqA[start]), start);
            } else {
                addResult(newReqA[start], start);
            }

            all = end - mid;
            int b = request(scanner, newReqB);
            if (Math.abs(previous - b) == all) {
                if (b > previous) {
                    addResult(inv(newReqB[mid]), mid);
                } else {
                    addResult(newReqB[mid], mid);
                }
            }
            walk(b, newReqB, mid, end);
        } else {
            walk(a, newReqA, start, mid);
        }

    }

    static void addResult(char c, int pos) {
        if (c == '0') poss[0] = pos;
        if (c == '1') poss[1] = pos;
        if (poss[0] != -1 && poss[1] != -1) {
            System.out.println("! " + (poss[0] + 1) + " " + (poss[1] + 1));
            System.out.flush();
            System.exit(0);
        }
    }

    static char inv(char c) {
        return c == '0' ? '1' : '0';
    }

    public static int request(FastScanner scanner, char[] request) {
        System.out.println("? " + String.valueOf(request));
        System.out.flush();
        return scanner.nextInt();
    }

    static int gcdRecursive(int a, int b)
    {
        //if (a == 0) return b;
        if (b > 0)
            return gcdRecursive(b, a % b);
        else
            return a;
    }


    static class GroupContainer {
        int number;

        public GroupContainer(int number) {
            this.number = number;
        }
    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (Exception e) {
                e.printStackTrace();
                throw new RuntimeException();
            }
        }

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

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

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

        int[] nextIntArray(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) res[i] = nextInt();
            return res;
        }

        long[] nextLongArray(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) res[i] = nextLong();
            return res;
        }

        String[] nextStringArray(int n) {
            String[] res = new String[n];
            for (int i = 0; i < n; i++) res[i] = nextToken();
            return res;
        }
    }

    static class PrefixSums {
        long[] sums;

        public PrefixSums(long[] sums) {
            this.sums = sums;
        }

        public long sum(int fromInclusive, int toExclusive) {
            if (fromInclusive > toExclusive) throw new IllegalArgumentException("Wrong sum");
            return sums[toExclusive] - sums[fromInclusive];
        }

        public static PrefixSums of(int[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }

        public static PrefixSums of(long[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }
    }

    static class ADUtils {
        static void sort(int[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                int a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }

        static void sort(long[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                long a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }
    }

    static class MathUtils {
        static long modpow(long b, long e, long m) {
            long result = 1;

            while (e > 0) {
                if ((e & 1) == 1) {
            /* multiply in this bit's contribution while using modulus to keep
             * result small */
                    result = (result * b) % m;
                }
                b = (b * b) % m;
                e >>= 1;
            }

            return result;
        }
    }
}