Mimi is playing with a string ~S~, consisting of only 0s and 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.

Constraints

Let ~|S|~ denote the length of string ~S~.

For all subtasks:

~1 \le x_i, y_i \le |S|~

~0 \le z_i \le 1~

Subtask 1 [20%]

~1 \le |S|, Q \le 1\,000~

Subtask 2 [80%]

~1 \le |S|, Q \le 200\,000~

Input Specification

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.

Output Specification

The output should contain ~Q~ integers, each on a new line. 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.

Sample Input

010100
3
1 2 0
1 2 1
1 3 1

Sample Output

3
4
-1