#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,n;
int a[100005],_l[100005],_r[100005],occ[100005],idx[100005];
vector <int> S[100005];
int ans[100005];

void solve(){
	scanf("%d",&n);
	fill(occ,occ + n + 1,0);
	rep(i,1,n) S[i].clear();
	rep(i,1,n){
		scanf("%d",&a[i]);
		S[a[i]].eb(i);
		idx[i] = occ[a[i] - 1];
		occ[a[i]] = i;
	}
	rep(i,1,n) scanf("%d%d",&_l[i],&_r[i]);
	rep(i,1,n){
		reverse(S[i].begin(),S[i].end());
		int prv = -1;
		for(int p:S[i]){
			ans[p] = _l[p];
			if(a[p] > 1) chkmax(ans[p],ans[idx[p]] + 1);
			if(prv != -1) chkmax(ans[p],ans[prv]);
			prv = p;
//			printf("%d->%d %d\n",p,ans[p],_r[p]);
			assert(ans[p] <= _r[p]);
		}
	}
	rep(i,1,n) printf("%d%c",ans[i]," \n"[i == n]);
}

int main(){
#ifdef cxy
	freopen("test.in","r",stdin);
#endif
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}