# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Relations

Last week Mahde brought an array of n integers. **A***i* 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= **A***b* – **A***a* )

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.

### Samples

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.

#### amin21

→

Login to submit