Shortest Path on a Grid with Temporary Edge Removal

Given an $n \times n$ grid graph, each point $(x,y)$ has two possible outgoing directed edges:\

1. If $y<n$, there is an edge from $(x, y)$ to $(x, y+1)$ with weight $ea_{x,y}$.\
2. If $x<n$, there is an edge from $(x,y)$ to $(x+1, y)$ with weight $eb_{x,y}$.\

The task is to compute the shortest path from $(1,1)$ to $(n,n)$. In addition, there are $q$ queries. In each query, an edge is temporarily removed from the grid. Specifically, if the removed edge is horizontal (denoted by 'R'), then the edge from $(x,y)$ to $(x, y+1)$ is removed; if it is vertical (denoted by 'D'), then the edge from $(x,y)$ to $(x+1,y)$ is removed. After computing the shortest path (or reporting (-1) if no path exists), the removed edge is restored for the next query.

Your task is to output the shortest path cost for every query under these conditions.

inputFormat

The input is given as follows:\n\n- The first line contains an integer $n$, the size of the grid.\n- The next $n$ lines each contain $n-1$ integers. The $j$-th integer in the $i$-th line is $ea_{i,j}$, the weight of the edge from $(i,j)$ to $(i,j+1)$.\n- The following $n-1$ lines each contain $n$ integers. The $j$-th integer in the $i$-th line is $eb_{i,j}$, the weight of the edge from $(i,j)$ to $(i+1,j)$.\n- The next line contains an integer $q$, the number of queries.\n- Each of the next $q$ lines contains a character and two integers: the character is either 'R' or 'D', indicating whether a rightward (horizontal) or downward (vertical) edge is to be temporarily removed, and the two integers $x$ and $y$ denote the starting coordinates of the edge to be removed.

outputFormat

For each query, output the shortest path cost from $(1,1)$ to $(n,n)$ after the specified edge is removed. If there is no valid path, output (-1).

sample

3
1 2
3 4
5 6
7 8 9
10 11 12
2
R 1 1
D 2 2

20
20