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 xith index, what is the leftmost index such that there are yi occurrences of the digit zi?"

relatable