4 9
1 2 2 3 1
1 1 2 5 10
2 2 5 5 100
3 1 5 2 1000
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3