5
10 6 1
0 1 4 1 6 2 0 2 3 5
10 6 1
0 0 1 0 2 0 1 0 4 5
10 1 1
1 0 0 0 0 0 0 0 0 0
10 1 1
1 0 0 1 1 0 0 0 0 0
10 5 1
0 0 0 2 5 0 2 0 1 2