Same as A22 but harder!

If the last test fails, make sure you only use ~2m bits of space!

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

• m is less than or equal to 10^9.
• n is less than 10^7

Example

Input:

As 64-bit binary:

4 10 2 4 6 8 3 4 5 6

Output:

1
1
2
2