A compressed list of positions

compression search engines bit tricks binary search

A search index stores for each word the list of its occurrences: the numbers of the words of the text where it stands. The numbers are increasing, so what is stored is not them but the gaps between neighbours; the first gap is the first number itself. Each gap is written with the Elias δ code, and the codes are glued into one string of bits without separators.

The δ code of a number x ≥ 1 is built like this. Let x have N digits in binary. First N is written with the Elias γ code: as many zeros as N has binary digits after the first, then N itself in binary. Then comes the binary notation of x without its first digit (which is always 1). For example, δ(1) = 1, δ(3) = 0101, δ(5) = 01101, δ(21) = 001010101.

Decode the list and answer queries: how many occurrences of the word are among the first p words of the text. Three tests are the real lists of occurrences of the words «Наташа» (Natasha), «война» (war) and «и» (and) in the Russian original of “War and Peace”.

Input

The first line holds the number of occurrences k and the number of queries q (1 ≤ k ≤ 2·10⁵, 1 ≤ q ≤ 2·10⁵). The second holds a string of zeros and ones: the codes of the k gaps in a row. The occurrence numbers are at most 10¹². The third holds q numbers p (1 ≤ p ≤ 10¹²).

Output

q lines: for each p, how many occurrences have a number at most p.

Examples

Example 1

Input

4 6
0101101101001010101
1 3 8 9 29 100

Output

Example 2

Input

1 2
0001010111101000
999 1000

Output

0
1

Limits

Time · Python: 4000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

There are no separators between the codes. How do you tell where the code of one gap ends? Look at what stands at the start of each code and how much it says about its length.

2Hint 2

The leading zeros are the first phase of exponential search: each zero doubles the bound, and the first one closes it. How many digits must be read after that one?

3The idea

The code is prefix-free: no code word is the beginning of another, so the string reads unambiguously from left to right. Count the zeros up to the first one, say z of them; the next z + 1 digits, starting with that one, are the length of the gap N; the next N − 1 digits with a one put in front are the gap itself. The occurrence numbers are the running sums of the gaps, and the answer to a query is a binary search in the sorted list of numbers.

4Walkthrough

In Python the first one is conveniently found with the method str.index("1", at), which runs through the zeros in C, and digits are turned into a number with int(…, 2). Each bit of the string is read once. The numbers accumulate in a list in increasing order, and bisect_right(positions, p) answers how many of them are at most p.

What all this trouble is for. The list of occurrences of «Наташа», 827 numbers, takes 9198 bits in the δ code, about 11 per number, against 26,464 as 32-bit numbers. The list of «и», 21,079 numbers, takes 8 bits each instead of 32: the gaps of frequent words are short, and the code adapts to them by itself. Real indexes compress gaps in the same way, with Elias, Golomb or byte-oriented codes, and decompress them on the fly when searching.

4+Solution

5Complexity

O(L + q log k), where L is the length of the bit string: decoding is one pass, each query a binary search.

6Common mistakes

Reading the gaps with the γ code. The γ code is only the first part of δ, the length of the gap. If the gap itself is read with it, the string falls apart from the first code. This is wrong.py.
Forgetting the leading one. The tail of the δ code is the digits of the gap without the leading one; it must be put back.
A number instead of a gap. The codes store differences of neighbouring numbers, the first difference being the first number itself. The answer concerns the numbers, that is, the running sums.
32-bit numbers. The numbers reach 10¹²; Go needs int64.

Algorithms behind it

SRT Algorithm Exponential search Steps 1, 2, 4, 8, … until you overshoot, then binary search: when the bound is unknown or the answer is near. 2⌊log₂ i⌋ + 1 questions to position i 1 problem SYS Data structure Inverted index and BM25 A dictionary “word → documents that contain it”: a query reads a few short lists instead of all the texts. O(total length of the query words' lists); AND by galloping O(m·log(n/m)) 2 problems