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.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.FileNotFoundException;
import java.io.File;
import java.util.TreeSet;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    E solver = new E();
    solver.solve(1, in, out);
    out.close();
  }

  static class E extends SimpleSavingChelperSolution {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
      wrapSolve(testNumber, in, out);
    }


    public void solve(int testNumber) {
      int n = in.nextInt();
      int m = in.nextInt();

      int q = in.nextInt();

      long[] a = in.nextLongArray(n);
      long[] b = in.nextLongArray(m);

      long sum1 = 0;
      for (int i = 0; i < n; i++) {
        sum1 += a[i] * (i % 2 == 0 ? 1 : -1);
      }

      long[] sumOdd = new long[m];
      long[] sumEven = new long[m];

      for (int i = 0; i < m; i++) {
        if (i % 2 == 0) {
          sumEven[i / 2] += b[i];
          if (i / 2 > 0) {
            sumEven[i / 2] += sumEven[i / 2 - 1];
          }
        } else {
          sumOdd[i / 2] += b[i];
          if (i / 2 > 0) {
            sumOdd[i / 2] += sumOdd[i / 2 - 1];
          }
        }
      }

      int k = m - n + 1;

      long[] initValues = new long[k];
      for (int i = 0; i < k; i++) {
        int res;
        long sum2 = 0;

        long d = i % 2 == 0 ? 1 : -1;

        int l = i - 1;
        int r = i + n - 1;

        int maxE;
        int minE;
        int maxO;
        int minO;

        maxE = r / 2;
        maxO = r / 2 - (1 - r % 2);

        minE = l < 0 ? -1 : l / 2;
        minO = l < 0 ? -1 : l / 2 - (1 - l % 2);

        if (maxE >= 0) {
          sum2 += sumEven[maxE] * d;
        }
        if (minE >= 0) {
          sum2 -= sumEven[minE] * d;
        }
        if (maxO >= 0) {
          sum2 -= sumOdd[maxO] * d;
        }
        if (minO >= 0) {
          sum2 += sumOdd[minO] * d;
        }

        initValues[i] = sum1 - sum2;
      }

//    out.println(Arrays.toString(initValues));

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

      for (int i = 0; i < k; i++) {
        set.add((long) initValues[i]);
      }

      long X = 0;

      out.println(closestDistance(X, set));

      for (int i = 0; i < q; i++) {
        int l = in.nextInt() - 1;
        int r = in.nextInt();
        long x = in.nextInt();

        if ((r - l) % 2 == 1) {
          if (l % 2 == 0) {
            X -= x;
          } else {
            X += x;
          }
        }

        out.println(closestDistance(X, set));
      }
    }

    long closestDistance(long X, TreeSet<Long> set) {
      long res = Long.MAX_VALUE;

      Long t = set.floor(X);
      if (t != null) {
        res = Math.min(res, X - t);
      }
      t = set.ceiling(X);
      if (t != null) {
        res = Math.min(res, t - X);
      }
      return res;
    }

  }

  static abstract class SavingChelperSolution {
    protected int testNumber;
    public InputReader in;
    public OutputWriter out;
    private OutputWriter toFile;
    private boolean local = new File("chelper.properties").exists();
    public OutputWriter debug;

    {
      if (local) {
        debug = new OutputWriter(System.out);
      } else {
        debug = new OutputWriter(new OutputStream() {

          public void write(int b) {
          }
        });
      }
    }

    public SavingChelperSolution() {
      try {
        toFile = new OutputWriter("last_test_output.txt");
      } catch (FileNotFoundException e) {
        throw new RuntimeException(e);
      }
    }

    public abstract void solve(int testNumber);

    public abstract String processOutputPreCheck(int testNumber, String output);

    public abstract String processOutputPostCheck(int testNumber, String output);

    public void wrapSolve(int testNumber, InputReader in, OutputWriter out) {
      this.testNumber = testNumber;

      ByteArrayOutputStream substituteOutContents = new ByteArrayOutputStream();
      OutputWriter substituteOut = new OutputWriter(substituteOutContents);

      this.in = in;
      this.out = substituteOut;

      solve(testNumber);
      substituteOut.flush();

      String result = substituteOutContents.toString();

      result = processOutputPreCheck(testNumber, result);
      out.print(result);
      out.flush();

      if (local) {
        debug.flush();

        result = processOutputPostCheck(testNumber, result);
        toFile.print(result);
        toFile.flush();
      }
    }

  }

  static class OutputWriter extends PrintWriter {

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

    public OutputWriter(String fileName) throws FileNotFoundException {
      super(fileName);
    }

    public OutputWriter(OutputStream outputStream) {
      super(outputStream);
    }

    public OutputWriter(Writer writer) {
      super(writer);
    }

  }

  static abstract class SimpleSavingChelperSolution extends SavingChelperSolution {

    public String processOutputPreCheck(int testNumber, String output) {
      return output;
    }


    public String processOutputPostCheck(int testNumber, String output) {
      return output;
    }

  }

  static class InputReader {
    private BufferedReader br;
    private StringTokenizer in;

    public InputReader(String fileName) {
      try {
        br = new BufferedReader(new FileReader(fileName));
      } catch (IOException e) {
        throw new RuntimeException(e);
      }
    }

    public InputReader(InputStream inputStream) {
      br = new BufferedReader(new InputStreamReader(inputStream));
    }

    private boolean hasMoreTokens() {
      while (in == null || !in.hasMoreTokens()) {
        String s = nextLine();
        if (s == null) {
          return false;
        }
        in = new StringTokenizer(s);
      }
      return true;
    }

    public String nextString() {
      return hasMoreTokens() ? in.nextToken() : null;
    }

    public String nextLine() {
      try {
        in = null;
        return br.readLine();
      } catch (Exception e) {
        e.printStackTrace();
        return null;
      }
    }

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

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

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

  }
}

