**Time limit:**1.50 s**Memory limit:**512 MB

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:

- n - number of insertions and queries.
- m - number of bits to allocate for the bit array.
- n values to set.
- 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