Minimum Spanning Tree in a 2×N Grid

In a certain country there are \(2N\) cities arranged in a grid with 2 rows and \(N\) columns. The cities are labeled by their row and column indices, where the rows are 1 and 2 and the columns are from 1 to \(N\). For each column \(i\) (\(1 \le i \le N\)) there is a vertical road connecting the city in row 1 and column \(i\) with a cost \(v_i\). For every two consecutive columns \(i\) and \(i+1\) (\(1 \le i < N\)), there are two horizontal roads: one connecting the cities in row 1 (with cost \(h_{1,i}\)) and one connecting the cities in row 2 (with cost \(h_{2,i}\)).

The government plans to improve tourism by selecting two columns \(L\) and \(R\) (with \(L \le R\)) and constructing a set of special roads among the cities in columns \(L, L+1, \dots, R\) so that all \(2(R-L+1)\) cities become connected via these roads. However, in order to reduce expenditure, exactly \(2(R-L+1)-1\) roads are constructed, which by definition forms a spanning tree on these cities.

You are given \(M\) operations. Each operation is one of the following two types:

• C x0 y0 x1 y1 w: The cost of the road connecting the city at row \(x_0\), column \(y_0\) and the city at row \(x_1\), column \(y_1\) is updated to \(w\). It is guaranteed that the two cities are adjacent, i.e. either \(x_0 \neq x_1\) (a vertical road) or \(x_0 = x_1\) and \(|y_0-y_1| = 1\) (a horizontal road).
• Q L R: If the government selects columns \(L\) and \(R\), output the minimum total cost to construct \(2(R-L+1)-1\) roads forming a spanning tree among the \(2(R-L+1)\) cities in these columns, using the current road costs.

The allowed roads are only those between two adjacent cities in the same row (horizontal) or the two cities in the same column (vertical). Initially the cost for each road is given implicitly; you may assume that the initial costs are provided as part of the input in a format described below.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space, where \(N\) is the number of columns and \(M\) is the number of operations.

The next line contains \(N\) integers: \(v_1, v_2, \dots, v_N\) representing the costs of the vertical roads for columns 1 to \(N\) respectively.

The following line contains \(N-1\) integers: \(h_{1,1}, h_{1,2}, \dots, h_{1,N-1}\) representing the costs of the horizontal roads in row 1 between columns \(i\) and \(i+1\) for \(i=1\) to \(N-1\).

The next line contains \(N-1\) integers: \(h_{2,1}, h_{2,2}, \dots, h_{2,N-1}\) representing the costs of the horizontal roads in row 2 between columns \(i\) and \(i+1\) for \(i=1\) to \(N-1\).

Each of the next \(M\) lines describes an operation. An operation is in one of the following two formats:

• C x0 y0 x1 y1 w — update the cost of the road between city \((x0, y0)\) and city \((x1, y1)\) to \(w\).
• Q L R — query the minimum cost to build a spanning tree on the cities in columns \(L\) to \(R\) (inclusive) using exactly \(2(R-L+1)-1\) roads.

Note that row indices are either 1 or 2 and column indices range from 1 to \(N\).

outputFormat

For each query operation, output a single line containing one integer: the minimum total cost of constructing the spanning tree for the selected subgrid.

sample

3 5
100 200 300
10 20
30 40
Q 1 1
C 1 1 2 1 50
Q 1 1
C 1 1 1 2 5
Q 1 2

100
50
65

</p>