CSES - B41 Sum-based random access
  • Time limit: 3.00 s
  • Memory limit: 512 MB

Implement sum-based random access for VByte encoded data as described in the course materials. But now you need to be efficient.

Input data is read from a file given as a command line argument.

First encode n in put integers, then output data_structure[q_i] for each of the q query integers.

Simply scan from the beginning for each of the query values.

The tests will also use the -q command line flags when invoking your program, to be compatible with other tests that could use the same program.

Input

All 64-bit unsigned binary integers:

the integer n, followed by
n integers, followed by
the integer q, followed by
q integers in the [0, n) range.

Output

data_structure[q_i] for each of the q integers.

Constraints

  • n << 2^32

Example

Input (in binary):

2, 7, 500, 2, 1, 0

Output:

500
7