In the Bit Array class from task A20, implement the "location(i)" method that calculates the index of the ith 1-bit (i.e. the smallest index x, such that rank(x) == i). The class constructor and "set" should work as before. Watch out for off-by-one errors and note that location(0) should always be 0.

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 -l flag to specify that "location" operations are to be tested, and the -t flag to indicate that timing data for set 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. m - number of bits to allocate for the bit array.
3. n values to set.
4. n values for location queries.

Output

For each value i, output the index of the ith 1-bit in the Bit Array.

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:

1
1
2
2