Mimi is playing with a string , consisting of only
0
s and 1
s. Her little sister comes along and being very curious, asks questions about the binary string:
If we consider the substring starting from the
th index, what is the leftmost index such that there are
occurrences of the digit
?
Help Mimi write a program to answer these queries.
Constraints
Let denote the length of string
.
For all subtasks:
Subtask 1 [20%]
Subtask 2 [80%]
Input Specification
The first line will contain the string .
The next line of input will contain a single integer, .
The next lines will each contain three space-separated integers:
,
, and
, the
th query.
Output Specification
The output should contain integers, each on a new line. The
th integer should be either the leftmost index such that there are
occurrences of the digit
, or
-1
if no such index exists.
Sample Input
010100
3
1 2 0
1 2 1
1 3 1
Sample Output
3
4
-1
Comments
Could someone explain the sample input and output?
For the first query the substring
is the first to have
occurrences of
so the answer is
, the second query the substring
is the first to have
occurrences of
hence the answer is
and for the last there is no substring containing
ones starting from first char.
don't you just hate it when you're doing something and your younger sibling comes over and asks "if we consider the substring starting from the
th index, what is the leftmost index such that there are
occurrences of the digit
?"
relatable