Sample run 3 (a) [25 marks] You are to write a program that will fit a set of dominoes onto a grid which is 7 squares high, and eight squares across. This is to be subject to restrictions, in the form of doubles in fixed positions, and to the rule that two touching squares can only be equal if they belong to the same domino. A square should only be considered to touch the four squares directly above, below, left or right. Dominoes may not overlap. You should first read in input indicating where the fixed doubles are. For each double this will be in the form of an x co-ordinate and y co-ordinate for one of the halves of the domino, and a R or B to indicate whether the other half is to the right or below. The top left corner of the board is at (1,1). The list of doubles will terminate with the number -1. Note that not all the doubles may be fixed, and that their value is left for you to decide. Once you have read the list you should try and fit the other dominoes to the grid. You should then output a valid solution if there is one, or print 'Impossible'. Your program should then terminate. ```8 3 B 4 1 R 5 7 R -1 0-1 0 1-1 0-3 0 | | 5-0 2 0-6 1-2 4 1-3 1-4 1-5 1 0 | | 3-2 4-2 5-2 6 0 2-6 3-4 3-5 3-6 4-5 4-6 5-6 5-5 6-6 3-3 2-2 4-4 ```