15 80 2 1000000
4 15 4
4 8 3
1 3 4
10 4 3
13 5 1
4 9 3
9 10 1
15 10 4
14 4 2
5 8 2
15 9 2
1 4 3
10 2 3
3 9 1
15 7 1
3 8 3
1 7 4
12 3 1
2 3 2
15 13 1
2 11 4
12 4 4
7 14 1
12 14 2
14 5 4
8 7 3
15 2 4
10 5 4
6 13 4
11 8 1
2 6 2
12 5 2
1 2 1
3 11 2
3 5 2
10 8 1
2 14 2
5 2 1
7 2 1
1 5 3
7 9 4
14 8 1
6 14 2
11 4 4
7 6 3
15 8 4
8 1 4
6 9 2
8 9 1
9 5 4
7 4 4
1 15 2
4 5 4
11 6 3
9 14 1
7 10 4
3 10 3
15 3 1
10 11 1
9 12 4
7 5 4
10 13 1
11 9 1
14 3 2
8 13 3
10 14 2
13 12 3
15 14 3
13 7 3
10 6 4
6 8 4
3 13 1
13 14 2
11 15 3
3 4 1
12 15 1
1 6 1
10 1 3
1 9 3
8 2 3
