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
2
28
12
6
0
0
0
0
17
23
1
20
2
11
28
27
3
15
3
2
0
0
0
10
20
5
0
0
0
7
2
0
4
32
15
7
11
0
8
5
2
8
5
1
6
0
7
0
7
6
3
2
5
0
0
0
7
14
2
5
0
2
0
0
6
12
6
0
4
5
0
0
1
22
21
4
1
24
0
3
4
4
10
3
16
0
13
2
4
0
0
16
8
2
8
18
23
2
24
4
12
7
4
14
5
0
6
7
7
17
8
6
4
22
15
1
4
3
0
2
10
0
1...

result:

wrong answer 12th numbers differ - expected: '1', found: '2'