3 300
100 50 150
100 50 150
100 50 150
3 300
100 50 150
100 50 150
200 50 150
9 18
3 1 1
3 1 1
3 1 1
4 100 1
5 100 1
5 100 1
10 5 3
10 5 3
1 7 1000
10 18
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
8 9 10
9 10 11
10 11 12
0 0