Create a Bit Array class. The class constructor should take a value m, and then allocate at least m bits of space. The class should support "set" and "get" operations where set(i) sets the ith bit to 1, and get(i) returns the value of the ith bit. (You can implement these as with operator[] if you want to get fancy.)

The program that uses the Bit Array class should accept an optional input file argument to read from file, or if no file is present read from standard input. The program should accept the -b flag to specify that "get" operations are to be tested, and the -t flag to indicate that timing data for set and get operations should be separately output to std::cerr.

Input

The input is a binary data stream either from file or standard input.

The file contains the 64-bit integers:

1. n - number of insertions and queries.
2. m - number of bits to allocate for the bit array.
3. n values to set.
4. n values to get.

Output

For each of the get values output 1 if the bit is set and 0 if not.

Constraints

• n and m are less than 10^9.

Example

Input:

As 64-bit binary:

4 10 2 4 6 8 3 4 5 6

Output:

0
1
0
1