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.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.Collection;
import java.util.Random;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskE solver = new TaskE();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskE {
    int n;
    int[] values;
    long sumA;
    LongArrayList sumB;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      int m = in.nextInt();
      int q = in.nextInt();
      values = new int[m];
      in.nextInt(n, values);
      sumA = calcFirstSum();
      in.nextInt(m, values);
      sumB = new LongArrayList(m - n + 1);
      sumB.add(calcFirstSum());
      for (int i = n, j = 0; i < m; ++i, ++j) {
        sumB.add(values[j] - sumB.peekLast() + (IntUtils.isOdd(n) ? values[i] : -values[i]));
      }
      sumB.sort();
//System.out.printf("sumB:%s\n", sumB.toDisplay());
      out.println(calc());
      for (int i = 0; i < q; ++i) {
        int l = in.nextInt() - 1;
        int r = in.nextInt() - 1;
        int x = in.nextInt();
        if (IntUtils.isOdd(r - l + 1)) {
          sumA += IntUtils.isEven(l) ? x : -x;
        }
        out.println(calc());
      }
    }

    long calc() {
      int idx = sumB.lowerBound(sumA);
      long res = Long.MAX_VALUE;
      if (idx < sumB.size) {
        res = Math.min(res, sumB.get(idx) - sumA);
      }
      if (idx > 0) {
        res = Math.min(res, sumA - sumB.get(idx - 1));
      }
//System.out.printf("sumA:%d res:%d\n", sumA, res);
      return res;
    }

    long calcFirstSum() {
      long res = 0;
      for (int i = 0; i < n; ++i) {
        if (IntUtils.isEven(i)) {
          res += values[i];
        } else {
          res -= values[i];
        }
      }
      return res;
    }

  }

  static class IntUtils {
    public static boolean isPow2(int n) {
      return n > 0 && (n & (n - 1)) == 0;
    }

    public static int nextPow2(int n) {
      if (n < 1) return 1;
      return isPow2(n) ? n : Integer.highestOneBit(n) << 1;
    }

    public static boolean isEven(int x) {
      return (x & 1) == 0;
    }

    public static boolean isOdd(int x) {
      return (x & 1) > 0;
    }

  }

  static class LongArrayList implements Displayable, LongCollection, Iterable<Long> {
    private static final long[] EMPTY = {};
    public long[] values;
    public int size;

    public LongArrayList() {
      values = EMPTY;
      clear();
    }

    public LongArrayList(int capacity) {
      values = new long[IntUtils.nextPow2(capacity)];
      clear();
    }

    public LongArrayList(Collection<Long> collection) {
      this(collection.size());
      addAll(collection);
    }


    public void clear() {
      size = 0;
    }


    public void add(long value) {
      ensureCapacity(size + 1);
      addInternal(value);
    }


    public void addAll(Collection<Long> values) {
      ensureCapacity(size + values.size());
      for (long value : values) {
        addInternal(value);
      }
    }

    public long peekLast() {
      return values[size - 1];
    }

    public long get(int idx) {
      if (idx >= size) throw new ArrayIndexOutOfBoundsException();
      return values[idx];
    }

    public void sort() {
      LongArrayUtils.sort(values, 0, size);
    }

    public int lowerBound(long value) {
      return LongArrayUtils.lowerBound(values, 0, size, value);
    }

    public void ensureCapacity(int capacity) {
      if (capacity <= values.length) return;
      long[] newValues = new long[IntUtils.nextPow2(capacity)];
      for (int i = 0; i < size; ++i) {
        newValues[i] = values[i];
      }
      values = newValues;
    }


    public Iterator<Long> iterator() {
      return new Iterator<Long>() {
        private int i = 0;


        public boolean hasNext() {
          return i < size;
        }


        public Long next() {
          return values[i++];
        }
      };
    }

    private void addInternal(long value) {
      values[size++] = value;
    }

  }

  static interface Displayable {
  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public void nextInt(int n, int[] res) {
      for (int i = 0; i < n; ++i) {
        res[i] = nextInt();
      }
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\t' || isEndOfLineChar(c);
    }

    public boolean isEndOfLineChar(int c) {
      return c == '\n' || c == '\r' || c < 0;
    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void println(Object... objects) {
      print(objects);
      writer.print('\n');
    }

    public void close() {
      writer.close();
    }

  }

  static interface LongCollection {
  }

  static class LongArrayUtils {
    private static final Random RANDOM = new Random(1000000007);

    public static void sort(long[] values, int fromIdx, int toIdx) {
      shuffle(values, fromIdx, toIdx);
      Arrays.sort(values, fromIdx, toIdx);
    }

    public static int lowerBound(long[] values, int fromIdx, int toIdx, long value) {
      int res = toIdx;
      for (int lower = fromIdx, upper = toIdx - 1; lower <= upper; ) {
        int medium = (lower + upper) >> 1;
        if (value <= values[medium]) {
          res = medium;
          upper = medium - 1;
        } else {
          lower = medium + 1;
        }
      }
      return res;
    }

    public static void swap(long[] values, int uIdx, int vIdx) {
      if (uIdx == vIdx) return;
      values[uIdx] ^= values[vIdx];
      values[vIdx] ^= values[uIdx];
      values[uIdx] ^= values[vIdx];
    }

    public static void shuffle(long[] values, int fromIdx, int toIdx) {
      for (int i = toIdx - fromIdx - 1; i > 0; --i) {
        swap(values, i + fromIdx, RANDOM.nextInt(i + 1) + fromIdx);
      }
    }

  }
}

