KOPC12G  K12Bored of Suffixes and Prefixes
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 topleft point of the rectangle and (x2,y2) is the bottomright 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:
20121028 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:
20120312 12:43:52
O(NQlogN) also will pass! Last edit: 20120312 12:44:40 

~ adieus ~:
20120218 10:40:12
O(NQ) will pass ! 
Added by:  Radhakrishnan Venkataramani 
Date:  20120131 
Time limit:  0.100s0.690s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own 