Nested Squares

Input: Standard Input

Output: Standard Output

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.

aaaaa

abbba

abcba

abbba

aaaaa

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 (99999X99999) 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 r₁, c₁, r₂, c₂, which actually denotes a bounding box whose upper left corner is (r₁, c₁) and lower right corner is (r₂, c₂). You can assume that (1 ≤ r₁, c₁, r₂, c₂ ≤ 2*|S|-1) , 0 ≤ r₂-r₁ ≤ 100 and 0 ≤ c₂-c₁ ≤ 100.

Output

For each set of input produce several lines of output.

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 Output for Sample Input

abca 2

3 2 5 7

3 2 3 2

Aacc32 1

1 1 8 2

Square 1:

Query 1:

bcccba

bcacba

bcccba

Query 2:

Square 2:

Query 1:

Problem setter: Shahriar Manzoor, Special thanks: Syed Monowar Hossain & Abdullah al Mahmud