Last week Mahde brought an array of n integers. Ai is the i-th integer of the array.
Each integer is positive and less than 100000.
Then he wrote m relations in his notebook. Each relation consists of 3 integers a, b, x (x= Ab – Aa )
Then he destroys this array and he gifts you the notebook, consisting of m relations.
Now he gives you q query. Each query has 3 integers a, b, p.
In each query, you have to tell the b’th integer, if the a’th integer is p, according to the m relations which is written in his notebook. And each query is independent form another query.
Input
The first line consists of 3 integers n, m, q. here n is the array size, m is the number of relations written in his notebook, q is the number of the query.
Next m lines consist of m relations a b x.
It is guaranteed that every relation is valid. Next q lines contain q query a b p.
- 1<=n,p,m,q<=100 000
- 1<=a,b<=n
- And each x will be valid according to his Array .
Output
For each query print a single line consisting the b-th integer, if a-th integer is p. If it is impossible to determine this single query from these relations then print -1.
Sample
| Input | Output |
|---|---|
5 3 4 1 2 3 2 3 2 3 4 4 1 2 5 1 3 4 1 4 5 1 5 9 | 8 9 14 -1 |
Remember each query is totally independent from others.
