Mimi is playing with a string , consisting of only
1s. 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.
Let denote the length of string .
For all subtasks:
Subtask 1 [20%]
Subtask 2 [80%]
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.
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.
010100 3 1 2 0 1 2 1 1 3 1
3 4 -1