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
1
0
2
33
22
11
0
0
0
0
23
29
1
25
3
14
34
33
3
15
5
2
0
0
0
2
4
1
1
0
0
7
2
0
5
32
15
7
11
0
4
6
2
9
6
1
6
3
8
0
7
6
3
2
5
0
0
0
16
16
4
7
0
2
0
0
6
12
6
0
2
3
0
0
1
17
14
1
1
13
2
3
2
5
10
3
17
0
17
2
3
0
2
19
10
2
8
18
26
2
27
4
14
7
4
14
6
1
2
8
4
16
10
6
4
21
15
1
3
3
0
2
5
2
...

result:

wrong answer 10th numbers differ - expected: '0', found: '1'