Input
2 1 4
1 5 3
3 3 10
7 10 2
6 4 8
Output
4
-1
8
-1
Input
1 5 2
1 5 10
2 7 4
Output
1
2