当第 $i$ 个滑块在 $x$ 时，一个操作 $j,y$ 的影响有三种情况：

  • 当 $j<i$ 时，$x\gets\max(x,y+i-j)$；
  • 当 $j=i$ 时，$x\gets y$；
  • 当 $j>i$ 时，$x\gets\min(x,y+i-j)$。

由此，不同滑块之间实际上不会互相干扰。

本体的 trick 在于 01 拆分，我们难以计算 $i$ 最终落在 $x$ 的方案数，但我们可以计算 $i$ 最终落在 $\ge x$ 的方案数。
注意到每次变化都是取 $\max,\min$，所以滑块 $i$ 的最终位置只有可能在其初始位置 $a_i$，以及 $q$ 种操作 $j,y$ 产生的 $y+i-j$ 之中。

现在，不妨枚举滑块的最终位置是否 $\ge k$，那么什么样的操作序列可以满足这个呢？
可以发现，对 $<k$ 取 $\max$ 以及对 $\ge k$ 取 $\min$ 都是无效操作，不会改变 $\ge k$ 状态。
而对 $<k$ 取 $\min$ 会不合法（记这个数量为 $c_1$），对 $\ge k$ 取 $\max$ 都是合法（记这个数量为 $c_2$）。我们只需让对 $\ge k$ 取 $\max$ 是这两个操作中的后面那个即可，这个方案数是 $q!\frac{c_2}{c_1+c_2}$。

另外，还需要特判 $c_2=0$ 的情况，此时不会进行任何移动，贡献是 $q!a_i$。

维护 $c_1,c_2$ 可以在循环的同时枚举，具体实现见代码。

#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=5e3+7,P=1e9+7;
struct mint{
	int d;
	mint()=default;
	mint(int x):d(x){}
	friend std::istream&operator>>(std::istream&x,mint&y){return x>>y.d;}
	friend std::ostream&operator<<(std::ostream&x,mint y){return x<<y.d;}
	friend mint operator+(mint x,mint y){return (x.d+=y.d)<P?x.d:x.d-P;}
	mint&operator+=(mint z){return (d+=z.d)<P?d:d-=P,*this;}
	friend mint operator-(mint x,mint y){return (x.d-=y.d)<0?x.d+P:x.d;}
	mint&operator-=(mint z){return (d-=z.d)<0?d+=P:d,*this;}
	friend mint operator*(mint x,mint y){return int(1ll*x.d*y.d%P);}
	mint&operator*=(mint z){return d=int(1ll*d*z.d%P),*this;}
	static mint qpow(int x,int y=P-2){int z=1;for(;y;y>>=1,x=int(1ll*x*x%P))if(y&1)z=int(1ll*x*z%P);return z;}
	friend mint operator/(mint x,mint y){return x*=qpow(y.d);}
	mint&operator/=(mint z){return (*this)*=qpow(z.d);}
	friend mint operator^(mint x,mint y){return qpow(x.d,y.d);}
	mint&operator^=(mint z){return *this=qpow(d,z.d);}
	mint operator()(mint z)const{return qpow(d,z.d);}
	mint&operator[](mint z){return *this=qpow(d,z.d);}
	mint inv()const{return qpow(d);}
	mint pow(mint z)const{return qpow(d,z.d);}
	int operator+()const{return d;}
	mint operator-()const{return d?P-d:0;}
	int operator~()const{return ~d;}
};
mint operator""_m(lolu x){return mint(int(x%P));}
int n,m,q,a[N];
mint fac[N],inv[N];
pii b[N];
mint Bi(int x,int y){
	if(x<0||y<0||x<y)return 0;
	return fac[x]*inv[y]*inv[x-y];
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	fac[0]=inv[0]=1;
	for(int i=1;i<N;i++)fac[i]=fac[i-1]*i;
	inv[N-1]=fac[N-1].inv();
	for(int i=N-2;i;i--)inv[i]=inv[i+1]*(i+1);
	int T;cin>>T;while(T--){
		cin>>n>>m>>q;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=q;i++)cin>>b[i].fi>>b[i].se,b[i].se-=b[i].fi;
		sort(b+1,b+1+q,[](pii x,pii y){
			return x.se<y.se;
		});
		for(int i=1;i<=n;i++){
			mint ans=0;
			bool flag=0;
			for(int j=1;j<=q;j++){
				if(b[j].fi==i)flag=1;
				if(b[j].fi<=i&&b[j].se>=a[i]-i)flag=1;
				if(b[j].fi>=i&&b[j].se<=a[i]-i)flag=1;
			}
			if(!flag){
				cout<<fac[q]*a[i]<<' ';
				continue;
			}
			int c1=0,c2=0;
			for(int j=1;j<=q;j++)c2+=(b[j].fi<=i);
			for(int j=1;j<=q;j++){
				if(c1+c2==0)ans+=(b[j].se<=a[i]-i)*fac[q]*(b[j].se-b[j-1].se);
				else ans+=c2*inv[c1+c2]*fac[c1+c2-1]*fac[q]*(b[j].se-b[j-1].se);
				c1+=(b[j].fi>=i);
				c2-=(b[j].fi<=i);
			}
			cout<<(ans+i*fac[q])<<' ';
		}
		cout<<'\n';
	}
	return 0;
}