It is post COVID19 and an examination as a physical meet needs to be conducted. The institute has k classrooms, each as an array of m×n seats in a rectangle. l students need to appear in the examination. Each student has a batch (string) and a roll number (string). In order to control cheating, the institute decides to disallow 2 students of the same batch to occupy adjacent seats. Two seats are adjacent if they are consecutive in the same row, same column, same forward or backward diagonal. Print the seating order using backtracking. Treat the seats as variables and the students as values. Prefer filling from the smallest classroom (as per index, primary), lower row (secondary), and lower column (tertiary). In terms of students, prefer filling from a smaller batch number (primary) and a smaller roll number (secondary).
Input Format
The first line contains T, the number of test cases. The second line contains k (number of classrooms), m (number of rows) and n (number of columns). The next line contains l (number of students). The next l lines contain details of each student with batch and roll number separated by a space.
Output Format
For every test case print the details of all classroom from the smallest to the largest index. Each classroom details contain m rows, printing details of each row. The row details contain the occupancy of every seat, first printing the batch number of occupying student and then the roll number, totaling to 2n entries. In case a seat is unoccupied, print “NIL NIL”. Print -1 in case no solution exists.
Constraints
1≤m,n,k≤10
1≤l≤mnk
Note: l can be less than, equal to, or larger than the product mnk
Sample Input
2
2 4 3
20
A 01
B 02
C 03
D 04
A 05
B 06
C 07
D 08
A 09
B 10
C 11
D 12
A 13
B 14
C 15
D 16
A 17
B 18
C 19
D 20
2 4 3
10
A 01
B 02
C 03
A 04
B 05
C 06
A 07
B 08
C 09
A 10
Sample Output
A 01 B 02 A 05
C 03 D 04 C 07
A 09 B 06 A 13
C 11 D 08 C 15
A 17 B 10 C 19
D 12 NIL NIL D 16
B 14 NIL NIL B 18
D 20 NIL NIL NIL NIL
//Test case 2, space for illustration only
A 01 B 02 A 04
C 03 NIL NIL C 06
A 07 B 05 A 10
C 09 NIL NIL NIL NIL
B 08 NIL NIL NIL NIL
NIL NIL NIL NIL NIL NIL
NIL NIL NIL NIL NIL NIL
NIL NIL NIL NIL NIL NIL
