3
10 3
1 2 3
5 6 4
100000 2
500 1000
600 1200
50000 1
100
200