input:

200
3 1
50 50
3 2
0 50 50
3 3
25 25 25 25
8 1
41 59
7 3
37 30 7 26
3 3
16 12 18 54
9 2
9 43 48
9 3
3 40 42 15
9 1
29 71
9 2
40 42 18
5 1
76 24
5 1
39 61
9 2
23 38 39
10 4
18 15 34 2 31
7 2
23 28 49
9 4
15 13 25 19 28
7 1
64 36
6 1
50 50
9 1
4 96
4 1
64 36
9 2
24 45 31
9 2
3 61 36
9 1
65 35
8 4
6 1 3...

output:

500000004 
500000004 375000003 125000001 
406250003 109375001 250000002 265625002 562500004 
858129220 
40267248 73443306 307645653 13908396 542571454 781149891 223877799 478284083 469782292 483514097 271207900 851118600 686534546 
708608005 271088002 536992004 107032001 243224002 
763536836 2052710...

result:

ok 200 lines