For a given sequence $A = \\{a_0, a_1, ..., a_{n-1}\\}$ which is sorted by ascending order, find a specific value $k$ given as a query.

Constraints

* $1 \leq n \leq 100,000$
* $1 \leq q \leq 200,000$
* $0 \leq a_0 \leq a_1 \leq ... \leq a_{n-1} \leq 1,000,000,000$
* $0 \leq k_i \leq 1,000,000,000$

Input

The input is given in the following format.


$n$
$a_0 \; a_1 \; ,..., \; a_{n-1}$
$q$
$k_1$
$k_2$
:
$k_q$


The number of elements $n$ and each element $a_i$ are given in the first line and the second line respectively. In the third line, the number of queries $q$ is given and the following $q$ lines, $q$ integers $k_i$ are given as queries.

Output

For each query, print 1 if any element in $A$ is equivalent to $k$, and 0 otherwise.

Example

Input

4
1 2 2 4
3
2
3
5


Output

1
0
0
#define ENABLE_DEBUG 0
// hidden common codes{{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(lint ngtkana_is_a_genius=0; ngtkana_is_a_genius<(lint)k; ngtkana_is_a_genius++)
using lint=long long;
using ld=long double;
template<class T> using numr=std::numeric_limits<T>;
struct input_t {
    template<class T> operator T() {
        T t;
        std::cin>>t;
        return t;
    }
} input;
#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

template <class Value> struct splay_node {
    using this_type = splay_node<Value>;

    enum class kstate {
        left,
        right,
        none
    };

    this_type *parent, *left, *right;
    std::size_t size;
    Value value;

    splay_node()
        : parent(nullptr)
        , left(nullptr)
        , right(nullptr)
        , size(1u)
        , value()
    {}

    splay_node(splay_node const&)=default;
    splay_node(splay_node&&)=default;
    splay_node& operator=(splay_node const&)=default;
    splay_node& operator=(splay_node&&)=default;
    ~splay_node()=default;

    splay_node(Value x)
        : parent(nullptr)
        , left(nullptr)
        , right(nullptr)
        , size(1u)
        , value(x)
    {}

    kstate state() const {
        assert(!parent || parent->left==this || parent->right==this);
        if (!parent) return kstate::none;
        if (parent->left==this) return kstate::left;
        if (parent->right==this) return kstate::right;
        throw;
    }

    void update() {
        size = 1u;
        if (left) size += left->size;
        if (right) size += right->size;
    }

    void rotate() {
        DEBUG("rotate", this);
        assert(parent);
        this_type *p=parent, *pp=p->parent, *c;

        this->parent=pp;
        if (pp) (pp->left==p ? pp->left : pp->right) = this;

        p->parent=this;

        if (p->left==this) {
            c = right;
            p->left=c;
            right=p;
            if(c)c->parent=p;
        }
        if (p->right==this) {
            c = left;
            p->right=c;
            left=p;
            if(c)c->parent=p;
        }

        p->update();
        update();
    }

    this_type* splay() {
        DEBUG("splay", this);
        this_type *now = this;

        while (now->parent) {
            if (!now->parent->parent) {
                now->rotate();
            } else if (now->state() == now->parent->state()) {
                now->parent->rotate();
                now->rotate();
            } else {
                now->rotate();
                now->rotate();
            }
        }

        return now;
    }
};

template <class Value> splay_node<Value>* get(splay_node<Value>* root, std::size_t i) {
    std::size_t lsize = root->left ? root->left->size : 0u;
    std::size_t rsize = root->right ? root->right->size : 0u;
    DEBUG("get", i, root, lsize, rsize, root->size);
    assert(i < root->size);
    if (i == lsize) {
        root->splay();
        return root;
    } else if (i < lsize) {
        assert(root->left);
        return get(root->left, i);
    } else {
        assert(root->right);
        return get(root->right, i-lsize-1);
    }
}

template <class Value> bool binary_search(splay_node<Value>* root, Value x) {
    DEBUG("binary_search", root, x, root->value);
    if (x < root->value) {
        return root->left && binary_search(root->left, x);
    } else if (root->value==x) {
        return true;
    } else {
        return root->right && binary_search(root->right, x);
    }
}

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    lint n=input;
    std::vector<splay_node<lint>> a(n);
    for(lint i=0;i<n;i++){
        lint x=input;
        a.at(i).value=x;

        if (i<n-1){
            a.at(i).parent = &a.at(i+1);
            a.at(i+1).left = &a.at(i);
            a.at(i+1).update();
        }
    }
    splay_node<lint>* root = &a.at(n-1);

    std::mt19937 mt{ 0 };

    lint q=input;
    LOOP(q){
        lint x=input;
        DEBUG(x);
        bool ans;
        ans = binary_search(root, x);
        root = get(root, std::uniform_int_distribution<lint>(0, n-1)(mt));
        std::cout<<ans<<'\n';
    }
}

