Implement the Packed Array class, that takes the array size n and the width per element w as constructor argument. The Packed Array should then support at most n append(m) calls, to append the value 0 <= m < 2^w to the array. get(i) (or operator[]) should return the ith value appended to the array.

The program that uses the Packed 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 -i flag to specify that Packed Array operations are to be tested, and the -t flag to indicate that timing data for append and get operations should be output separately 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. w - number of bits taken by each element.
3. n values to append.
4. n values for index queries.

Output

For each index query value i, output the ith element appended to the Packed Array.

Constraints

• n is less than 10^9
• 0 < w <= 64

Example

Input:

As 64-bit binary:

4 3 2 4 6 7 3 2 1 0

Output:

7
6
4
2