#include<iostream>
using namespace std;
const int N=2e5+5;
int d[N],l[N],r[N],minr[N],s[N];

int main(){
	int t;
	cin>>t;
	while(t--){
		int n,flag=0;
		cin>>n;
		for(int i=1;i<=n;i++) cin>>d[i];
		for(int i=1;i<=n;i++){
			s[i]=s[i-1];
			if(d[i]!=-1) s[i]+=d[i];
		}
		for(int i=1;i<=n;i++){
			cin>>l[i]>>r[i];
			l[i]-=s[i];
			r[i]-=s[i];
			if(r[i]<0){
				cout<<"-1\n";
				flag=1;
			}
		} 
		if(flag) continue;
		minr[n]=r[n];
		for(int i=n-1;i>=1;i--){
			minr[i]=min(minr[i+1],r[i]);
		}
		int cnt=0;
		for(int i=1;i<=n;i++){
			if(d[i]==-1){
				if(cnt+1>minr[i]) d[i]=0;
				else{
					d[i]=1;
					cnt++;
				}
			}
			if(cnt<l[i] || cnt>r[i]){
				flag=1;
				cout<<"-1\n";
				break;
			}
		}
		if(flag) continue;
		for(int i=1;i<=n;i++) cout<<d[i]<<" ";
		cout<<'\n';
	}
	return 0;
}

WA on test 2，一个数据我的程序输出了-1，但此数据有解

主要思路：将l[i],r[i]减去前缀和，这样只用考虑d[i]=-1时需要加多少高度。minr[i]为r[i]（减去前缀和后）的后缀最小值，cnt为所有修改后的d[i]的值的和（动态修改），任意时刻cnt均不能大于minr[i]，那么考虑贪心，对于每个d[i]=-1，cnt+1后如果仍不大于minr[i]，那就把这个d[i]修改为1，否则改为0