The country of Gridland is very special. It is divided into N rows and M columns; and both of them are 1 indexed. The intersection cell of the i-th row and the j-th column will be denoted as land(i, j). land(i, j) is either a flat surface of height Hij or does not have any land rather it contains only bottomless sea water. All heights are measured from sea level; if Hij is negative then it means the surface of that land is under the sea level. Gridland is very much prone to natural calamities. Some lands of the Gridland are so low that they become flood affected most of the time in a year. Again some land are so high that there is always fog in those lands. This has been a dream of the people from Gridland for many years that the height of the country will be adjusted to reduce effect of natural calamities. Government of Gridland decided to increase or decrease heights of all the lands such that heights of all the lands reside between L and U. But people of Gridland also wants to maximize the average height of the country. So government of Gridland decided to maximize the sum of the heights of all the lands. To increase or decrease height government can perform two operations
2/3 Given N, M, L, U and the height H of all the lands, use the operations described above to increase or decrease height of the lands such that the new heights of the lands are between the range L and U (inclusive) and sum of the heights of all the lands is the maximum. Help government of Gridland to solve the problem. Input First line of the input contains a positive integer T (T ≤ 300), number of test cases. First line of each test case contains four integers N, M, L and U (1 ≤ N,M ≤ 75, −1000 ≤ L ≤ U ≤ 1000). Each of the next N lines contains M integers Hij (−500 ≤ Hij ≤ 500), height of land(i, j) or character ‘X’, where ‘X’ means that the cell has bottomless sea water. Note: 90% of all the test cases contain N, M ≤ 20. Output First line of each test case contains test case number and ‘Impossible’, if there is no way to change the heights of all the lands with the operations described above such that the new height of each land remains between L and U. Otherwise print the sum of the new heights of all the lands (except ‘X’ marked lands). Following line contains N non-negative integers Ri (Ri ≤ 1000000), where Ri is the number of operation 1 applied on the row i and the next line will contain M non-negative integers Cj (Cj ≤ 1000000), where Cj is the number of operation 2 applied on column j. If there is any solution for a test case, then there will always be a solution with 0 ≤ Ri ≤ 1000000 and 0 ≤ Cj ≤ 1000000. If there are multiple solutions, print any of them. Sample Input 4 3301 -1 -1 0 0X2 112 2 2 5 10 14 32 1 1 5 10 X 2277 17 77 Sample Output Case 1: 7 200 001 Case 2: 36 15 17 10 9 Case 3: 0 0 0
3/3 Case 4: Impossible