Kazami Yuuka is a very powerful Youkai. Except for the incredible fighting capacity, she is also known as the "Flower Master of the Four Seasons".
TH_KazamisParterre.jpg
She loves seasonal flowers, so throughout the year she moves to the respective place where the flowers grow: spring flowers for spring, summer flowers for summer, autumn flowers for autumn, and although there aren't many, winter flowers for winter.
This time, she comes to a parterre with N rows and M columns. There is exactly one flower in each 1 * 1 grid. All flowers in the parterre formed many rectangle loops, from the border to the center of the parterre. Each loop has a width of 1 and consists of a same kind of flowers.
Kazami Yuuka loves flowers so much that she asks you Q questions about Q submatrices of the parterre. For each question, you need to answer the number of different kinds in the submatrix TOTAL, the index of the kind with the maximal number of flowers INDEX and the number of flowers of this kind COUNT. If there are multiple answers, choose the answer with the smallest INDEX.
Input
There are multiple test cases. For each test case:
The first line contains two integers N (1 <= N <= 500) and M (1 <= M <= 500). Then followed by ceil(min(N, M) / 2) lines, each line contains an integer Ai (1 <= Ai <= 250) denotes the kind index of a rectangle loop of flowers, from the border to the center. Next, there is a line containing an integer Q (1 <= Q <= 10000) and Q lines of four integers Ti, Li, Bi and Ri indicating the positions of the i-th submatrix's top, left, bottom and right edges, respectively. Ti, Bi are between 0 and N-1; Li, Ri are between 0 and M-1.
Output
For each test case, output three integers that described above.
Sample Input
2 5
1
1
0 0 1 4
3 3
1
2
1
0 0 2 2
Sample Output
1 1 10
2 1 8
