Position of the K-th One

Difficulty: 1200 3500 ms 128 MB

implementation binary-search

Given a binary string, answer Q queries: where (1-based) is the K-th 1? Print −1 if there are fewer than K ones.

Input: the first line has the binary string; the second line has Q; the next Q lines each have one K.

Output: Q lines with the positions.

Constraints:

• 1 ≤ length, Q ≤ 10⁵

Sample Tests

10101
2
2
4

3
-1

0
1
1

-1

Read the Editorial