In the Bit Array class from task A20, implement the "sum(i)" method that calculates the number of 1-bits in the first i bits. The class constructor and "set" should work as before.

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 -s flag to specify that "sum" operations are to be tested, and the -t flag to indicate that timing data for set and get operations should be output 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 sum queries.

Output

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