Minimum Tickets Purchase on a Rail Line

A railway line consists of $n$ stations placed along a straight line, and the segment between any two consecutive stations is called a section. A train starts at station 1 and stops at every station until it reaches station $n$. The train has $k$ seats, numbered from 1 to $k$.

Some tickets have already been sold. Each ticket is represented by three integers $s$, $t$, $a$, meaning that the passenger holding that ticket is allowed to travel from station $s$ to station $t$ in seat number $a$. A ticket from station $s$ to station $t$ can only be purchased if the corresponding seat is free in every section between $s$ and $t$ (i.e. the seat is free on every segment from station $s$ to station $t-1$).

On a summer day, Vasya wants to travel on the train from one station to another. He finds that due to the $m$ sold tickets, there might be no single ticket available for the entire journey he is interested in. However, he can purchase several tickets and switch seats at intermediate stations so that he always has a seat on every section of his journey. His goal is to buy the minimum number of tickets so that the entire journey is covered by tickets.

Vasya is considering several travel plans. In total, there are $q$ queries. For each query with starting station $S$ and ending station $T$ ($S < T$), output the minimum number of tickets that must be purchased in order to cover all sections from $S$ to $T$. If it is impossible to cover the journey (i.e. there exists a section with no available seat), output -1.

Note: A ticket for a given seat is valid only if the seat is free on all segments between the chosen stations. Formally, if a seat is free on a contiguous block of segments from $L$ to $R$ (note that these segments correspond to a ticket from station $L$ to station $R+1$), then that ticket can be purchased.

The sold tickets affect the availability on each seat independently. You need to consider the free intervals on every seat and then determine, for each travel query, if it is possible to cover the journey using one or more available tickets. The answer is the minimum number of tickets required, or -1 if it is not possible.

inputFormat

The first line contains three integers: $n$ (2 ≤ n), $k$ (1 ≤ k), and $m$ (the number of sold tickets).

The next m lines each contain three integers $s$, $t$, $a$ (1 ≤ s < t ≤ n and 1 ≤ a ≤ k), describing a sold ticket. This ticket means that seat $a$ is occupied on all segments from station $s$ to station $t-1$.

The next line contains an integer $q$, the number of queries.

Each of the following q lines contains two integers $S$ and $T$ (1 ≤ S < T ≤ n), representing a travel plan from station $S$ to station $T$.

outputFormat

For each query, output a single integer: the minimum number of tickets that need to be purchased to cover the journey from station $S$ to station $T$. If it is impossible to cover the journey on every segment, output -1.

sample

6 2 3
1 3 1
3 6 1
2 4 2
3
1 6
4 6
1 2

 -1
1
1