Similar to speed dating, during speed interviewing, you rapidly do a bunch of interviews!

The interviewers are situated in a grid formation (\(​R\) by ​~C~). Each interviewer has a rating score (from ~1~ to ~100~). However, due to certain events, interviewers will occasionally change in rating.

Hungry for interviews, Reyno will interview with everyone in a square area. Being both ambitious and lazy, he wants to achieve a certain total summed score with interviewers.

Input Specification

The first line contains three numbers, ​~R~ ~C~ \(Q​\), the rows and column of the grid and the number of queries to answer.

The next ​~R~​ lines will each contain ​~C~​ numbers, representing the scores of the interviewers within the grid.

The next ​~Q~​ lines will contain a query of the following form:

1. U r c s​ – the interviewer at location​ ~(r, c)~​ now has a rating of ​~s~ ~(1 \le s \le 100)~.

2. S r c s​ – Reyno wants to know the side length of the square starting at ​~(r, c)~​ that has a total summed rating closest to ~s~ \((0 \le s​ \le 100​RC)\). If multiple squares are equally close, output the larger side length.

\(1 ​\le R, ​C ​\le 500\)

\(1 ​\le Q ​\le 10​^5\)

Output Specification

Output the answer to each S type query on its own line.

Sample Input

3 3 7
1 2 6
3 5 7
4 8 9
S 1 1 27
S 1 1 28
U 2 2 50
S 1 2 33
S 1 2 34
S 3 2 100
S 3 2 0

Sample Output

2
3
1
2
1
1

Explanation for Sample Output

The sum of the ratings for the answers of the S type queries are: ~11~, ~45~, ~2~, ~65~, ~8~, ~8~.