Problem: Problem Statement

Have you experienced $10$-by-$10$ grid calculation? It's a mathematical exercise common in Japan. In this problem, we consider the generalization of the exercise, $N$-by-$M$ grid calculation.

In this exercise, you are given an $N$-by-$M$ grid (i.e. a grid with $N$ rows and $M$ columns) with an additional column and row at the top and the left of the grid, respectively. Each cell of the additional column and row has a positive integer. Let's denote the sequence of integers on the column and row by $a$ and $b$, and the $i$-th integer from the top in the column is $a_i$ and the $j$-th integer from the left in the row is $b_j$, respectively.

Initially, each cell in the grid (other than the additional column and row) is blank. Let $(i, j)$ be the cell at the $i$-th from the top and the $j$-th from the left. The exercise expects you to fill all the cells so that the cell $(i, j)$ has $a_i \times b_j$. You have to start at the top-left cell. You repeat to calculate the multiplication $a_i \times b_j$ for a current cell $(i, j)$, and then move from left to right until you reach the rightmost cell, then move to the leftmost cell of the next row below.

At the end of the exercise, you will write a lot, really a lot of digits on the cells. Your teacher, who gave this exercise to you, looks like bothering to check entire cells on the grid to confirm that you have done this exercise. So the teacher thinks it is OK if you can answer the $d$-th digit (not integer, see an example below), you have written for randomly chosen $x$. Let's see an example.

<image>

For this example, you calculate values on cells, which are $8$, $56$, $24$, $1$, $7$, $3$ in order. Thus, you would write digits 8, 5, 6, 2, 4, 1, 7, 3. So the answer to a question $4$ is $2$.

You noticed that you can answer such questions even if you haven't completed the given exercise. Given a column $a$, a row $b$, and $Q$ integers $d_1, d_2, \dots, d_Q$, your task is to answer the $d_k$-th digit you would write if you had completed this exercise on the given grid for each $k$. Note that your teacher is not so kind (unfortunately), so may ask you numbers greater than you would write. For such questions, you should answer 'x' instead of a digit.

* * *

Input

The input consists of a single test case formatted as follows.

> $N$ $M$ $a_1$ $\ldots$ $a_N$ $b_1$ $\ldots$ $b_M$ $Q$ $d_1$ $\ldots$ $d_Q$

The first line contains two integers $N$ ($1 \le N \le 10^5$) and $M$ ($1 \le M \le 10^5$), which are the number of rows and columns of the grid, respectively.

The second line represents a sequence $a$ of $N$ integers, the $i$-th of which is the integer at the $i$-th from the top of the additional column on the left. It holds $1 \le a_i \le 10^9$ for $1 \le i \le N$.

The third line represents a sequence $b$ of $M$ integers, the $j$-th of which is the integer at the $j$-th from the left of the additional row on the top. It holds $1 \le b_j \le 10^9$ for $1 \le j \le M$.

The fourth line contains an integer $Q$ ($1 \le Q \le 3\times 10^5$), which is the number of questions your teacher would ask.

The fifth line contains a sequence $d$ of $Q$ integers, the $k$-th of which is the $k$-th question from the teacher, and it means you should answer the $d_k$-th digit you would write in this exercise. It holds $1 \le d_k \le 10^{15}$ for $1 \le k \le Q$.

Output

Output a string with $Q$ characters, the $k$-th of which is the answer to the $k$-th question in one line, where the answer to $k$-th question is the $d_k$-th digit you would write if $d_k$ is no more than the number of digits you would write, otherwise 'x'.

Examples

Input| Output
---|---


2 3
8 1
1 7 3
5
1 2 8 9 1000000000000000


|


853xx



3 4
271 828 18
2845 90 45235 3
7
30 71 8 61 28 90 42


|


7x406x0






Example

Input




Output

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
//#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

//永続segtree
#define sz (1<<17)
struct per_seg{
	vector<int>root;
	int L[20000005],R[20000005],id;
	int seg[20000005];
	void make(){
		for(int i=0;i<sz-1;i++) L[i] = i*2+1,R[i] = i*2+2;
		root.push_back(0); id = 2*sz;
	}
	int update(int a,int k,int l,int r){
		if(l==r){
			seg[id] = 1;
			return id++;
		}
		if(l<=a && a<=(l+r)/2){
			int x = update(a,L[k],l,(l+r)/2);
			seg[id] = (seg[x]+seg[R[k]]);
			L[id] = x; R[id] = R[k];
			return id++;
		}
		else{
			int x = update(a,R[k],(l+r)/2+1,r);
			seg[id] = (seg[L[k]]+seg[x]);
			L[id] = L[k]; R[id] = x;
			return id++;
		}
	}
	void update(int pos){
		int R = root.back();
		int nw = update(pos,R,0,sz-1);
		root.push_back(nw);
	}
	pair<int,ll> query(vector<int>k,int l,int r,ll zan){
		if(l == r) return mp(l,zan);
        ll sum = 0;
        rep(x,k.size()) sum += seg[L[k[x]]];
        if(sum >= zan) {
            rep(x,k.size()) k[x] = L[k[x]];
            return query(k,l,(l+r)/2,zan);
        }
        else{
            rep(x,k.size()) k[x] = R[k[x]];
            return query(k,1+(l+r)/2,r,zan-sum);
        }
	}
    pair<int,ll> query(vector<int>ver,ll zan){
        rep(i,ver.size()) ver[i] = root[ver[i]];
		return query(ver,0,sz-1,zan);
	}
}kaede;


int n,m,q;
ll a[100005],b[100005],sum[100005];
ll ten[19];
ll rui[100005];
vector<pair<ll,int>>query,query2;
vector<pair<ll,int>>solve[100005];
int ans[300005];
int calc_digit(int i,int j,int x){
    ll V = a[i]*b[j]; //cout << V << " " << x << endl;
    vector<int>vi;
    while(V){vi.pb(V%10);V/=10;}
    reverse(vi.begin(),vi.end());
    assert(vi.size() >= x);
    return vi[x-1];
}
int main(){
    scanf("%d%d",&n,&m);
    repn(i,n) {sum[i] = m; scanf("%lld",&a[i]);}
    repn(j,m) scanf("%lld",&b[j]);
    ten[0] = 1;
    for(int i=1;i<=18;i++) ten[i] = ten[i-1]*10LL;
    repn(i,n){
        repn(j,18){
            ll dv = (ten[j]+a[i]-1)/a[i];
            query.pb(mp(dv,-i));
        }
    }
    repn(j,m) query.pb(mp(b[j],1));
    repn(j,m) query2.pb(mp(-b[j],j)); 
    SORT(query); reverse(query.begin(),query.end());
    SORT(query2); 

    int cur = 0;
    rep(i,query.size()){
        if(query[i].sc == 1) cur++;
        else sum[-query[i].sc]+=cur;
    }
    //repn(i,n) cout << sum[i] << endl;
    repn(i,n) rui[i] = rui[i-1]+sum[i];
    scanf("%d",&q);
    repn(i,q){
        ll x; scanf("%lld",&x);
        //rui[i] >= x min i
        if(rui[n] < x) { ans[i ]= -1; continue;}
        int xx = lower_bound(rui+1,rui+n+1,x)-rui;
        solve[xx].pb(mp(x-rui[xx-1],i));
        //cout << xx << " " << x-rui[xx-1] << " " << i << endl;
    }
    kaede.make();
    rep(i,query2.size()){
        kaede.update(query2[i].sc);
    }
    repn(i,n){
        vector<int>rt;
        for(int j=0;j<=18;j++){
            ll dv = (ten[j]+a[i]-1)/a[i];
            //dv以上の値を追加したときの永続segtreeのトップを求める
            int a = lower_bound(query2.begin(),query2.end(),mp(-dv,INF))-query2.begin();
            rt.pb(a); //if(i == 2) cout << a << " ";
        }
        //19個のsegtreeで上から舐める
        rep(j,solve[i].size()){
            pair<int,ll>ret = kaede.query(rt,solve[i][j].fi);
            //cout << i << ret.fi << ret.sc << endl;
            ans[solve[i][j].sc] = calc_digit(i,ret.fi,ret.sc);
        }
    }
    repn(i,q){
        if(ans[i] == -1) printf("x");
        else printf("%d",ans[i]);
    }
    puts("");
    return 0;
}