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:

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 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