/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int B=4000;
int q,a[2000005],b[2000005],n,m,ans[2000005],lst;
pii c[2000005];
void solve()
{
	cin>>n>>q;
	m=n;
	for(int i=1;i<=n;i++) cin>>a[i],c[i]=mp(a[i],i);
	sort(c+1,c+1+n);
	
	for(int i=1;i<=n;i++) cin>>b[i],ans[0]=max(ans[0],a[i]+b[i]);
	priority_queue <int,vector<int>, greater<int> > qa,qb;
	for(int i=1;i<=n;i++) 
	{
		qa.push(a[i]),qb.push(a[i]);
		if(qa.size()>B) qa.pop();
		if(qb.size()>B) qb.pop();
	}
	for(int i=1;i<=n;i++)
	{
		int lim=qa.top()+qb.top()-b[i];
		int p=lower_bound(c+1,c+1+n,mp(lim,0))-c;
		for(int j=p;j<=n;j++)
		{
			int v=c[j].se;
			if(v<i) ans[i-v]=max(ans[i-v],a[v]+b[i]);
		}
	}
	lst=ans[0];
	cout<<lst<<"\n";
	for(int i=1;i<=q;i++)
	{
		int v;
		cin>>v;
//		v^=lst;
		b[++m]=v;
		qb.push(v);
		if(qb.size()>B) qb.pop();
		int lim=qa.top()+qb.top()-b[m];
		int p=lower_bound(c+1,c+1+n,mp(lim,0))-c;
		for(int j=p;j<=n;j++)
		{
			v=c[j].se;
			if(v<m) ans[m-v]=max(ans[m-v],a[v]+b[m]);
		}
		lst=ans[i];
		cout<<lst<<"\n";
	}
}
signed main()
{
//	freopen("K.in","r",stdin);
//	freopen("K.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}