Description

You‘ve been given a N×N matrix {W_ij} containing the cost of a weighted bipartite graph, on this graph, you need to implement the following operations:

• C i j w : Change Wij to w.
• X i x0 x1 ... xn-1 : Change all Wij to xj.
• Y i y0 y1 ... yn-1 : Change all Wji to yj.
• A : Add a new pair of node to the current bipartite graph, then increase N by 1. The weight of those 2n+1 new edges will be set to 0 by default.
• Q : Query the current maximum weighted matching.

Input

N
(... following the N×N matrix ...)
M
(... following the M operation ......)

Output

...
(for each query, simply print the result.)

Example

Input 1:
2
1 0
0 1
3
Q
C 0 1 9
Q

Output 1:
2
9

Input 2:
10
76 98 80 30 87 84 78 75 53 26 
85 7 83 15 21 91 47 84 82 78 
36 39 49 64 71 14 53 2 82 21 
83 31 32 30 78 19 46 95 50 55 
50 76 63 54 99 55 50 16 29 26 
58 74 77 32 3 91 90 18 34 3 
56 23 2 78 84 83 71 41 32 54 
53 75 39 29 61 25 42 79 58 2 
19 13 65 94 9 33 61 5 1 70 
34 56 45 37 72 98 47 40 80 79 
20
Q
Y 3 62 90 89 41 58 56 34 55 53 53
X 0 7 30 30 76 2 48 8 18 89 88
Q
C 2 0 3
C 3 0 0
C 8 0 2
C 1 0 3
C 1 0 6
C 5 0 9
Q
A
X 10 93 8 56 40 4 56 30 32 59 11 52
Y 10 84 62 26 13 66 21 53 23 54 81 52
Q
Y 9 13 38 99 50 20 25 59 7 6 77 82
C 4 0 8
C 6 0 6
C 10 0 8
Q

Output 2:
870
849
844
947
899

Restriction

We guarantee the N will never be more than 100 even during the running time.

The total operation M will less than 10000, and among them the Query Operation will be less than 1000.