Simple ASCII characters can form a figure containing nested squares: as shown in Figure-1 below. Here the outer most square is formed by character ‘a’, the next square is formed by character ‘b’ and the innermost square is formed by character ‘c’. Figure 1: Nested squares of ASCII characters Figure 2: This is a nested square generated by the characteristic string ‘abca’. The dotted rectangle is the bounding box denoted by the corners (3,2) and (5,7). Such a square can be denoted uniquely by a characteristics string ‘abc’: that is the first character forms the outermost square, the next character forms the next square and so on. So a string of length 50000 can actually denote a (99999 × 99999) square grid, which will require around 9 Gigabyte of memory to be stored normally. In this problem you will be asked to print a small portion of such a huge square. The different characters that form a (N × N ) square are numbered in row major order, the upper left character is at position (1,1) and the lower right character is at position (N,N). This is shown in Figure 2. Input The first line contains an integer N (0 < N < 31) which denotes how many sets of inputs are there. The description of each set is given below. The first line of each set contains a string S (1 ≤ |S| ≤ 50000) and an integer Q (1 ≤ Q ≤ 50). Here S is the characteristic string of a nested square pattern and |S| is the length of string S. This string contains only alphabets and decimal digits. The integer Q denotes the total number of query. Each of the next Q lines contain four integers r1, c1, r2, c2, which actually denotes a bounding box whose upper left corner is (r1, c1) and lower right corner is (r2, c2). You can assume that (1 ≤ r1, c1, r2, c2 ≤ 2∗|S|−1), 0≤r2−r1 ≤100and0≤c2−c1 ≤100. There is a blank line between two consecutive input cases. Output For each set of input produce several lines of output.
2/2 The first line of output for each set contains the serial of the set. Then for each query produce the serial of query followed by the contents within the required bounding box. Print a blank line after the output for each test case. Look at the output for sample input for details. Sample Input 2 abca 2 3257 3232 Aacc32 1 1182 Sample Output Square 1: Query 1: bcccba bcacba bcccba Query 2: b Square 2: Query 1: AA Aa Aa Aa Aa Aa Aa Aa