3
3 5
1 2 3
1 6 7 12 1000000000000000000
1 3
1000000000
1 1000000000 1000000001
5 4
5 4 3 2 1
1 15 16 100