#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountll((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzll(x))
#define rep(i, n) for(int i = 0; i < n; i++)
const int inf9 = 1e9; const lint inf18 = 1e18;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ double y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); } double euclidean(double first, double second){ return sqrt(first * first + second * second); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + ","; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint P(int n, int r){ if(r < 0 || n < r) return 0; return (fact[n] * inv[n - r] % mod); } lint C(int p, int q){ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
template<class itr, class itr2> bool next_sequence2(itr first, itr last, itr2 first2, itr2 last2){ itr now = last; itr2 now2 = last2; while(now != first){ now--, now2--; (*now)++; if((*now) == (*now2)){ (*now) = 0; }else{ return true; } } return false; }
inline int at(lint i, int j){ return (i >> j) & 1; }

struct segtree{
    int sz = 1;
    vector<int> data;
    
    segtree(int n){
        while(sz < n){
            sz *= 2;
        }
        data.resize(sz * 2 - 1, 0);
    }
    
    void update(int k, int x){
        k += sz - 1;
        data[k] = x;
        while(k > 0){
            k = (k - 1) / 2;
            data[k] = max(data[k * 2 + 1], data[k * 2 + 2]);
        }
    }
    
    int query(int a, int b, int l, int r, int now){
        if(r <= a || b <= l){
            return 0;
        }
        if(a <= l && r <= b){
            return data[now];
        }
        return max(query(a, b, l, (l + r) / 2, now * 2 + 1), query(a, b, (l + r) / 2, r, now * 2 + 2));
    }
    
    int query(int a, int b){ // [a, b)
        return query(a, b, 0, sz, 0);
    }
};

int main(){
    int N, Q;
    cin >> N >> Q;
    int sz = 3e5 + 100;
    segtree seg(sz);
    for(int i = 0; i < N; i++){
        int c;
        cin >> c;
        seg.update(c, c);
    }
    for(int i = 0; i < Q; i++){
        int q;
        cin >> q;
        int ans = 0;
        for(int j = 0; j < sz; j += q){ // [j, j + q)
            ans = max(ans, seg.query(j, min(sz, j + q)) - j);
        }
        cout << ans << endl;
    }
}





### Prompt

Construct a cpp code solution to the problem outlined:

Give you N cards. Only one natural number is written on each card. However, the same number is never written.

From now on, as a question, I will say an appropriate natural number. Please answer the largest remainder you get when you divide the number on the card you have by the number I said.

For example, suppose you have three cards with 9, 3, and 8, respectively. If I say "4", find the remainder of 9 and 3 and 8 divided by 4, respectively. The remainders are 1, 3, and 0, respectively, but the largest remainder is 3, so 3 is the correct answer.

Let's get started. e? Is it hard to have a lot of cards? It can not be helped. Now let's use the computer to find the largest remainder. Create a program that finds the largest of the remainders of the number on the card divided by the number asked. Ask the question many times, not just once, but never ask the same number more than once.



input

The input consists of one dataset. Input data is given in the following format.


N Q
c1 c2 ... cN
q1
q2
::
qQ


The number of cards N (2 ≤ N ≤ 300000) and the number of questions Q (2 ≤ Q ≤ 100000) are given in the first line, separated by one space, and the number ci (1 ≤ 100000) written on the card in the second line. ci ≤ 300000) is given with one space delimiter. The following Q line is given the number qi (1 ≤ qi ≤ 300000) given as a question.

output

Output the maximum remainder on one line for each question.

Example

Input

3 3
9 3 8
4
6
5


Output

3
3
4

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountll((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzll(x))
#define rep(i, n) for(int i = 0; i < n; i++)
const int inf9 = 1e9; const lint inf18 = 1e18;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ double y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); } double euclidean(double first, double second){ return sqrt(first * first + second * second); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + ","; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint P(int n, int r){ if(r < 0 || n < r) return 0; return (fact[n] * inv[n - r] % mod); } lint C(int p, int q){ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
template<class itr, class itr2> bool next_sequence2(itr first, itr last, itr2 first2, itr2 last2){ itr now = last; itr2 now2 = last2; while(now != first){ now--, now2--; (*now)++; if((*now) == (*now2)){ (*now) = 0; }else{ return true; } } return false; }
inline int at(lint i, int j){ return (i >> j) & 1; }

struct segtree{
    int sz = 1;
    vector<int> data;
    
    segtree(int n){
        while(sz < n){
            sz *= 2;
        }
        data.resize(sz * 2 - 1, 0);
    }
    
    void update(int k, int x){
        k += sz - 1;
        data[k] = x;
        while(k > 0){
            k = (k - 1) / 2;
            data[k] = max(data[k * 2 + 1], data[k * 2 + 2]);
        }
    }
    
    int query(int a, int b, int l, int r, int now){
        if(r <= a || b <= l){
            return 0;
        }
        if(a <= l && r <= b){
            return data[now];
        }
        return max(query(a, b, l, (l + r) / 2, now * 2 + 1), query(a, b, (l + r) / 2, r, now * 2 + 2));
    }
    
    int query(int a, int b){ // [a, b)
        return query(a, b, 0, sz, 0);
    }
};

int main(){
    int N, Q;
    cin >> N >> Q;
    int sz = 3e5 + 100;
    segtree seg(sz);
    for(int i = 0; i < N; i++){
        int c;
        cin >> c;
        seg.update(c, c);
    }
    for(int i = 0; i < Q; i++){
        int q;
        cin >> q;
        int ans = 0;
        for(int j = 0; j < sz; j += q){ // [j, j + q)
            ans = max(ans, seg.query(j, min(sz, j + q)) - j);
        }
        cout << ans << endl;
    }
}





```