This problem is a Mooshak version of a UVA Online Judge Problem.

[PC019] Census

This year, there have been many problems with population calculations, since in some cities, there are many emigrants, or the population growth is very high. Every year the ACM (for Association for Counting Members) conducts a census in each region. The country is divided into \(n^2\) regions, consisting of an \(n \times n\) grid of regions. Your task is to find the least, and the greatest population in some set of regions. Since in a single year there is no significant change in the populations, the ACM modifies the population counts by some number of inhabitants.

Input

In the first line you will find the integer \(n.\). The following \(n\) lines will each contain the \(n\) integers, representing the initial population of city \(c[y,x]\). In the following line is the number \(q\), followed by \(q\) lines with queries, each one being of one of the following two types::

• \(\text{q} \, y_1 \, x_1 \, y_2 \, x_2\) which represents the coordinates of the upper left and lower right of where you must calculate the maximum and minimum change in population.
• \(\text{c} \, y \, x \, v\) indicating a change of the population of city \(c[y, x]\) to value \(v\).

Output

For each query \(q \, y_1 \, x_1 \, y_2 \, x_2\) print in a single line the greatest and least amount of current population in that region, separated by a single space.

Constraints

• \( 1 \leq n \leq 500 \)
• \( 1 \leq q \leq 40\,000 \)
• \( 0 \leq c[i,j], v \leq 10^6\)
• \( 1 \leq y_1 \leq y_2 \leq n\)
• \( 1 \leq x_1 \leq x_2 \leq n\)
• \( 1 \leq x, y \leq n\)

5
1 2 3 4 5
0 9 2 1 3
0 2 3 4 1
0 1 2 4 5
8 5 3 1 4
4
q 1 1 2 3
c 2 3 10
q 1 1 5 5
q 1 2 2 2

9 0
10 0
9 2

• Query 1 (1 1 2 3) corresponds to the following region (max=9, min=0):

  1 2 3 4 5
  0 9 2  1 3
  0 2 3 4 1
  0 1 2 4 5
  8 5 3 1 4
  

• Query 1 (1 1 5 5) corresponds to the following region (max=10, min=0):

  1  2 3 4 5
  0 10 2 1 3
  0  2 3 4 1
  0  1 2 4 5
  8  5 3 1 4
  

• Query 1 (1 2 2 2) corresponds to the following region (max=10, min=0):

  1  2 3 4 5
  0  9 2 1 3
  0 10 3 4 1
  0  1 2 4 5
  8  5 3 1 4