Mimi is playing with a string ~S~, consisting of only
1s. Her little sister comes along and being very curious, asks ~Q~ questions about the binary string:
If we consider the substring starting from the ~x_i~th index, what is the leftmost index such that there are ~y_i~ occurrences of the digit ~z_i~?
Help Mimi write a program to answer these queries.
Let ~|S|~ denote the length of string ~S~.
For all subtasks, ~1 \le x_i, y_i \le |S|~, and ~0 \le z_i \le 1~.
Subtask 1 [20%]
~1 \le |S| \le 1\,000~
~1 \le Q \le 1\,000~
Subtask 2 [80%]
~1 \le |S| \le 200\,000~
~1 \le Q \le 200\,000~
The first line will contain the string ~S~.
The next line of input will contain a single integer, ~Q~.
The next ~Q~ lines will each contain three space-separated integers: ~x_i~, ~y_i~, and ~z_i~, the ~i~th query.
The output should contain ~Q~ integers, each on a newline. The ~i~th integer should be either the leftmost index such that there are ~y_i~ occurrences of the digit ~z_i~, or
-1 if no such index exists.
010100 3 1 2 0 1 2 1 1 3 1
3 4 -1