input:

5 9
7 7 7 6 7
3 1 5
2 1 3
3 1 5
3 1 3
1 1 2 3
3 1 3
2 2 8
3 1 3
3 1 2

output:

6
6
7
3
0
8

result:

wrong answer 1st lines differ - expected: '7', found: '6'