#include <iostream>
#include <random>
#include <array>
#include <algorithm>
#include <functional>
#include "utils.h"

using namespace std;

class BinsearchSolver {
public:
    BinsearchSolver(const vector<uint64_t> &arr, string label) : arr_(arr), label_(label) {
    }

    virtual void PreProcess() {}

    virtual bool Query(uint64_t q) = 0;

    void Process(uint64_t q) {
         timer_.Start();

        bool res;
//        auto getter = [this, &res, q]() {
//            res = Query(q);
//        };

        //sum_cache_misses += profiler.RunAndGetCacheMisses(getter);
        res = Query(q);
        timer_.Finish();
        yes_ += res;
        queries_count_++;
        results_.push_back(res);
    }

    string get_label() const {
        return label_;
    }

    void OutputResults(ostream &out) const {
        cerr << "Timer output for " << label_ << ":" << endl;
        cerr << "Percent of YES answer " << yes_ * 1.0 / queries_count_ << endl;
        cerr << "||||||||||Elapsed time for all queries : " << timer_.GetResult() << "ns" << endl;
        cerr << "||||||||||Average time for one binsearch : " << timer_.GetResult() * 1.0 / results_.size() << "ns"
             << endl;
//        cerr << "||||||||||Cache misses for all queries : " << sum_cache_misses << endl;
//        cerr << "||||||||||Average misses on one query: " << (sum_cache_misses * 1.0 / results_.size()) << endl;


        for (const auto &el : results_) {
            out << el << " ";
        }
        out << endl;
    }

    virtual ~BinsearchSolver() {}

private:
    int64_t sum_cache_misses = 0;
    int yes_ = 0;
    int queries_count_ = 0;
    Timer timer_;
    vector<int> results_;
protected:
    const vector<uint64_t> &arr_;
    string label_;
};

class SqrtBinsearchSolver : public BinsearchSolver {
public:
    SqrtBinsearchSolver(const vector<uint64_t> &arr, string label) : BinsearchSolver(arr, label) {
        PreProcess();
    }

    void PreProcess() override {
        sq_ = sqrt(arr_.size());
        layout_.reserve(sq_);
        int index = 0;
        while (index < arr_.size()) {
            layout_.push_back(arr_[index]);
            index += sq_;
        }
        cerr << "Sqrt Layout has been built" << endl;
    }

    bool TryFindInSubarray(int l, int r, uint64_t q) {
        auto it = lower_bound(arr_.begin() + l, arr_.begin() + r + 1, q);
        if (it == arr_.begin() + r + 1) {
            return false;
        }
        return (*it == q);
    }

    bool TryFindInPart(int i, uint64_t q) {
        return TryFindInSubarray(i * sq_, min((i + 1) * sq_ - 1, (int) arr_.size() - 1), q);
    }

    bool Query(uint64_t q) override {
        auto sq_find = lower_bound(layout_.begin(), layout_.end(), q);
        auto ind = sq_find - layout_.begin();
        if (ind == layout_.size()) {
            return TryFindInPart(layout_.size() - 1, q);
        }
        if (*sq_find == q) {
            return true;
        }
        if (ind == 0) {
            return false;
        }
        return TryFindInPart(ind - 1, q);
    }

    virtual ~SqrtBinsearchSolver() {}

private:
    int sq_ = -1;
    std::vector<uint64_t> layout_;
};

class DefaultBinsearchSolver : public BinsearchSolver {
public:
    DefaultBinsearchSolver(const vector<uint64_t> &arr, string label) : BinsearchSolver(arr, label) {
    }

    bool Query(uint64_t q) override {
        auto res_it = std::lower_bound(arr_.begin(), arr_.end(), q);
        if (res_it != arr_.end()) {
            return (*res_it) == q;
        }
        return false;
    }

    virtual ~DefaultBinsearchSolver() {}

};

class BTreeBinsearchSolver : public BinsearchSolver {
public:
    BTreeBinsearchSolver(const vector<uint64_t> &arr, string label, int b) : BinsearchSolver(arr, label), b_(b) {
        PreProcess();
    }

    void PreProcess() override {
        layout_.resize(arr_.size());
        int cur_arr_id_ = 0;
        int cur_v = 1;
        DfsInorder(cur_v, cur_arr_id_);
        cerr << "BTree Layout has been built" << endl;
    }

    void DfsInorder(int cur_v, int &cur_arr_id) {
        if (cur_v * 1ll * (b_) <= arr_.size()) {
            auto ver = cur_v * b_;
            for (int i = 0; i < b_ - 1; i++) {
                DfsInorder(ver, cur_arr_id);
                layout_.at(cur_v - 1) = arr_.at(cur_arr_id++);
                cur_v++;
                ver += b_ - 1;
            }
            DfsInorder(ver, cur_arr_id);
        } else {
            int cnt = 0;
            while (cnt < b_ - 1 && cur_v <= arr_.size()) {
                layout_.at(cur_v - 1) = arr_.at(cur_arr_id++);
                cur_v++;
                cnt++;
            }
        }
    }

    bool Query(uint64_t q) override {
        int cur_v = 1;
        int cnt = 0;
        int n = arr_.size();
        while (cur_v <= n) {
            cnt++;
            int l = cur_v - 1;
            int r = min(n - 1, l + b_ - 2);
            if (BinsearchInplace(l, r, q)) {
                return true;
            }
            uint64_t new_cur_v = (b_) * (cur_v + l) - l;
            if (new_cur_v > n) {
                break;
            }
            cur_v = new_cur_v;
        }
        return false;
    }

    inline bool BinsearchInplace(int &l, int r, uint64_t q) {
        if (r - l <= 8) {
            int cur = 0;
            for (int i = l; i <= r; i++, cur++) {
                if (layout_[i] == q) {
                    return true;
                }
                if (layout_[i] > q) {
                    l = cur;
                    return false;
                }
            }
            l = cur;
            return false;
        }
        auto l_val = layout_[l];
        if (l_val == q) {
            return true;
        }
        auto r_val = layout_[r];
        if (r_val == q) {
            return true;
        }
        if (l_val > q) {
            l = 0;
            return false;
        }
        if (r_val < q) {
            l = r - l + 1;
            return false;
        }
        int st_l = l;
        while (r - l > 1) {
            int m = (l + r) / 2;
            auto val = layout_[m];
            if (val == q) {
                return true;
            }
            if (val < q) {
                l = m;
            } else {
                r = m;
            }
        }
        l = l - st_l + 1;
        return false;
    }

    virtual ~BTreeBinsearchSolver() {}

private:
    vector<uint64_t> layout_;
    int b_;
};

class VanEmdeBoasSolver : public BinsearchSolver {
public:
    VanEmdeBoasSolver(const vector<uint64_t> &arr, string label) : BinsearchSolver(arr, label) {
        PreProcess();
    }

    void PreProcess() override {
        lg_ = Log2(arr_.size());
        layout_.resize(1 << lg_);
        std::copy(arr_.begin(), arr_.end(), layout_.begin() + 1);
        for (int i = arr_.size() + 1; i < layout_.size(); i++) {
            layout_[i] = arr_.back();
        }
        d_.resize(lg_ + 1);
        tt_.resize(lg_ + 1);
        pos_.resize(lg_ + 2);
        tmp_.resize(sqrt(layout_.size()));
        PrepareLayout(1, layout_.size() - 1, 1, lg_);
        cerr << "VanEmdeBoas Layout has been built" << endl;
    }

    int Log2(int val) {
        int cnt = 30;
        while (!((1 << cnt) & val)) {
            cnt--;
        }
        return (cnt + 1);
    }

    int CountOfDiv2(int val) {
        int cnt = 0;
        while (!(val & 1)) {
            val >>= 1;
            cnt++;
        }
        return cnt;
    }

    void PrepareLayout(int l, int r, int h, int log_len) {
        if (log_len == 1) {
            return;
        }
        int top_log = log_len / 2;
        int bottom_log = log_len - top_log;
        int cnt_top = (1 << top_log) - 1;
        int cnt_bottom = (1 << bottom_log) - 1;

        int layout_iter = r;
        int tmp_iter = cnt_top - 1;
        for (int i = r; i >= l; i--) {
            if (log_len - CountOfDiv2(i - l + 1) <= top_log) {
                tmp_[tmp_iter--] = layout_[i];
            } else {
                layout_[layout_iter--] = layout_[i];
            }
        }
        std::copy(tmp_.begin(), tmp_.begin() + cnt_top, layout_.begin() + l);
        PrepareLayout(l, l + cnt_top - 1, h, top_log);
        for (int i = 0; i <= cnt_top ; i++) {
            PrepareLayout(l + cnt_top + i * cnt_bottom, l + cnt_top + (i + 1) * cnt_bottom - 1, h + top_log,
                          bottom_log);
        }
        tt_[h + top_log] = log_len;
        d_[h + top_log] = h;
    }
    bool Query(uint64_t q) override {
        int bfs_pos = 1;
        int d = 1;
        pos_[1] = 1;
        for (int i = 1; i <= lg_; i++) {
            auto val = layout_[pos_[i]];
            if (val == q) {
                return true;
            }
            bfs_pos <<= 1;
            if (val < q) {
                bfs_pos |= 1;
            }
            if (i == lg_) {
                return false;
            }
            d++;
            int log_len = tt_[d];
            int top = log_len >> 1;
            int bottom = log_len - top;
            top = (1 << top) - 1;
            auto bottom_pos = (bfs_pos & top);
            pos_[d] = pos_[d_[d]] + top + (bottom_pos << bottom) - bottom_pos;
        }
        exit(1);
    }

    virtual ~VanEmdeBoasSolver() {}

private:
    vector<uint8_t> tt_;
    vector<uint8_t> d_;
    vector<int> pos_;
    int lg_;
    vector<uint64_t> layout_;
    vector<uint64_t> tmp_;
};

void GetResultsForOneSolver(const vector<uint64_t> &queries, ostream *outputs, BinsearchSolver *solver) {
    for (auto q : queries) {
        solver->Process(q);
    }
    solver->OutputResults(*outputs);
}

void GetResultsForAllSolversVector(const vector<uint64_t> &arr, const vector<uint64_t> &queries, int b,
                                   map<string, ostream *> outputs) {
    {
        DefaultBinsearchSolver dbs(arr, "bs");
        GetResultsForOneSolver(queries, outputs["bs"], &dbs);
    }
    {
        SqrtBinsearchSolver sbs(arr, "sqrt");
        GetResultsForOneSolver(queries, outputs["sqrt"], &sbs);
    }
    {
        BTreeBinsearchSolver bbs(arr, "btree", b);
        GetResultsForOneSolver(queries, outputs["btree"], &bbs);
    }
    {
        VanEmdeBoasSolver veb(arr, "veb");
        GetResultsForOneSolver(queries, outputs["veb"], &veb);
    }

}

void GetResultsForAllSolversIO(istream &input, int b, map<string, ostream *> outputs) {
    int n;
    input >> n;
    vector<uint64_t> arr(n);
    for (auto &el : arr) {
        input >> el;
    }
    int m;
    input >> m;
    vector<uint64_t> queries(m);
    for (auto &q : queries) {
        input >> q;
    }
    GetResultsForAllSolversVector(arr, queries, b, outputs);
}