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.math.BigInteger;
import java.util.*;

public class Template implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void init() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine(), " :");
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    int[] readIntArray(int size) throws IOException {
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = readInt();
        }
        return res;
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    <T> List<T>[] createGraphList(int size) {
        List<T>[] list = new List[size];
        for (int i = 0; i < size; i++) {
            list[i] = new ArrayList<>();
        }
        return list;
    }

    public static void main(String[] args) {
        new Thread(null, new Template(), "", 1l * 200 * 1024 * 1024).start();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    long memoryTotal, memoryFree;

    void memory() {
        memoryFree = Runtime.getRuntime().freeMemory();
        System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10)
                + " KB");
    }

    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            memoryTotal = Runtime.getRuntime().freeMemory();
            init();
            solve();
            out.close();
            if (System.getProperty("ONLINE_JUDGE") == null) {
                time();
                memory();
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    class SegmentTree {
        long[] sum;
        long[] push;
        int n;

        SegmentTree(int n) {
            sum = new long[n * 4];
            push = new long[n * 4];
            this.n = n;
        }

        void push(int v, int tl, int tr) {
            int len = (tr - tl + 1);
            if (push[v] == 0) return;
            if (len % 2 != 0) {
                if (tl % 2 == 0) {
                    sum[v] += push[v];
                } else {
                    sum[v] -= push[v];
                }
            }
            if (v * 2 < push.length) {
                push[v * 2] += push[v];
            }
            if (v * 2 + 1 < push.length) {
                push[v * 2 + 1] += push[v];
            }
            push[v] = 0;
        }

        void add(int v, int tl, int tr, int l, int r, int add) {
            push(v, tl, tr);
            if (tl == l && tr == r) {
                push[v] += add;
                push(v, tl, tr);
                return;
            }
            int mid = (tl + tr) >> 1;
            if (r <= mid) {
                add(v * 2, tl, mid, l, r, add);
            } else if (l > mid) {
                add(v * 2 + 1, mid + 1, tr, l, r, add);
            } else {
                add(v * 2, tl, mid, l, mid, add);
                add(v * 2 + 1, mid + 1, tr, mid + 1, r, add);
            }
            push(v * 2, tl, mid);
            push(v * 2 + 1, mid + 1, tr);
            sum[v] = sum[v * 2] + sum[v * 2 + 1];
        }

        void add(int l, int r, int add) {
            add(1, 0, n - 1, l, r, add);
        }

        long get() {
            push(1, 0, n - 1);
            return sum[1];
        }
    }

    long prefsum(long[] pref, int l, int r) {
        long sum = pref[r];
        if (l > 0) {
            sum -= pref[l - 1];
        }
        return sum;
    }

    void solve() throws IOException {
        int n = readInt();
        int m = readInt();
        int q = readInt();
        SegmentTree segmentTree = new SegmentTree(n);
        for (int i = 0; i < n; i++) {
            segmentTree.add(i, i, readInt());
        }
        long[] bvalues = new long[m - n + 1];
        long[] b = new long[m];
        for (int i = 0; i < m; i++) {
            b[i] = readInt();
            if (i % 2 == 1) b[i] *= -1;
        }
        long[] bpref = new long[m];
        for (int i = 0; i < m; i++) {
            bpref[i] = b[i];
            if (i > 0) bpref[i] += bpref[i - 1];
        }
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < bvalues.length; i++) {
            bvalues[i] = prefsum(bpref, i, i + n - 1);
            if (i % 2 == 1) bvalues[i] *= -1;
            set.add(bvalues[i]);
        }
        out.println(best(segmentTree.get(), set));
        while (q --> 0) {
            segmentTree.add(readInt() - 1, readInt() - 1, readInt());
            long sum = segmentTree.get();
            out.println(best(sum, set));
        }
    }

    long best(long sum, TreeSet<Long> set) {
        if (set.contains(sum)) {
            return 0;
        } else {
            Long higher = set.higher(sum);
            Long lower = set.lower(sum);
            long best = Long.MAX_VALUE;
            if (higher != null) {
                best = Math.min(best, higher - sum);
            }
            if (lower != null) {
                best = Math.min(best, sum - lower);
            }
            return best;
        }
    }

}