KOPC12G - K12-Bored of Suffixes and Prefixes

no tags 

 

You are given an alphabetical matrix of size NxN .You have to perform two kinds of operations 1) Update and 2) query.The matrix contains only Uppercase English alphabets.
Update operation is to replace a row or  column of the matrix with the given string.
Query Operation returns the count of each alphabest in the query region.
The operations are given as
A) 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)
B) 1   x1 y1 x2 y2 -> Count the number of each alphabets in the rectangular region where (x1,y1) is topleft point of the rectangle and (x2,y2) is the bottom right point of the rectangle.
For count operation Print Output;
where Output=1*number  of A's + 2*number of B's + ...... 26*number of Z's;

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

hide comments
:D: 2012-10-28 12:14:37

Theoretically O(N*Q) could be optimal, if number updates is at least comparable with the number of queries. Then the test case size is O(N*N + N*Q) (in bytes).

Xunie J: 2012-03-12 12:43:52

O(NQlogN) also will pass!

Last edit: 2012-03-12 12:44:40
~ adieus ~: 2012-02-18 10:40:12

O(NQ) will pass !


Added by:Radhakrishnan Venkataramani
Date:2012-01-31
Time limit:0.100s-0.690s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own