UVa 10717 - Mint

// UVa 10717 - Mint

#include <iostream>
#include <climits>
#include <limits>
using namespace std;

#define ll unsigned long long
const ll oo = ULONG_MAX;

ll gcd(ll a, ll b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

int main() {
	ll n, t, x[50];
	ll lc[50][50];
	while ((cin >> n >> t) && (n || t)) {
		for (ll i = 0; i < n; i++)
			cin >> x[i];
		ll m = 0, l[230301];
		for (ll a = 0; a < n; a++)
			for (ll b = a + 1; b < n; b++)
				lc[a][b] = lcm(x[a], x[b]);
		for (ll a = 0; a < n; a++)
			for (ll b = a + 1; b < n; b++)
				for (ll c = b + 1; c < n; c++)
					for (ll d = c + 1; d < n; d++) {
						l[m] = lcm(lc[a][b], lc[c][d]);
						m++;
					}

		for (ll i = 0; i < t; i++) {
			ll h;
			cin >> h;
			ll s1 = oo, s2 = oo;
			for (ll j = 0; j < m; j++) {
				//cout << "D:" << l[j] << endl;
				ll d1 = h % l[j];
				ll d2 = (l[j] - d1) % l[j];
				if (d1 < s1)
					s1 = d1;
				if (d2 < s2)
					s2 = d2;
			}
			cout << h - s1 << " " << h + s2 << endl;
		}
	}
	return 0;
}