5 5 10
3 1 2 1
3 4 3 3
1 3 1 2
4 2 3 2
5 1 4 1
3 1 4 1
3 4 2 4
2 2 2 1
2 2 1 2
1 2 1 1
5
5 5
2 3
2 1
4 1
1 5