C++ :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
#define MAXN 100010
inline int next(){
	int ret = 0;
	scanf("%d",&ret);
	return ret;
}
int a[MAXN], n;
inline int id(int x){
	int ret = x % 9;
	if(x != 0 && ret == 0) ret = 9;
	return ret;
}
struct Seg{
	Seg(){
		sum = 0;
		memset(s, false, 10*sizeof(bool));
		memset(ls, false, 10*sizeof(bool));
		memset(rs, false, 10*sizeof(bool));
	}
	bool s[10], ls[10], rs[10];
	int l, r, sum;
	Seg *lc, *rc;
}nodes[MAXN*3], *head;
Seg *newSeg(int l,int r){
	head->l = l;
	head->r = r;
	head->sum = 0;
	memset(head->s, false, 10*sizeof(bool));
	memset(head->ls, false, 10*sizeof(bool));
	memset(head->rs, false, 10*sizeof(bool));
	return head ++;
}
void build(Seg *p,int l,int r){
	if(l == r){
		int t = id(a[l]);
		p->s[t] = p->ls[t] = p->rs[t] = true;
		p->sum = t;
		return ;
	}
	p->lc = newSeg(l, (l + r)/2);
	p->rc = newSeg((l + r)/2 + 1, r);
	build(p->lc, l, (l+r)/2);
	build(p->rc, (l+r)/2+1, r);
	p->sum = id(p->lc->sum + p->rc->sum);
	for(int i = 0;i < 10; ++i){
		if(p->lc->ls[i]) p->ls[i] = true;
		if(p->rc->rs[i]) p->rs[i] = true;
		if(p->lc->s[i] || p->rc->s[i]) p->s[i] = true;
		if(p->lc->rs[i]) p->rs[id(p->rc->sum+i)] = true;
		if(p->rc->ls[i]) p->ls[id(p->lc->sum+i)] = true;
		for(int j = 0;j < 10; ++j)
			if(p->lc->rs[i] && p->rc->ls[j]) p->s[id(i+j)] = true;
	}
}
Seg merge(Seg *x,Seg *y){
	Seg ans;
	for(int i = 0;i < 10; ++i){
		if(x->ls[i]) ans.ls[i] = true;
		if(y->rs[i]) ans.rs[i] = true;
		if(x->s[i] || y->s[i]) ans.s[i] = true;
		if(x->rs[i]) ans.rs[id(y->sum+i)] = true;
		if(y->ls[i]) ans.ls[id(x->sum+i)] = true;
		for(int j = 0;j < 10; ++j)
			if(x->rs[i] && y->ls[j]) ans.s[id(i+j)] = true;
	}
	return ans;
}
Seg Query(Seg *p, int l,int r){
	if(p->l >= l && p->r <= r) return *p;
	int mid = (p->l + p->r) / 2;
	if(mid >= r) return Query(p->lc, l, r);
	else if(l > mid) return Query(p->rc, l, r);
	else{
		Seg L = Query(p->lc, l, mid);
		Seg R = Query(p->rc, mid + 1,r);
		return merge(&L, &R);
	}
}
int main()
{
	//freopen("digit.in","r",stdin);
	//freopen("digit.out","w",stdout);
	//int cas = next(), ca = 0;
	int n;
	while(scanf("%d",&n) != EOF){
		for(int i = 1;i <= n; ++i) a[i] = next();
		head = nodes;
		Seg *root = newSeg(1, n);
		build(root, 1, n);
		int m = next();
		//printf("Case #%d:\n",++ca);
		Seg ans;
		while(m-- > 0){
			int l = next();
			int r = next();
			ans = Query(root, l, r);
			int cnt = 0;
			for(int i = 9;i >= 0 && cnt < 5; --i){
				if(ans.s[i] || ans.ls[i] || ans.rs[i]){
					if(cnt != 0)putchar(' ');
					printf("%d",i);
					cnt ++;
				}
			}
			while(cnt < 5){
				if(cnt != 0)putchar(' ');
				printf("-1");
				cnt ++;
			}
			puts("");
		}
	}
}