30 435 20000 1000000000
23 24 1
14 30 3
24 22 3
14 9 3
14 1 2
24 30 1
25 26 3
22 23 3
19 25 1
2 11 5
23 6 6
26 22 1
20 5 2
1 8 1
2 21 4
4 24 1
12 14 4
29 22 7
12 10 6
17 28 3
7 10 3
20 16 2
4 21 1
24 14 3
7 22 2
29 12 5
29 9 2
4 26 3
11 1 1
10 16 1
9 30 4
13 2 5
17 12 1
7 28 2
27 21 1
25 9 1
12 26 3
7 18 1
28 21 3
15 10 6
28 11 1
6 16 4
16 24 7
25 2 4
6 10 4
10 13 1
23 8 1
30 10 1
5 25 2
9 2 1
30 3 2
20 6 2
11 12 2
28 30 7
12 30 1
16 5 1
11 6 1
21 14 2
8 21 3
8 26 1
26 29 3
13 18 1
19 10 1
24 20 8
16 30 2
28 13 2
18 27 3
20 4 5
16 21 1
11 30 1
25 3 1
17 9 3
22 25 3
18 22 1
24 18 1
28 23 1
30 6 2
13 8 2
28 18 4
20 17 4
27 25 2
8 17 1
5 7 6
4 27 6
21 17 4
19 20 4
11 21 3
17 2 6
2 3 2
24 28 1
14 16 3
3 13 3
16 4 3
12 24 3
24 7 1
18 16 3
19 9 2
8 10 3
13 11 6
25 13 1
16 1 2
15 19 1
8 7 2
1 5 3
21 19 1
17 1 3
26 14 2
4 22 5
22 9 2
27 14 2
21 10 2
11 10 1
12 19 3
14 20 1
2 7 5
17 11 2
3 12 3
17 18 1
25 16 1
27 2 8
25 20 5
28 1 2
5 13 2
2 1 1
11 29 5
12 22 2
15 7 1
11 22 2
14 13 1
21 30 1
15 1 1
17 24 3
22 19 1
12 28 1
29 15 6
5 12 1
18 12 6
24 15 2
6 24 3
3 11 1
3 8 2
7 14 1
11 4 1
7 6 1
11 9 6
5 15 4
23 10 1
3 17 2
4 29 3
24 25 1
21 20 6
23 7 1
22 10 1
24 3 1
2 10 2
10 28 1
22 27 4
30 20 4
18 20 3
25 17 2
13 26 1
22 28 4
27 8 3
2 29 4
5 17 1
26 24 1
12 4 7
8 12 2
22 6 1
26 27 1
4 30 1
24 1 3
13 19 2
1 25 1
20 13 3
26 3 1
6 4 1
9 13 2
8 5 1
11 23 1
23 26 1
19 14 1
17 30 1
21 1 4
4 7 2
11 26 5
27 5 1
13 21 1
2 15 3
2 26 3
16 26 2
13 23 1
3 19 1
4 1 2
6 28 2
4 10 1
9 23 1
3 15 2
3 18 4
26 9 7
9 20 1
28 26 5
14 4 3
5 6 4
14 15 1
21 25 2
19 17 1
27 23 5
26 17 1
28 14 2
23 30 2
25 12 3
9 10 1
1 13 2
29 24 4
29 8 6
3 21 3
16 9 4
20 23 3
9 4 2
5 14 3
28 25 2
16 27 5
25 23 3
13 6 1
17 15 5
18 29 3
30 7 4
12 7 4
18 30 3
8 20 4
20 3 2
16 28 3
7 3 6
22 1 3
28 5 2
21 24 2
6 29 1
2 19 2
26 19 1
28 20 3
23 29 5
14 6 2
27 20 1
22 17 1
8 2 1
12 21 6
11 24 3
22 15 4
7 13 3
10 25 2
15 26 1
5 29 4
15 28 1
22 16 4
15 21 7
21 9 1
1 29 1
6 15 1
11 7 2
5 10 2
18 8 2
16 11 2
11 27 3
26 7 1
16 17 3
17 7 1
30 25 5
15 11 1
9 24 3
16 7 2
12 13 4
11 14 3
16 8 1
19 18 1
2 6 3
8 6 2
27 28 2
3 28 5
27 12 2
2 20 3
18 11 1
30 27 1
7 20 1
26 5 1
19 29 1
18 2 1
15 20 1
27 10 7
28 29 1
25 11 2
21 7 1
15 30 3
17 13 1
12 20 2
6 1 1
26 10 2
19 8 1
28 4 3
22 30 2
27 19 1
18 25 1
6 21 5
25 14 1
19 6 2
13 15 1
10 1 3
9 27 1
20 11 1
1 20 6
1 12 3
22 21 7
23 18 6
17 6 2
25 15 2
3 6 1
29 17 1
23 14 2
3 9 1
4 3 4
14 17 1
15 12 7
1 27 1
16 15 1
8 4 2
9 8 2
6 18 2
14 3 2
9 1 4
18 21 6
30 8 4
2 4 2
17 27 1
14 18 1
5 21 1
13 24 1
5 30 1
13 4 1
2 30 4
18 9 3
17 10 1
4 25 5
21 23 6
2 14 7
29 3 1
30 29 3
3 22 1
8 25 1
4 15 2
27 6 1
6 12 1
16 12 1
18 15 3
26 20 4
7 25 1
24 2 7
13 22 7
24 10 2
11 5 3
6 25 2
18 26 1
8 14 5
19 23 3
22 8 4
18 5 5
23 17 1
1 7 4
9 6 1
4 18 5
4 17 1
10 3 4
26 21 2
29 16 3
12 9 2
15 23 3
12 2 1
5 23 2
28 8 1
20 22 3
14 22 2
27 24 7
27 15 3
5 22 2
29 10 1
19 16 1
18 1 3
10 18 2
5 4 4
19 4 2
20 10 1
26 6 3
30 19 4
23 1 1
27 3 3
29 13 1
19 1 5
19 24 1
28 19 2
5 19 2
25 29 3
2 28 1
4 23 3
7 29 1
14 10 2
27 7 1
30 26 1
29 27 5
3 1 1
9 5 2
23 2 4
3 23 3
12 23 1
29 14 3
3 16 2
24 5 4
5 2 3
24 8 3
19 11 3
13 27 1
9 7 3
2 16 2
2 22 4
3 5 4
29 21 1
9 28 3
20 29 1
13 16 5
15 9 2
1 30 3
26 1 2
13 30 2
8 11 3
15 8 3
19 7 3
23 16 1
