You are given a matrix of size NxN containing only upper case letters. You have to perform two kinds of operations:

• Replace operation is to replace a row or column of the matrix with the given string.
• Count Operation returns the count of each letter in the required region.

The operations are given as:

• 0 x y str → Replace y th row with string str, if x = 0 or update yth column with string str (top to bottom), if x = 1
• 1 x1 y1 x2 y2 → Count the number of each latter in the rectangular region of the matrix where (x1, y1) is top-left point of the rectangle and (x2, y2) is the bottom-right point of the rectangle.

For every Count operation output the value of (1*number of A's + 2*number of B's + ... 26*number of Z's).

Input

The first line of the input file contains T which denotes the number of test cases.

The first line of each test case contains two integers N and q where N denotes size of the matrix and q denotes the number of queries. This is followed by NxN alphabetic matrix. The matrix is followed by q lines of queries, in the above given format.

T <= 10

N <= 500, Q <= 10000

0 <= x1 < N, 0 <= x2 < N, 0 <= y1 < N, 0 <= y2 < N

x1 <= x2, y1 <= y2

Warning: Huge I/O

Output

Print the output for each query line by line.

Example

Input:
1
4 3
ABCD
ABCD
ABCD
ABCD
1 0 0 3 3
0 0 2 PQRS
1 0 2 3 3
Output:
40
58