input:

10 500000
0 0 0 0 0 0 0 0 0 0
3 2 9
2 4 10
2 2 7
2 7 9
3 1 1
3 5 8
1 5 10 0
3 1 9
3 5 9
2 2 4
1 2 4 0
2 5 6
3 8 8
1 4 6 0
1 6 6 0
2 4 10
3 1 9
3 5 7
1 4 10 0
3 6 9
3 2 6
2 1 8
1 5 9 0
3 7 8
3 4 8
2 4 8
2 5 8
2 1 9
2 3 8
1 5 10 0
2 4 8
3 1 6
2 1 4
2 3 7
3 4 10
1 4 6 0
1 1 6 0
2 3 7
1 1 1 0
2 1 10
1 5...

output:

0
0
10
7
0
0
6
3
0
0
0
1
25
12
10
0
0
0
0
17
23
1
20
2
11
27
26
2
18
2
2
0
0
0
2
4
1
0
0
0
7
2
0
4
32
15
7
11
0
4
5
2
8
5
1
6
0
7
0
-999993
-1999994
-999997
2
-999995
0
0
0
7
14
2
5
0
2
0
0
6
12
6
0
-1000000
1
0
0
1
16
12
1
1
12
0
3
4
4
10
3
16
0
17
2
4
0
0
16
8
2
8
18
23
2
24
4
12
7
4
14
5
0
2
8
4
...

result:

wrong answer 60th numbers differ - expected: '7', found: '-999993'