题解

每个孩子带的钱是 $1,2,\dots,m$，所有孩子能获得的总愉悦度就是“对每个体积（花费）$w$，求出标准的有界背包的最优值”，最后把 $f_w$ 求和 / 取异或即可。因此问题被转化为“多次删除一个区间内的物品，询问剩余物品做 $m$ 以内的多重背包 DP 的结果”。

我们把物品分块，块大小设成 $B\approx 30$。预处理时：

1. 用单调队列优化的多重背包转移维护一个结构体 BP，里面是一维 DP 数组 dp[0..m]。insert(cost,value,limit) 表示把某个物品加入背包，复杂度为 $\mathcal{O}(m)$。
2. 对于所有块对 $(i,j)$（$i<j$），预先计算 block[i][j]：它表示在整体物品序列中删去区间 $[i+1, j-1]$ 中的整块之后，剩余物品跑完背包 DP 的结果。具体做法是从左到右维护前缀 DP，再倒着往前加入后缀块，类似“分块 + 前缀 + 后缀”预处理。

每次询问删除区间 $[l,r]$ 时，先找到它所在块的编号。整块部分直接由 block[belong(l)-1][belong(r)+1] 给出；边缘的零散物品最多两个块，直接把它们逐件重新 insert 即可。得到完整的 dp[1..m] 之后，再扫一遍前缀最大值，求和与异或输出答案。预处理复杂度 $\mathcal{O}(n m)$，每个查询的增量部分只有 $\mathcal{O}(m + B \cdot m)$ 的时间。

#include<bits/stdc++.h>

using namespace std;

#define int long long

constexpr int maxm=1000;
constexpr int maxn=1000;

int n,m;

struct Queue{
	pair<int,int> info[maxm+1];
	int beg,ed;
	
	void push(int p,int q){
		while(ed>=beg&&info[ed].first<p){
			ed--;
		}
		info[++ed]=make_pair(p,q);
	}
	
	int ask(int lim){
		while(info[beg].second<lim){
			beg++;
		}
		return info[beg].first;
	}
}q[maxm+1];

int Mod[maxm+1][maxm+1];
int Div[maxm+1][maxm+1];

struct BP{
	int dp[maxm+1];
	
	void clear(){
		for(int i=1;i<=m;i++){
			dp[i]=-1e18;
		}
		dp[0]=0;
	}
	
	void insert(int sze,int v,int lim){
		//cout<<"Insert sze:"<<sze<<" v:"<<v<<" lim:"<<lim<<"\n";
		for(int i=0;i<sze;i++){
			q[i].beg=1;
			q[i].ed=0;
			q[i].push(dp[i],i);
		}
		for(int i=sze;i<=m;i++){
			q[Mod[i][sze]].push(dp[i]-Div[i][sze]*v,i);
			dp[i]=q[Mod[i][sze]].ask(i-sze*lim)+Div[i][sze]*v;
		}
	}
};

constexpr int B=30;
constexpr int bnum=(maxn-1)/B+1;

BP block[bnum+1][bnum+1];
BP base,tmp;

int c[maxn+1];
int v[maxn+1];
int t[maxn+1];
int belong[maxn+1];
int bl[bnum+1];
int br[bnum+1];

void solve(){
	int Q;
	cin>>n>>m>>Q;
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	for(int i=1;i<=n;i++){
		cin>>t[i];
		belong[i]=(i-1)/B+1;
	}
	for(int i=1;i<=belong[n];i++){
		bl[i]=(i-1)*B+1;
		br[i]=min(n,i*B);
	}
	for(int i=0;i<belong[n];i++){
		for(int j=i+2;j<=belong[n]+1;j++){
			block[i][j].clear();
		}
	}
	base.clear();
	tmp.clear();
	for(int i=0;i<belong[n];i++){
		tmp=base;
		for(int j=belong[n]+1;j>=i+2;j--){
			block[i][j]=tmp;
			for(int k=bl[j-1];k<=br[j-1];k++){
				tmp.insert(c[k],v[k],t[k]);
			}
		}
		for(int j=bl[i+1];j<=br[i+1];j++){
			base.insert(c[j],v[j],t[j]);
		}
	}
	int lastans=0;
	while(Q--){
		int l,r;
		cin>>l>>r;
		l=(l+lastans-1)%n+1;
		r=(r+lastans-1)%n+1;
		if(l>r){
			swap(l,r);
		}
		base=block[belong[l]-1][belong[r]+1];
//		cout<<"Pre:"<<belong[l]-1<<" ED:"<<belong[r]+1<<"\n";
//		for(int i=1;i<=m;i++){
//			cout<<base.dp[i]<<" ";
//		}
//		cout<<"\n";
		for(int i=r+1;i<=br[belong[r]];i++){
			base.insert(c[i],v[i],t[i]);
		}
		for(int i=bl[belong[l]];i<l;i++){
			base.insert(c[i],v[i],t[i]);
		}
		constexpr int mod=1e8+7;
		int sum=0,Xor=0;
		for(int i=1;i<=m;i++){
			base.dp[i]=max(base.dp[i],base.dp[i-1]);
			sum=(sum+base.dp[i])%mod;
			Xor^=base.dp[i];
//			cout<<base.dp[i]<<" ";
		}
//		cout<<"\n";
		lastans=sum;
		cout<<sum<<" "<<Xor<<"\n";
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	for(int i=0;i<=maxm;i++){
		for(int j=1;j<=maxm;j++){
			Mod[i][j]=i%j;
			Div[i][j]=i/j;
		}
	}
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}