鉴于本样例过于平凡，提供一组样例供调试：

INPUT:

20 30
0 2 -3 -1 -2 1 -1 -4 2 2 5 -5 2 0 5 3 4 2 2 1
2 7 16 5
1 11 19 8
2 11 19 4
2 4 14 -2
2 19 20 -4
1 16 17 2
2 19 19 -4
1 20 20 1
1 10 15 6
1 13 18 1
1 18 18 18
2 15 15 -1
1 6 18 11
2 3 14 4
2 6 18 -1
1 9 11 3
2 4 15 2
2 19 20 2
1 18 19 2
1 8 10 3
1 12 19 7
1 11 13 1
1 1 16 4
2 18 18 0
1 8 20 10
1 19 19 1
2 11 20 -5
2 12 14 5
2 11 18 -3
2 20 20 0

OUTPUT:

10
12
0
14
6
-1
12
15
5
10
14
7
2
12
0