Holiday Train Trip

The railway of Flatland is a straight line with n stations. The track between a station and the next station is called a segment. The train runs from station 1 to station n and stops at every station. The train has k seats, numbered from 1 to k. Tickets are sold for the train. Each ticket is described by three numbers s, t and a, and lets the holder ride from station s to station t in seat a.

Vasya plans to ride the train from one station to another on one of his summer holiday days. m tickets have already been sold for that day, and there may be no seat that is free on every segment between the stations he wants. A ticket from one station to another in a given seat can be bought only if that seat is free on every segment between those stations.

Vasya noticed that he can sometimes still travel between two stations by buying several tickets and changing seats at some intermediate stations. Changing seats is inconvenient, so Vasya wants to buy the minimum number of tickets so that he has one seat for every segment of the trip.

Vasya has not yet decided where to start and where to finish. He wrote down q possible trips, and for each one he wants to know the minimum number of tickets he must buy to make that trip.

For each trip, find that minimum number of tickets, given the description of the tickets already sold and the list of trips.

The first line contains three integers n, m and k (2 is at most n, which is at most 200000; 0 is at most m, which is at most 200000; 1 is at most k, which is at most 200000): the number of stations, the number of tickets already sold, and the number of seats in the train.

Each of the next m lines contains three integers s_i, t_i and a_i: the station where the ticket starts, the station where it ends, and the seat number. It holds that 1 is at most s_i, which is less than t_i, which is at most n, and 1 is at most a_i, which is at most k.

It is guaranteed that no seat on any segment has more than one ticket.

The next line contains q (1 is at most q, which is at most 200000). Each of the next q lines contains two integers f_j and d_j: the starting station and the destination station of a trip, with 1 is at most f_j, which is less than d_j, which is at most n.

Print q numbers. For each trip, print the minimum number of tickets Vasya must buy to make that trip. If the trip is impossible, print -1 for it.

Every segment between stations 2 and 3 is fully occupied, so the trip from station 1 to station 5 is impossible. The trip from station 3 to station 5 can be made with two tickets: seat 2 from station 3 to station 4, and seat 1 from station 4 to station 5. The trip from station 4 to station 5 can be made with one ticket in seat 1.