Under construction

Still being built. Things may change

Counting Events

Time limit2sMemory limit1024 MB

Summary
Given n numbers and q queries, decide for each query whether it can be built from the numbers by repeatedly applying bitwise OR and AND.
Level

Medium6 of 10

Topics
Bit manipulation, Math
Solved
No attempts yet

Statement

While waiting for Thanos on Titan, Doctor Strange did not waste time. He used the Eye of Agamotto, which holds the Time Stone, the fifth Infinity Stone, to calculate the odds of winning the war. He picked nn actions the Avengers can take and qq actions whose feasibility he needs to check. Each action is labeled with a number that uniquely identifies it. The Avengers' actions are a1,a2,…,ana_1, a_2, \ldots, a_n, and the actions to check are b1,b2,…,bqb_1, b_2, \ldots, b_q.

The magician knows that the timeline works as follows. If action xx and action yy can be performed, then actions x∨yx \lor y and x∧yx \land y can also be performed, where ∨\lor and ∧\land are bitwise OR and bitwise AND. For each b1,b2,…,bqb_1, b_2, \ldots, b_q, decide whether it can be obtained this way. Help Strange, since Thanos will arrive on Titan soon. Any action can be performed any number of times.

Input

The first line contains nn, the number of actions the Avengers can perform (1≤n≤1000001 \le n \le 100000).

The next line contains nn integers aia_i, the numbers describing these actions (0≤ai≤1090 \le a_i \le 10^9). All numbers are pairwise distinct.

The third line contains qq, the number of actions to check (1≤q≤1000001 \le q \le 100000).

The last line contains qq integers bjb_j, the numbers describing these actions (0≤bj≤1090 \le b_j \le 10^9).

Output

On the ii-th line, print YES if the action described by bib_i can be performed, and NO otherwise.

Hint

The numbers 11, 33, and 44 can be obtained without using ∨\lor and ∧\land, and 5=4∨15 = 4 \lor 1.

Examples1

  1. Example 1

    Input
    3
    1 3 4
    6
    1 2 3 4 5 6
    
    Expected output
    YES
    NO
    YES
    YES
    YES
    NO