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

Same as A21 but harder!

If the last test crashes, make sure you are using at most ~2m bits of memory.

# 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 sum queries.

# Output

For each value i, output the number of 1-bits in the first i bits of 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