Problem C
Fimbulferð

This spring, like many others, has had its fair share of really cold mornings. It’s quite a challenge to focus in class when you’re busy with desperately trying to warm your fingers. To try to prevent this we need a program that finds the warmest route between buildings! This is a normal and effective way to combat this problem.

Input

The input begins with a line containing three integers $1 \leq V, E \leq 5000$, $1 \leq Q \leq 10^5$. $V$ denotes the number of buildings on campus. $E$ denotes the number of paths between the buildings and $Q$ denotes the number of queries for the warmest route. We number the buildings from $1$ to $n$. The next $E$ lines each describe one path between a pair of buildings. Each of these lines contains three integers $1 \leq a, b \leq V$, $-10^9 \leq t \leq 10^9$. This means there is a path from building number $a$ to building number $b$ that cools one down by $t$. If $t$ is negative this means you get warmer instead, for example if there is an indoor walkway between the buildings. This does not mean there is necessarily a path from $b$ to $a$, the route could for example involve jumping off a balcony. Finally there are $Q$ liens, each describing one query. Each of those lines contain two integers $1 \leq a, b \leq V$, which means the query is asking for the warmest route from building number $a$ to building number $b$.

Output

For each query print how much one would cool down in the best case. If you get warmer print the corresponding negative number. If there is no route to the destination print engin leid. If it’s possible to walk around and get arbitrarily warm before reaching the destination print nogu hlytt.

8 10 3
1 2 10
2 3 -1
3 4 -1
4 2 -1
4 8 10
1 7 10
1 5 10
5 6 -20
6 7 10
7 8 10
1 7
1 8
8 1

0
nogu hlytt
engin leid