862E.cpp

#include <bits/stdc++.h>
using namespace std;
#define TR(i,v)       for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
#define DEBUG(x)      cout<<#x<<" = "<<x<<endl
#define SIZE(p)       (int)(p).size()
#define MP(a,b)       make_pair((a),(b))
#define ALL(p)        (p).begin(),(p).end()
#define rep(i,n)      for(int i=0;i<(int)(n);++i)
#define REP(i,a,n)    for(int i=(a);i<(int)(n); ++i)
#define FOR(i,a,b)    for(int i=(int)(a);i<=(int)(b);++i)
#define FORD(i,b,a)   for(int i=(int)(b);i>=(int)(a);--i)
#define CLR(x,y)      memset((x),(y),sizeof((x)))
typedef long long LL;
typedef pair<int,int> pii;
const int maxn=100055;
int A[maxn],B[maxn];
struct SegTree{
  struct Node{
    int l,r;LL s[2],f;
    void upd(LL y){
      f+=y;
      int o=l&1,k1=(r-l)/2+1,k2=r-l+1-k1;
      s[o]+=y*k1,s[o^1]+=y*k2;
    }
  }v[maxn<<2];
  void build(int l,int r,int x){
    v[x].l=l,v[x].r=r,v[x].s[0]=v[x].s[1]=v[x].f=0;
    if(l==r){
      v[x].s[l&1]=A[l];
      return;
    }
    int m=l+r>>1;
    build(l,m,x<<1),build(m+1,r,x<<1|1);
    up(x);
  }
  void pd(int x){
    if(v[x].f){
      v[x<<1].upd(v[x].f),v[x<<1|1].upd(v[x].f);
      v[x].f=0;
    }
  }
  void up(int x){
    rep(i,2){
      v[x].s[i]=v[x<<1].s[i]+v[x<<1|1].s[i];
    }
  }
  void mf(int l,int r,int y,int x){
    // printf("at [%d %d] y=%d\n",v[x].l,v[x].r,y);fflush(stdout);
    if(v[x].l>=l && v[x].r<=r){      
      v[x].upd(y);      
      // printf("sum %d %d\n",v[x].s[0],v[x].s[1]);
      return;
    }
    int m=v[x].l+v[x].r>>1;
    pd(x);
    if(r<=m)mf(l,r,y,x<<1);
    else if(l>m)mf(l,r,y,x<<1|1);
    else mf(l,r,y,x<<1),mf(l,r,y,x<<1|1);
    up(x);
    // printf("sum %d %d\n",v[x].s[0],v[x].s[1]);
  }
}ds;
inline LL myabs(LL x){
  return x>=0?x:-x;
}
LL getans(LL a,vector<LL> &b){
  auto f=lower_bound(ALL(b),a);
  if(f==b.end())
    return abs(*--f-a);
  LL r=*f-a;
  if(f!=b.begin())r=min(r,abs(*--f-a));
  return r;
}
int main(){
  int n,m,Q;scanf("%d%d%d",&n,&m,&Q);
  rep(i,n)scanf("%d",A+i);
  rep(i,m)scanf("%d",B+i);
  vector<LL> bs;
  LL s=0;
  rep(i,n)s+=(i&1?-1:1)*B[i];
  for(int i=0;i+n-1<m;++i){
    bs.push_back(s);
    // DEBUG(s);
    s-=B[i];
    if(i+n<m)s=-s+(((i+n)&1)==(i&1)?-1:1)*B[i+n];
  }
  ds.build(0,n-1,1);
  sort(ALL(bs));
  LL as=ds.v[1].s[0]-ds.v[1].s[1];
  as=0;
  rep(i,n)as+=(i&1?-1:1)*A[i];
  // for(LL x:bs)printf("%lld ",x);puts("");
  // DEBUG(as);
    // printf("%lld %lld %lld\n",ds.v[1].s[0],ds.v[1].s[1],as);
  LL res=getans(as,bs);
  printf("%lld\n",res);
  while(Q--){
    int l,r,x;scanf("%d%d%d",&l,&r,&x);--l,--r;
    ds.mf(l,r,x,1);
    LL as=ds.v[1].s[0]-ds.v[1].s[1];
    // printf("%lld %lld %lld\n",ds.v[1].s[0],ds.v[1].s[1],as);
    LL res=getans(as,bs);
    // DEBUG(res);
    printf("%lld\n",res);
  }
  return 0;
}