Description

A certain country has $2N$ cities. These $2N$ cities form a $2$-row, $N$-column grid. The government now has a tourism development plan: it needs to choose two columns $L$ and $R$ $(L \leq R)$, and build some dedicated roads so that among all $2(R-L+1)$ cities between these two columns (including these two columns), every city can reach any other of these $2(R-L+1)$ cities using only the dedicated roads.

A dedicated road can only be built between two cities in the same row and adjacent columns, or between the two cities in the same column, and building a road costs some amount.

Since the government wants to reduce expenses as much as possible, after choosing $L$ and $R$, it will build only $2(R-L+1)-1$ dedicated roads, so that these roads form a tree structure. Now you need to help the government write a program to complete this task.

Specifically, the task contains $M$ operations, each in one of the following formats:

1. C x0 y0 x1 y1 w: Because the situation between the city at row $x_0$, column $y_0$ and the city at row $x_1$, column $y_1$ has been re-evaluated, the cost to build a dedicated road between them becomes $w$.

2. Q L R: If the government chooses columns $L$ and $R$, ask for the minimum total expense.

Input Format

The first line contains two integers $N$ and $M$.

The second line contains $N-1$ integers. The $i$-th integer indicates the initial cost to build a dedicated road between the city at row $1$, column $i$ and the city at row $1$, column $i+1$.

The third line contains $N-1$ integers. The $i$-th integer indicates the initial cost to build a dedicated road between the city at row $2$, column $i$ and the city at row $2$, column $i+1$.

The fourth line contains $N$ integers. The $i$-th integer indicates the initial cost to build a dedicated road between the city at row $1$, column $i$ and the city at row $2$, column $i$.

The next $M$ lines each contain one operation.

Output Format

For each query operation, output one line containing the minimum expense you computed for the government.

3 3
1 2
2 1
3 1 2
Q 1 3
C 1 2 2 2 3
Q 2 3

7
5

Hint

For all testdata, $1 \leq N, M \leq 60000$, and at any time, the construction cost of any dedicated road does not exceed $10^4$.

Translated by ChatGPT 5