hdu4095

/*
第一步，构建BST，用第一个数作为bst的根，每加进 一个节点u，查询bst中比u小且和u的差的绝对值最小的数rv，如果 rv存在且rv还没有右孩子，
则把u作为rv的左孩子，否则，查询bst中比u大且和u的差的绝对值最小的 数字lv,把u作为lv的左孩子。这一步可以用树状数组搞定。时间复杂度是
O(n*log(n))。
第二步，计算以每个节点u为根的子树往左边延伸的长度llen[u]和 往右边延伸的长度rlen[u]，llen[u]和rlen[u]依赖于左右孩子，所以要从
叶子节点开始找起。
第三步，计算每个节点u的符号'o'的坐标，这个根据数组llen和rlen可以算出来，儿子节点的坐标依赖于父节点的坐标，所以要从根部开始找。
然后对于每一个查询的矩形区域，扫描每一个节点就可以算出每个节点对这个 区域贡献了哪些字符。
总的时间复杂度是O(n*log(n))。
初看此题，挺麻烦，找到好的方法解决之后，就是个水题…………
^-^
*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100005;
const int L=205;
typedef pair<int, int> pii;
int in[N], ks[N], par[N], ls[N], rs[N];
int front[N], back[N], llen[N], rlen[N], que[N];
pii pos[N];
int n, root;
bool mark[N];
char out[L][L];
int sr, sc, r, c;
//输入一个整数
template<typename T>
void getSNum(T& ans){
	char ch;
	int s;
	while(true){
		ch = getchar();
		if((ch >= '0' && ch <= '9') || ch == '-') break;
	}
	if(ch == '-'){
		s = -1;
		ans = 0;
	}else{
		s = 1;
		ans = ch -'0';
	}
	while(true){
		ch = getchar();
		if(!(ch >= '0' && ch <= '9')) break;
		ans = ans*10+ch-'0';
	}
	ans *= s;
}
bool input(){
	scanf("%d", &n);
	int i;
	for(i=1; i<=n; i++){
		getSNum(in[i]);
		ks[i]=in[i];
	}
	return true;
}
int lowb(int t){
	return t&(-t);
}
int hash(const int& k){
	return lower_bound(ks+1, ks+1+n, k)-ks;
}
void ins(int* ar, int i, int v){
	for(; i <= n; i+=lowb(i)){
		if(ar[i]<v){
			ar[i]=v;
		}
	}
}
void ins(int i, bool isFront){
	if(isFront){
		ins(front, i, i);
	}else{
		ins(back, n-i+1, n-i+1);
	}
}
void ins(int s){
	mark[s]=true;
	ls[s]=rs[s]=-1;
	ins(s, true);
	ins(s, false);
}
int qry(int* ar, int i){
	int ans=-1;
	for(; i > 0; i -= lowb(i)){
		if(ans < ar[i]){
			ans = ar[i];
		}
	}
	return ans;
}
int qryl(int k){
	return k>1 ? qry(front, k-1) : -1;
}
int qryr(int k){
	int ans=-1;
	if(k<n){
		ans=qry(back, n-k);
		if(ans >= 1){
			ans=n-ans+1;
		}
	}
	return ans;
}
void buildTree(){
	sort(ks+1, ks+1+n);
	int i, k, u;
	for(i=1; i<=n; i++){
		mark[i]=false;
		front[i]=back[i]=-1;
	}
	ins(root=hash(in[1]));
	que[1]=root;
	par[root]=-1;
	for(i=2; i<=n; i++){
		que[i]=k=hash(in[i]);
		ins(k);
		u=qryl(k);
		if(u>=1 && rs[u] < 0){
			rs[u]=k;
			par[k]=u;
		}else{
			u=qryr(k);
			if(u>=1 && ls[u] < 0){
				ls[u]=k;
				par[k]=u;
			}
		}
	}
}
void callens(){
	int i, u;
	for(i=n; i>=1; i--){
		u=que[i];
		llen[u]=(ls[u]==-1 ? 0: llen[ls[u]]+rlen[ls[u]]+1);
		rlen[u]=(rs[u]==-1 ? 0: llen[rs[u]]+rlen[rs[u]]+1);
	}
}
void calpos(){
	pos[root].first=llen[root]+1;
	pos[root].second=1;
	int i, u, f;
	for(i=2; i<=n; i++){
		f=par[u=que[i]];
		if(u==ls[f]){
			pos[u].first=pos[f].first-rlen[u]-1;
		}else{
			pos[u].first=pos[f].first+llen[u]+1;
		}
		pos[u].second=pos[f].second+2;
	}
}
void set(int i, int j, char ch){
	if(i>=sr && i<=sr+r-1 && j>=sc && j<=sc+c-1){
		out[i-sr+1][j-sc+1]=ch;
	}
}
void set(int r, int c1, int c2, char ch){
	if(r<sr || r>sr+r-1) return;
	if(c1<sc) c1=sc;
	if(c2>sc+c-1) c2=sc+c-1;
	if(c1>c2) return;
	int i;
	for(i=c1; i<=c2; i++){
		out[r-sr+1][i-sc+1]=ch;
	}
}
bool check(char* str){
	int i;
	for(i=0; str[i]; i++){
		if(str[i]!=' ') return true;
	}
	return false;
}
void handle(){
	int i, j, len;
	for(i=1; i<=r; i++){
		for(j=1; j<= c; j++){
			out[i][j]=' ';
		}
		out[i][j]='\0';
	}
	for(i=1; i<= n; i++){
		set(pos[i].second, pos[i].first, 'o');
		if(i!=root){
			set(pos[i].second-1, pos[i].first, '|');
			set(pos[i].second-2, pos[i].first, '+');
		}
		len=(ls[i]==-1 ? 0 : rlen[ls[i]]);
		set(pos[i].second, pos[i].first-len, pos[i].first-1, '-');
		len=(rs[i]==-1 ? 0 : llen[rs[i]]);
		set(pos[i].second, pos[i].first+1, pos[i].first+len, '-');
	}
	for(i=1; i<= r; i++){
		if(check(out[i]+1)){
			printf("%s\n", out[i]+1);
		}
	}
	printf("\n");
}
int ca=0;
void work(){
	int m, i;
	scanf("%d", &m);
	printf("Case #%d:\n", ++ca);
	for(i=1; i<=m; i++){
		scanf("%d%d%d%d", &sr, &sc, &r, &c);
		handle();
	}
}
void print(){
	int i;
	for(i=1; i<=n; i++){
		printf("%d (%d, %d)\n", i, ls[i], rs[i]);
	}
	printf("\n");
}
void solve(){
	buildTree();
	callens();
	calpos();
	work();
}
int main(){
	//freopen("in.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while(t--){
		input();
		solve();
	}
	return 0;
}