5 5
1 2 3 4 5
1 0 1 5
2 0
1 1 1 5
2 1
1 2 2 4