Alice the Fan (Codeforces 1089A)
Tags: DP, dp

Alice is a big fan of volleyball and especially of the very strong "Team A".Volleyball match consists of up to five sets. During each set teams score one point for winning a ball. The first four sets are played until one of the teams scores at least 25 points and the fifth set is played until one of the teams scores at least 15 points. Moreover, if one of the teams scores 25 (or 15 in the fifth set) points while the other team scores 24 (or 14 in the fifth set), the set is played until the absolute difference between teams' points becomes two. The match ends when one of the teams wins three sets. The match score is the number of sets won by each team.Alice found a book containing all the results of all matches played by "Team A". The book is old, and some parts of the book became unreadable. Alice can not read the information on how many sets each of the teams won, she can not read the information on how many points each of the teams scored in each set, she even does not know the number of sets played in a match. The only information she has is the total number of points scored by each of the teams in all the sets during a single match.Alice wonders what is the best match score "Team A" could achieve in each of the matches. The bigger is the difference between the number of sets won by "Team A" and their opponent, the better is the match score. Find the best match score or conclude that no match could end like that. If there is a solution, then find any possible score for each set that results in the best match score.

Input: The first line contains a single integer $$$m$$$ ($$$1 \le m \le 50\,000$$$) — the number of matches found by Alice in the book.Each of the next $$$m$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, b \le 200$$$) — the number of points scored by "Team A" and the number of points scored by their opponents respectively.

Output: Output the solution for every match in the same order as they are given in the input. If the teams could not score $$$a$$$ and $$$b$$$ points respectively, output "Impossible".Otherwise, output the match score formatted as "$$$x$$$:$$$y$$$", where $$$x$$$ is the number of sets won by "Team A" and $$$y$$$ is the number of sets won by their opponent. The next line should contain the set scores in the order they were played. Each set score should be printed in the same format as the match score, with $$$x$$$ being the number of points scored by "Team A" in this set, and $$$y$$$ being the number of points scored by their opponent.


Sample Inputs:
6
75 0
90 90
20 0
0 75
78 50
80 100

Sample Outputs:
3:0
25:0 25:0 25:0
3:1
25:22 25:22 15:25 25:21
Impossible
0:3
0:25 0:25 0:25
3:0
25:11 28:26 25:13
3:2
25:17 0:25 25:22 15:25 15:11

Solution (Python):
try:
    num_of_matches = int(input())
    teamA_win = False
    while num_of_matches > 0:
        num_of_matches -= 1
        (teamA_score, another_team_score) = (int(x) for x in input().split())
        if teamA_score < 65 and another_team_score < 65:
            print('Impossible')
            continue
        if teamA_score > another_team_score:
            teamA_win = True
        elif (another_team_score >= teamA_score and another_team_score - teamA_score <= 44) and teamA_score >= 65:
            teamA_win = True
        else:
            teamA_win = False
        if teamA_win == True:
            if teamA_score >= 75 and teamA_score - another_team_score >= 6:
                t = teamA_score - 50
                if t > 25:
                    s = another_team_score - (t - 2)
                    if s >= 0:
                        print('{0:n}:{1:n}'.format(3, 0))
                        s = another_team_score - (t - 2)
                        if s % 2 == 0:
                            print('{0:n}:{1:n}'.format(25, s / 2), '{0:n}:{1:n}'.format(25, s / 2), '{0:n}:{1:n}'.format(t, t - 2))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(25, int(s / 2) + 1), '{0:n}:{1:n}'.format(25, int(s / 2)), '{0:n}:{1:n}'.format(t, t - 2))
                            continue
                else:
                    print('{0:n}:{1:n}'.format(3, 0))
                    if another_team_score > 23:
                        t = another_team_score - 23
                        x = 23
                    else:
                        t = another_team_score
                        x = 0
                    if t % 2 == 0:
                        print('{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, x))
                        continue
                    else:
                        print('{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(25, x))
                        continue
            if another_team_score >= teamA_score:
                if teamA_score >= 75 and another_team_score - teamA_score <= 19:
                    s = teamA_score - 50
                    t = another_team_score - (s - 2)
                    t = t - 25
                    if t <= 46:
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(3, 1))
                            print('{0:n}:{1:n}'.format(0, 25), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(s, s - 2))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(3, 1))
                            print('{0:n}:{1:n}'.format(0, 25), '{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(s, s - 2))
                            continue
                if teamA_score >= 65 and another_team_score - teamA_score <= 44:
                    s = teamA_score - 50
                    t = another_team_score - (s - 2)
                    t = t - 50
                    if t <= 46:
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(3, 2))
                            print('{0:n}:{1:n}'.format(0, 25), '{0:n}:{1:n}'.format(0, 25), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(s, s - 2))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(3, 2))
                            print('{0:n}:{1:n}'.format(0, 25), '{0:n}:{1:n}'.format(0, 25), '{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(s, s - 2))
                            continue
            if teamA_score >= 75 and another_team_score >= 25:
                s = teamA_score - 75
                if s > 23:
                    s = teamA_score - 50 - 23
                    t = another_team_score - (25 + s - 2)
                    if t <= 46 and t >= 0:
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(3, 1))
                            print('{0:n}:{1:n}'.format(23, 25), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(s, s - 2))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(3, 1))
                            print('{0:n}:{1:n}'.format(23, 25), '{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(s, s - 2))
                            continue
                    elif another_team_score < 25 + s - 2:
                        s = teamA_score - 75
                        t = another_team_score - (s + 2)
                        if t >= 0:
                            if t > 23:
                                t -= 23
                                print('{0:n}:{1:n}'.format(3, 1))
                                print('{0:n}:{1:n}'.format(s, s + 2), '{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(25, t), '{0:n}:{1:n}'.format(25, 0))
                                continue
                            else:
                                print('{0:n}:{1:n}'.format(3, 1))
                                print('{0:n}:{1:n}'.format(s, s + 2), '{0:n}:{1:n}'.format(25, t), '{0:n}:{1:n}'.format(25, 0), '{0:n}:{1:n}'.format(25, 0))
                                continue
                    else:
                        t = another_team_score - 25
                        if t <= 69:
                            print('{0:n}:{1:n}'.format(3, 1))
                            if t > 23:
                                t = t - 23
                                x = 23
                            else:
                                x = 0
                            if t % 2 == 0:
                                print('{0:n}:{1:n}'.format(s, 25), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, x))
                                continue
                            else:
                                print('{0:n}:{1:n}'.format(s, 25), '{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(25, x))
                                continue
                        elif s >= t - 69:
                            s = teamA_score - (50 + 25 + (t - 69))
                            t = another_team_score - (25 + 23 + (t - 69))
                            if t <= 46:
                                if t % 2 == 0:
                                    print('{0:n}:{1:n}'.format(3, 1))
                                    print('{0:n}:{1:n}'.format(s, 25), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(teamA_score - (50 + s), teamA_score - (52 + s)))
                                    continue
                                else:
                                    print('{0:n}:{1:n}'.format(3, 1))
                                    print('{0:n}:{1:n}'.format(s, 25), '{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(teamA_score - (50 + s), teamA_score - (52 + s)))
                                    continue
                else:
                    t = another_team_score - 25
                    if t <= 69:
                        print('{0:n}:{1:n}'.format(3, 1))
                        if t > 23:
                            t = t - 23
                            x = 23
                        else:
                            x = 0
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(s, 25), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, x))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(s, 25), '{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(25, x))
                            continue
                    elif s >= t - 69:
                        s = teamA_score - (50 + 25 + (t - 69))
                        t = another_team_score - (25 + 23 + (t - 69))
                        if t <= 46:
                            if t % 2 == 0:
                                print('{0:n}:{1:n}'.format(3, 1))
                                print('{0:n}:{1:n}'.format(s, 25), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(teamA_score - (50 + s), teamA_score - (52 + s)))
                                continue
                            else:
                                print('{0:n}:{1:n}'.format(3, 1))
                                print('{0:n}:{1:n}'.format(s, 25), '{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(teamA_score - (50 + s), teamA_score - (52 + s)))
                                continue
            if teamA_score >= 65 and another_team_score >= 50:
                s = teamA_score - 65
                if s > 46:
                    s = teamA_score - 50 - 46
                    t = another_team_score - (50 + s - 2)
                    if t <= 46 and t >= 0:
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(3, 2))
                            print('{0:n}:{1:n}'.format(23, 25), '{0:n}:{1:n}'.format(23, 25), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(s, s - 2))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(3, 2))
                            print('{0:n}:{1:n}'.format(23, 25), '{0:n}:{1:n}'.format(23, 25), '{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(s, s - 2))
                            continue
                else:
                    t = another_team_score - 50
                    if t <= 59:
                        if s % 2 == 0:
                            x = y = s / 2
                        else:
                            x = int(s / 2) + 1
                            y = int(s / 2)
                        print('{0:n}:{1:n}'.format(3, 2))
                        if t > 23:
                            t = t - 13
                            z = 13
                        else:
                            z = 0
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(x, 25), '{0:n}:{1:n}'.format(y, 25), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(25, t / 2), '{0:n}:{1:n}'.format(15, z))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(x, 25), '{0:n}:{1:n}'.format(y, 25), '{0:n}:{1:n}'.format(25, int(t / 2) + 1), '{0:n}:{1:n}'.format(25, int(t / 2)), '{0:n}:{1:n}'.format(15, z))
                            continue
            print('Impossible')
            continue
        elif teamA_win == False:
            if teamA_score >= 50 and another_team_score >= 65:
                s = another_team_score - 65
                if s > 46:
                    if teamA_score >= s + 4:
                        t = teamA_score - (s + 4)
                        if t > 13:
                            t -= 13
                            if t % 2 == 0:
                                print('{0:n}:{1:n}'.format(2, 3))
                                print('{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(s - 25 + 4, s - 23), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(13, 15))
                                continue
                            else:
                                print('{0:n}:{1:n}'.format(2, 3))
                                print('{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(s - 25 + 4, s - 23), '{0:n}:{1:n}'.format(int(t / 2) + 1, 25), '{0:n}:{1:n}'.format(int(t / 2), 25), '{0:n}:{1:n}'.format(13, 15))
                                continue
                        elif t % 2 == 0:
                            print('{0:n}:{1:n}'.format(2, 3))
                            print('{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(s - 25 + 4, s - 23), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(0, 15))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(2, 3))
                            print('{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(s - 25 + 4, s - 23), '{0:n}:{1:n}'.format(int(t / 2) + 1, 25), '{0:n}:{1:n}'.format(int(t / 2), 25), '{0:n}:{1:n}'.format(0, 15))
                            continue
                s = another_team_score - (50 + 15)
                if s > 46:
                    s = another_team_score - (50 + 46)
                    t = teamA_score - (50 + s - 2)
                    if t >= 0:
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(2, 3))
                            print('{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(s - 2, s))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(2, 3))
                            print('{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(int(t / 2) + 1, 25), '{0:n}:{1:n}'.format(int(t / 2), 25), '{0:n}:{1:n}'.format(s - 2, s))
                            continue
                else:
                    s = another_team_score - (50 + 15)
                    if s % 2 == 0:
                        x = y = s / 2
                    else:
                        x = int(s / 2) + 1
                        y = int(s / 2)
                    t = teamA_score - 50
                    if t >= 13:
                        t -= 13
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(2, 3))
                            print('{0:n}:{1:n}'.format(25, x), '{0:n}:{1:n}'.format(25, y), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(13, 15))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(2, 3))
                            print('{0:n}:{1:n}'.format(25, x), '{0:n}:{1:n}'.format(25, y), '{0:n}:{1:n}'.format(int(t / 2) + 1, 25), '{0:n}:{1:n}'.format(int(t / 2), 25), '{0:n}:{1:n}'.format(13, 15))
                            continue
                    elif t % 2 == 0:
                        print('{0:n}:{1:n}'.format(2, 3))
                        print('{0:n}:{1:n}'.format(25, x), '{0:n}:{1:n}'.format(25, y), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(0, 15))
                        continue
                    else:
                        print('{0:n}:{1:n}'.format(2, 3))
                        print('{0:n}:{1:n}'.format(25, x), '{0:n}:{1:n}'.format(25, y), '{0:n}:{1:n}'.format(int(t / 2) + 1, 25), '{0:n}:{1:n}'.format(int(t / 2), 25), '{0:n}:{1:n}'.format(0, 15))
                        continue
            if teamA_score >= 25 and another_team_score >= 75:
                s = another_team_score - 75
                if s > 23:
                    if teamA_score >= s + 2:
                        t = teamA_score - (s + 2)
                        if t > 23:
                            t -= 23
                            if t % 2 == 0:
                                x = y = t / 2
                            else:
                                x = int(t / 2) + 1
                                y = int(t / 2)
                            print('{0:n}:{1:n}'.format(1, 3))
                            print('{0:n}:{1:n}'.format(s + 2, s), '{0:n}:{1:n}'.format(23, 25), '{0:n}:{1:n}'.format(x, 25), '{0:n}:{1:n}'.format(y, 25))
                            continue
                        else:
                            if t % 2 == 0:
                                x = y = t / 2
                            else:
                                x = int(t / 2) + 1
                                y = int(t / 2)
                            print('{0:n}:{1:n}'.format(1, 3))
                            print('{0:n}:{1:n}'.format(s + 2, s), '{0:n}:{1:n}'.format(0, 25), '{0:n}:{1:n}'.format(x, 25), '{0:n}:{1:n}'.format(y, 25))
                            continue
                s = another_team_score - 75
                if s > 23:
                    t = teamA_score - (25 + s - 2)
                    if t >= 0:
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(1, 3))
                            print('{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(s - 2, s))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(1, 3))
                            print('{0:n}:{1:n}'.format(25, 23), '{0:n}:{1:n}'.format(int(t / 2) + 1, 25), '{0:n}:{1:n}'.format(int(t / 2), 25), '{0:n}:{1:n}'.format(s - 2, s))
                            continue
                else:
                    t = teamA_score - 25
                    if t % 2 == 0:
                        print('{0:n}:{1:n}'.format(1, 3))
                        print('{0:n}:{1:n}'.format(25, s), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(0, 25))
                        continue
                    else:
                        print('{0:n}:{1:n}'.format(1, 3))
                        print('{0:n}:{1:n}'.format(25, s), '{0:n}:{1:n}'.format(int(t / 2) + 1, 25), '{0:n}:{1:n}'.format(int(t / 2), 25), '{0:n}:{1:n}'.format(0, 25))
                        continue
            if teamA_score < 25 and another_team_score >= 75:
                s = another_team_score - 75
                if s > 0:
                    s = another_team_score - 50
                    if teamA_score >= s - 2:
                        t = teamA_score - (s - 2)
                        if t % 2 == 0:
                            print('{0:n}:{1:n}'.format(0, 3))
                            print('{0:n}:{1:n}'.format(s - 2, s), '{0:n}:{1:n}'.format(t / 2, 25), '{0:n}:{1:n}'.format(t / 2, 25))
                            continue
                        else:
                            print('{0:n}:{1:n}'.format(0, 3))
                            print('{0:n}:{1:n}'.format(s - 2, s), '{0:n}:{1:n}'.format(int(t / 2) + 1, 25), '{0:n}:{1:n}'.format(int(t / 2), 25))
                            continue
                elif teamA_score > 23:
                    t = teamA_score - 23
                    print('{0:n}:{1:n}'.format(0, 3))
                    print('{0:n}:{1:n}'.format(23, 25), '{0:n}:{1:n}'.format(t, 25), '{0:n}:{1:n}'.format(0, 25))
                    continue
                else:
                    print('{0:n}:{1:n}'.format(0, 3))
                    print('{0:n}:{1:n}'.format(teamA_score, 25), '{0:n}:{1:n}'.format(0, 25), '{0:n}:{1:n}'.format(0, 25))
                    continue
            print('Impossible')
            continue
except ValueError:
    print('Invalid error..')
except Exception as ex:
    print(str(ex).replace(' ', ''))

Solution (Python):
f = [[[[None] * 201 for i in range(201)] for _ in range(4)] for haha in range(4)]

def solve(sa, sb, pa, pb):
    if sa == 3 or sb == 3:
        return
    if pa > 200 or pb > 200:
        return

    def myto(ntup):
        if ntup[2] > 200 or ntup[3] > 200:
            return
        if f[ntup[0]][ntup[1]][ntup[2]][ntup[3]]:
            return
        f[ntup[0]][ntup[1]][ntup[2]][ntup[3]] = (sa, sb, pa, pb)
        solve(*ntup)
    need = 25
    if sa + sb == 4:
        need = 15
    for o in range(0, need - 1):
        ntup = (sa + 1, sb, pa + need, pb + o)
        myto(ntup)
        ntup = (sa, sb + 1, pa + o, pb + need)
        myto(ntup)
    if sa + sb == 0 or sa + sb == 4:
        for o in range(need + 1, 210 - max(pa, pb)):
            ntup = (sa + 1, sb, pa + o, pb + o - 2)
            myto(ntup)
            ntup = (sa, sb + 1, pa + o - 2, pb + o)
            myto(ntup)
solve(0, 0, 0, 0)
m = int(input())
for _ in range(m):
    (a, b) = map(int, input().split())
    done = False
    for (i, j) in [[3, 0], [3, 1], [3, 2], [2, 3], [1, 3], [0, 3]]:
        if f[i][j][a][b]:
            done = True
            print(f'{i}:{j}')
            res = ''
            while i + j != 0:
                (ni, nj, na, nb) = f[i][j][a][b]
                res = f'{a - na}:{b - nb} ' + res
                (i, j, a, b) = (ni, nj, na, nb)
            print(res)
            break
    if not done:
        print('Impossible')

Solution (Python):
import random, sys, os, math, gc
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations, product
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
from bisect import bisect_left, bisect_right
from math import factorial, gcd
from operator import mul, xor
from types import GeneratorType
BUFSIZE = 8192
MOD = 10 ** 9 + 7
MODD = 998244353
INF = float('inf')
D4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]
D8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]
dp = [[[[0] * 4 for _ in range(4)] for _ in range(201)] for _ in range(201)]
ans = [[[[[] for _ in range(4)] for _ in range(4)] for _ in range(201)] for _ in range(201)]
dp[0][0][0][0] = 1
for A in range(201):
    for B in range(201):
        for x in range(3):
            for y in range(3):
                if not dp[A][B][x][y]:
                    continue
                s = 15 if x + y == 4 else 25
                for val in range(s + 1, 201):
                    if A + val <= 200 and B + val - 2 <= 200 and (not dp[A + val][B + val - 2][x + 1][y]):
                        dp[A + val][B + val - 2][x + 1][y] = 1
                        ans[A + val][B + val - 2][x + 1][y] = deepcopy(ans[A][B][x][y])
                        ans[A + val][B + val - 2][x + 1][y].append((val, val - 2))
                    if A + val - 2 <= 200 and B + val <= 200 and (not dp[A + val - 2][B + val][x][y + 1]):
                        dp[A + val - 2][B + val][x][y + 1] = 1
                        ans[A + val - 2][B + val][x][y + 1] = deepcopy(ans[A][B][x][y])
                        ans[A + val - 2][B + val][x][y + 1].append((val - 2, val))
                for val in range(s - 1):
                    if A + s <= 200 and B + val <= 200 and (not dp[A + s][B + val][x + 1][y]):
                        dp[A + s][B + val][x + 1][y] = 1
                        ans[A + s][B + val][x + 1][y] = deepcopy(ans[A][B][x][y])
                        ans[A + s][B + val][x + 1][y].append((s, val))
                    if A + val <= 200 and B + s <= 200 and (not dp[A + val][B + s][x][y + 1]):
                        dp[A + val][B + s][x][y + 1] = 1
                        ans[A + val][B + s][x][y + 1] = deepcopy(ans[A][B][x][y])
                        ans[A + val][B + s][x][y + 1].append((val, s))
X = [3, 3, 3, 2, 1, 0]
Y = [0, 1, 2, 3, 3, 3]

def solve():
    (A, B) = LII()
    for (x, y) in zip(X, Y):
        if dp[A][B][x][y]:
            print(f'{x}:{y}')
            print(' '.join([f'{i}:{j}' for (i, j) in ans[A][B][x][y]]))
            return
    print('Impossible')

def main():
    t = 1
    t = II()
    for _ in range(t):
        solve()

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def bitcnt(n):
    c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
    c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
    c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
    c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
    c = (c & 281470681808895) + (c >> 16 & 281470681808895)
    c = (c & 4294967295) + (c >> 32 & 4294967295)
    return c

def lcm(x, y):
    return x * y // gcd(x, y)

def lowbit(x):
    return x & -x

def perm(n, r):
    return factorial(n) // factorial(n - r) if n >= r else 0

def comb(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def probabilityMod(x, y, mod):
    return x * pow(y, mod - 2, mod) % mod

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0not r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

def getGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = LGMI()
        d[u].append(v)
        if not directed:
            d[v].append(u)
    return d

def getWeightedGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v, w) = LII()
        u -= 1
        v -= 1
        d[u].append((v, w))
        if not directed:
            d[v].append((u, w))
    return d
if __name__ == '__main__':
    main()