uva1101測資B

Input:
1 2 2 3 10 20
1 3 2 3 22 33
3 2 2 3 4 5
5 3 2 3 2 3
4 13 2 6 478958010 729952078
8 13 28 91 375383947 679472915
88 12 212 369 385323303 424389928
3 9 136 930 143924817 190809723
11 19 12 457 659732977 662785237
2 22 6 7 856479724 969859628
1 16 530 821 598744449 903880067
1 15 13 57 198924845 700112347
8 7 44 751 688864020 700746569
51 12 404 652 588484142 650194479
21 3 13 6227 922902558 922921202
53 11 98 602 906317335 906988160
1 11 467 512 913587890 993308137
6 24 98 772 234347738 457964768
29 3 1407 2808 115329539 115669986
10 9 57 65 817 950
321 94 253 736 268047 987636
50 10 138 949 44446425 86572540
228 10 173 894 4273657 6865811
770 4 117 441 643460 678251
28 8 37 87 12221 57701
16 6 18 33 10933 71186
29 9 26 53 5053196 7231725
19 6 39 81 887 3186
90 9 26 50 60012919 88413257
31 80 13 34 46 62
115 100 762 771 422933 2762846
741 85 620 913 2609 19210
139 8 46 63 47 59
5 14 98 100 428229 6894790
1 1 1 1 1000000000 1000000000
1000000000 1000000000 1 1 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1
1 2 1 1 1000000000 1000000000
1 1000000000 1 1 1000000000 1000000000
1 1000000000 1 1 999999999 999999999
1 2 1 2 1000000000 1000000000
1 2 1 2 500000001 1000000000
1 2 1 2 500000000 1000000000
1 2 1 1000000000 1 1000000000
1 2 1 999999999 2 1000000000
1 2 1 500000000 2 1000000000
1 2 1 250000000 4 1000000000
1 2 142857142 999998107 125000000 999998107
1 2 142857142 999998107 125000000 999998106
1 2 142857142 999998107 142857142 999999269
1 2 142857142 999998107 142857143 999999269
1 2 764705877 764705877 1 1000000000
1 2 2 2 536870911 536870913
1 2 1 1 536870913 536870913
1 2 1 1 536870911 536870911
1 500000000 1 1 999999999 999999999
1 500000000 1 1 999999999 1000000000
1 31622 1 1 999950883 999950883
1 31622 1 1 999950883 999950884
1 22360 1 1 999939199 999939199
1 22360 1 1 999939199 999939200
1 1000 1 1 999999999 999999999
1 1000 1 1 999999999 1000000000
1 793 1 1 997354513 997354513
1 793 1 1 997354513 997354514
1 177 1 1 981506240 981506240
1 177 1 1 981506240 981506241
1 149 1 1 985768801 985768801
1 149 1 1 985768801 985768802
43 7 231 231 44617 44617
43 7 231 231 11276 11276
1 2 1000 2000 10000 11999
1 2 1000 2000 10000 12000
8071957 2 2 122071 861171556 878487762
122071 2 1 124007 507279062 936375880
244142 30519 477 3815 262512964 449472169
9 18 1 1 654783002 654783006
3 24 3 3 741131682 741131684
1 2 24 56 426142721 963013633
16 2 39 86 11431874 19587898
93 45 303 874 878212595 932175739
5 3 7 7 100000007 100000007
3 2 5 5 300000007 300000007
7 3 2 2 700000004 700000004
987654321 2 1 1 536870912 536870912
987654321 2 1 1 268435457 987654321
987654321 2 1 1 536870913 987654321
123456789 41152264 3 3 864197526 864197528
123456789 164609053 3 3 864197526 864197528
30000 10000 30000 30000 900000000 900000000
27272727 7272727 2 7 222222222 777777777
27272727 72727272 2 7 222222222 777777777
3141592 65358 979 3238 46264338 327950288
3141592 65358 979 3238 246264338 327950288
1111 1 11 11 11111 11111
1111 1 11 11 111111 111111
1 256 1 2 1048576 16777216
1 131072 1 2 1048576 16777216
100000 10 2000 100000 800000000 900000000
100000 10 200000 1000000 200 300
100000 10 3000000 70000000 100000000 999999999
110 101 10101010 10101011 11111111 111111111
110 10 10101010 10101011 11111111 111111111
2 3 1000 4000 3500 35999
2 3 1000 4000 3500 36000
5 7 1 8829348 2532132 1000000000
1 1 3000 6000 4000 5000
4 5 200 300 150 250
1 2 665 666 666 999
1 2 666 666 666 999
1 2 999 999 666 999
1 2 999 1000 666 999
0 0 0 0 0 0
Output:
Case 1: 1A 2M
Case 2: 1M 2A 1M
Case 3: impossible
Case 4: empty
Case 5: 25A 6M
Case 6: 6A 1M 2A 1M 11A 1M 5A 1M 3A 1M 4A 1M 7A
Case 7: 15A 1M 2A 1M 3A 2M 6A 1M 7A
Case 8: 767A 1M 1A 1M 1A 1M 2A 1M 1A 1M 7A
Case 9: 8743A 3M 6A
Case 10: 1M 17A 1M 2A 1M 1A 1M 19A 1M 2A 1M 6A
Case 11: 41A 2M 1A 1M 13A 1M 8A 1M 1A
Case 12: 4A 1M 6A 1M 14A 1M 5A 1M 10A 1M 6A 1M 5A
Case 13: 5117A 1M 5A 1M 6A 1M 1A 1M 4A 1M 5A
Case 14: 38A 1M 5A 1M 4A 1M 10A 1M 9A 1M 9A
Case 15: 14649246A 1M 1A
Case 16: 12845A 1M 9A 1M 7A 1M 5A
Case 17: 48A 1M 7A 1M 7A 1M 3A 1M 1A 1M 1A 1M 6A
Case 18: 101A 1M 9A 1M 8A 1M 22A 1M 21A
Case 19: 16317A 2M 2A 2M 2A 1M
Case 20: 4A 1M
Case 21: 9A 1M
Case 22: 87A 4M
Case 23: 18A 3M
Case 24: 13A 3M
Case 25: 3M
Case 26: 4M
Case 27: 2A 1M 1A 4M
Case 28: 2M
Case 29: 1A 6M
Case 30: impossible
Case 31: 31A 1M
Case 32: 3A
Case 33: impossible
Case 34: 4M
Case 35: 999999999A
Case 36: 1M
Case 37: empty
Case 38: empty
Case 39: 2A 1M 1A 2M 1A 1M 1A 1M 1A 3M 1A 1M 1A 2M 1A 2M 1A 1M 1A 3M 1A 2M 1A 9M
Case 40: 1M
Case 41: 999999998A
Case 42: impossible
Case 43: 1A 28M
Case 44: 1A 28M
Case 45: empty
Case 46: 1A
Case 47: 1A
Case 48: 1A 1M
Case 49: empty
Case 50: impossible
Case 51: empty
Case 52: 1A
Case 53: empty
Case 54: 28M
Case 55: 1A 28M 1A
Case 56: 2A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A 1M 1A
Case 57: 1M 499999999A
Case 58: 1A 1M
Case 59: 31620A 1M 31621A
Case 60: 2M
Case 61: 1M 22359A 1M 22359A
Case 62: 1A 2M
Case 63: 998A 1M 999A 1M 999A
Case 64: 3M
Case 65: 1M 792A 1M 792A 1M 792A
Case 66: 1A 3M
Case 67: 175A 1M 176A 1M 176A 1M 176A
Case 68: 4M
Case 69: 1M 148A 1M 148A 1M 148A 1M 148A
Case 70: 1A 4M
Case 71: 142A 1M 6A
Case 72: impossible
Case 73: 9000A
Case 74: 4000A 1M
Case 75: 3A 2M 1A 1M 1A 2M
Case 76: 2A 1M 1A 10M
Case 77: 1M 1016A
Case 78: 2A 2M 9A 2M 16A 1M 6A 1M 7A
Case 79: 1M 7A 2M 14A 1M 15A 1M 15A 1M 14A
Case 80: 1A 2M 1A 1M 1A 3M 1A 1M 1A 3M 1A 1M 1A 2M 1A 1M 1A 10M 1A
Case 81: 3A 1M 1A 16M
Case 82: 100A 1M 17A 2M
Case 83: 36A 2M 2A 3M 2A 1M 2A 2M 2A 2M 1A 1M 2A 1M 1A
Case 84: 1A 2M 1A 2M 1A 6M 1A 4M 1A 2M 1A 1M 1A 1M 1A 2M 1A 2M 1A 1M 1A 2M 1A
Case 85: 20A 1M 1A 1M 2A 1M 1A 1M 2A 1M 1A 3M 2A 1M 1A 1M 2A 1M 2A 2M 2A 1M 2A
Case 86: 29M
Case 87: 29M
Case 88: impossible
Case 89: 7A
Case 90: 1M 3A
Case 91: 2A 1M
Case 92: 9A
Case 93: 1M 3A
Case 94: 1M
Case 95: 79A
Case 96: impossible
Case 97: 100A
Case 98: 15A 2M
Case 99: 7A 1M
Case 100: 8A 3M
Case 101: impossible
Case 102: 70A 1M
Case 103: 9183A
Case 104: 1M
Case 105: 84A 1M
Case 106: 2M
Case 107: 10336A 2M
Case 108: impossible
Case 109: impossible
Case 110: 1A
Case 111: empty
Case 112: empty
Case 113: impossible