You are given a matrix of size NxN containing only upper case alphabets .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 alphabet 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 alphabets 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