Fax McClad, Croneria's bravest bounty hunter, is commanding a fleet of fighters to engage the Dankey Kang Gang!

The Dankey Kang Gang's ships are clustered into groups. The groups form a line and are numbered from to , from left to right. The group contains ships.

Fax can deploy different types of fighters, numbered from to . The fighter type is designed to engage continuous intervals of groups of enemy ships, but can only destroy at most enemy ships in total.

Fax wants to plan well ahead for the battle, so he will perform simulations. For each simulation, he will choose fighters of type and an interval of groups . He will deploy fighters of his chosen type so that each enemy group in his target interval will only be destroyed by one fighter.

Fax wants to know if it is possible, and to save money, the minimum number of fighters he will need to call for each simulation. Can you help him?

#### Constraints

Subtask | Percentage | Additional Constraints |
---|---|---|

No additional constraints. |

#### Input Specification

The first line of input will contain , , and .

lines of input follow. The line will contain .

lines of input follow. The line will contain .

lines of input follow. Each line will be in the form `j l r`

.

#### Output Specification

For each simulation, output the minimum number of fighters required. If it is not possible, print `-1`

.

#### Sample Input

```
6 2 3
1
3
2
5
1
2
4
6
1 1 3
1 3 6
2 1 6
```

#### Sample Output

```
2
-1
3
```

#### Explanation for Sample Output

The enemy groups contain ships.

The types of fighters can handle enemy ships.

For the first query, fighters can be deployed: one to destroy groups , and the other to destroy group .

For the second query, group cannot be destroyed by a single fighter.

For the third query, fighters can be deployed: one to destroy groups , another to destroy group , and one more to destroy group .

## Comments