#include <bits/stdc++.h>
#define mp make_pair
#define fir first
#define sec second
#define mt make_tuple
#define ll long long
using namespace std;
const int N=3e5+10;
const ll inf=1e18;
int n,q,a[N],b[N],x,y,lg,block;
int nxt[N],lst[N],sz[N],st[N][18];
map <pair<int,int>,ll> ans;
ll tab[N<<1];ll calc(vector <pair<int,int>> s){
	int x_y=0;ll res=-inf,sum=0;vector <int> bin;
	tab[x_y+n]=0;bin.push_back(x_y+n);
	for(auto it:s){
		sum+=it.fir;x_y+=it.sec;
		res=max(res,sum-tab[x_y+n]);
		tab[x_y+n]=min(tab[x_y+n],sum);
		bin.push_back(x_y+n);
	}for(auto x:bin)tab[x]=inf;
	return res;
}
set <int> S[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;lg=log2(n)+1;
	block=sqrtl((1ll*n*n)/(1ll*q*log2(n)))+1;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=0;i<=(n<<1);i++)tab[i]=inf;
	for(int i=n;i>=1;i--){
		nxt[i]=lst[a[i]];
		st[i][0]=nxt[i];
		for(int j=1;j<=lg;j++)
			st[i][j]=st[st[i][j-1]][j-1];
		lst[a[i]]=i;sz[a[i]]++;
		S[a[i]].insert(i);
	}
	for(int i=1;i<=n;i++){
		if(sz[i]<block)continue;
		for(int j=1;j<=n;j++){
			if(i==j||sz[j]<block)continue;
			x=i,y=j;vector <pair<int,int>> in;
			int p1=lst[x],p2=lst[y];
			while(p1&&p2)
				if(p1<p2){in.push_back(mp(b[p1],1));p1=nxt[p1];}
				else{in.push_back(mp(b[p2],-1));p2=nxt[p2];}
			while(p1)in.push_back(mp(b[p1],1)),p1=nxt[p1];
			while(p2)in.push_back(mp(b[p2],-1)),p2=nxt[p2];
			ans[mp(x,y)]=calc(in);
		}
	}
	while(q--){
		cin>>x>>y;
		if(ans.count(mp(x,y))){cout<<ans[mp(x,y)]<<"\n";continue;}
		if(ans.count(mp(y,x))){cout<<ans[mp(y,x)]<<"\n";continue;}
		if(sz[x]>sz[y])swap(x,y);
		int cnt=0,pos=lst[y];
		vector <pair<int,pair<int,int>>> seq;
		vector <pair<int,int>> in;
		vector <int> undo;
		//cout<<"BEGIN"<<endl;
		for(int i=lst[x];i;i=nxt[i]){
			//cout<<i<<endl;
			++cnt;
			seq.push_back(mp(i,mp(b[i],1)));
			//cout<<"YES"<<endl;
			if((pos&&pos<nxt[i])||!nxt[i]){
				auto it=S[y].lower_bound(i);
				for(int j=1;j<=cnt+1;j++){
					if(it==S[y].end())break;
					seq.push_back(mp(*it,mp(b[*it],-1)));
					undo.push_back(*it);S[y].erase(it);
					it=S[y].lower_bound(i);
				}
				it=S[y].lower_bound(i);
				if(it==S[y].begin())continue;it--;
				for(int j=1;j<=cnt+1;j++){
					seq.push_back(mp(*it,mp(b[*it],-1)));
					undo.push_back(*it);S[y].erase(it);
					it=S[y].lower_bound(i);
					if(it==S[y].begin())break;it--;
				}
				cnt=0;pos=nxt[pos];
			}
		}
		//cout<<"END"<<endl;
		for(auto it:undo)S[y].insert(it);
		sort(seq.begin(),seq.end());
		for(auto it:seq)in.push_back(it.sec);
		//for(auto it:in)
		//	cout<<it.fir<<" "<<it.sec<<"\n";
		cout<<calc(in)<<"\n";
	}
	return 0;
}