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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005

struct Info{

	bool operator<(const struct Info &arg) const{

		return base < arg.base;
	}

	int index;
	ll base,digit;
};

struct Query{

	bool operator<(const struct Query &arg) const{

		return loc < arg.loc;
	}

	ll loc;
	int index;
};

int H,W;
ll ans[3*SIZE];
ll POW[18];
ll BIT[SIZE];
ll num_row[SIZE],num_col[SIZE];
ll sum_digit[SIZE];
ll COL_SUM_DIGIT;
Info ROW[SIZE],COL[SIZE];
vector<Query> V_Query,QUERY[SIZE];
vector<Info> V_ROW,V_COL;


//仮数部の桁が増えるかチェックする関数→桁が増えるならtrueを返す
bool increase_digit(Info A,Info B){

	ll tmp = A.base*B.base;

	return tmp >= POW[17];
}

void add(int loc,ll value){

	BIT[loc] += value;

	loc += loc & -loc; //最後の1ビットを足した場所が次の★更新★場所

	while(loc <= W){
		BIT[loc] += value;
		loc += loc & -loc;
	}
}

ll getSum(int loc){

	ll sum = BIT[loc];

	loc -= loc & -loc; //最後の1ビットを引いた場所が次の★加算★場所

	while(loc > 0){
		sum += BIT[loc];
		loc -= loc & -loc;
	}
	return sum;
}

ll calc(int left,int right){ //left～rightの区間の総和を、sum(1～right)-sum(1～left-1)で求める
	return getSum(right)-getSum(left-1);
}

int main(){

	POW[0] = 1;
	for(int i = 1; i < 18; i++){

		POW[i] = POW[i-1]*10;
	}

	scanf("%d %d",&H,&W);

	ll tmp;
	ll num_digit;

	for(int i = 1; i <= H; i++){

		scanf("%lld",&tmp);
		num_row[i] = tmp;

		for(num_digit = 1; ;num_digit++){

			if(POW[num_digit] > tmp)break;
		}

		if(num_digit == 10){ //10億

			ROW[i].base = tmp/10;

		}else{

			ROW[i].base = tmp*POW[9-num_digit];
		}

		ROW[i].digit = num_digit-1;
		ROW[i].index = i;

		V_ROW.push_back(ROW[i]);
	}

	sort(V_ROW.begin(),V_ROW.end());

	COL_SUM_DIGIT = 0; //列の各数の桁の総和

	for(int i = 1; i <= W; i++){

		scanf("%lld",&tmp);
		num_col[i] = tmp;

		for(num_digit = 1; ;num_digit++){

			if(POW[num_digit] > tmp)break;
		}

		if(num_digit == 10){ //10億

			COL[i].base = tmp/10;

		}else{

			COL[i].base = tmp*POW[9-num_digit];
		}

		COL[i].digit = num_digit-1;
		COL[i].index = i;

		COL_SUM_DIGIT += COL[i].digit;

		V_COL.push_back(COL[i]);
	}

	sort(V_COL.begin(),V_COL.end());

	//行ごとの、桁の数を計算する

	sum_digit[0] = 0;

	int L,R,mid;
	ll plus_2,plus_1;

	for(int row = 1; row <= H; row++){

		L = 0,R = W-1,mid = (L+R)/2; //★V_COLに合わせるので0オリジン★
		int left_col = W;

		while(L <= R){

			if(increase_digit(ROW[row],V_COL[mid])){

				left_col = mid;
				R = mid-1; //より左へ

			}else{

				L = mid+1;
			}
			mid = (L+R)/2;
		}

		plus_2 = W-left_col;
		plus_1 = W-plus_2;

		sum_digit[row] = ROW[row].digit*W+COL_SUM_DIGIT+2*plus_2+plus_1;

		if(row == 0)continue;

		sum_digit[row] += sum_digit[row-1];
	}

	int num_query;
	scanf("%d",&num_query);

	for(int i = 0; i < num_query; i++){

		Query query;
		scanf("%lld",&query.loc);
		query.index = i;

		V_Query.push_back(query);
	}

	sort(V_Query.begin(),V_Query.end());

	L = 1;
	int loc_row;

	for(int i = 0; i < num_query; i++){

		if(V_Query[i].loc > sum_digit[H]){

			ans[V_Query[i].index] = -1;
			continue;
		}

		R = H,mid = (L+R)/2;

		//どの行の、どの相対位置かを求める

		while(L <= R){

			if(sum_digit[mid] >= V_Query[i].loc){

				loc_row = mid;
				R = mid-1;

			}else{

				L = mid+1;
			}
			mid = (L+R)/2;
		}

		Query query;
		query.loc = V_Query[i].loc-sum_digit[loc_row-1]; //★1オリジンなので注意★
		query.index = V_Query[i].index;

		QUERY[loc_row].push_back(query);
	}

	for(int i = 0; i <= W; i++)BIT[i] = 0;

	for(int i = 1; i <= W; i++){

		add(i,COL[i].digit+1);
	}


	int pre_left_col = -1;

	stack<ll> S;

	for(int i = 0; i < H; i++){ //行を仮数の昇順に処理

		//仮数の掛け算で繰り上がりする左端を求める

		L = 0,R = W-1,mid = (L+R)/2; //★V_COLに合わせるので0オリジン★
		int left_col = -1;
		int row = V_ROW[i].index;

		while(L <= R){

			if(increase_digit(ROW[row],V_COL[mid])){

				left_col = mid;
				R = mid-1; //より左へ

			}else{

				L = mid+1;
			}
			mid = (L+R)/2;
		}

		if(pre_left_col == -1){

			if(left_col != -1){

				for(int col = left_col; col <= W-1; col++){

					add(V_COL[col].index,1); //本来の位置に加算
				}
			}

		}else{

			if(left_col != -1){

				for(int col = left_col; col < pre_left_col; col++){

					add(V_COL[col].index,1); //本来の位置に加算
				}
			}
		}

		pre_left_col = left_col;

		if(QUERY[row].size() == 0)continue;

		for(int k = 0; k < QUERY[row].size(); k++){

			int l = 1,r = W;
			mid = (l+r)/2;
			int loc_col = -1;

			while(l <= r){

				tmp = calc(1,mid)+ROW[row].digit*mid;

				if(tmp >= QUERY[row][k].loc){

					loc_col = mid;
					r = mid-1;

				}else{

					l = mid+1;
				}
				mid = (l+r)/2;
			}

			ll calc_digit = QUERY[row][k].loc;

			if(loc_col > 1){

				calc_digit -= (calc(1,loc_col-1)+ROW[row].digit*(loc_col-1));
			}

			//numberのcalc_digit桁目
			ll number = num_row[row]*num_col[loc_col];

			while(!S.empty())S.pop();

			while(true){

				S.push(number%10);
				number /= 10;

				if(number == 0)break;
			}

			for(int count = 0; count < calc_digit; count++){

				ans[QUERY[row][k].index] = S.top();
				S.pop();
			}
		}
	}

	for(int i = 0; i < num_query; i++){

		if(ans[i] == -1){

			printf("x");
		}else{

			printf("%lld",ans[i]);
		}
	}

	printf("\n");

	return 0;
}