A country has $2N$ cities, which form a $2 \times N$ grid. The government has a tourism development plan that requires selecting two columns $L$ and $R$ ($L \le R$) and building several dedicated roads such that every city among the $2(R-L+1)$ cities in these columns (inclusive) can reach any other city in this set using only these dedicated roads. These dedicated roads can only be built between adjacent cities in the same row or between the two cities in the same column, and each road has a certain construction cost. Since the government wants to minimize expenses, it has decided that after selecting $L$ and $R$, it will build exactly $2(R-L+1)-1$ dedicated roads such that they form a tree structure. You need to help the government write a program to complete this task. Specifically, the task involves $M$ operations, each formatted as follows:

1. C x0 y0 x1 y1 w: Due to a re-evaluation of the situation between the city at row $x_0$, column $y_0$ and the city at row $x_1$, column $y_1$, the cost to build a dedicated road between them has become $w$.
2. Q L R: If the government selects columns $L$ and $R$, query the minimum cost for the government.

Input

The first line contains two integers $N$ and $M$. The second line contains $N-1$ integers, where the $i$-th integer represents 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, where the $i$-th integer represents 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, where the $i$-th integer represents 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 following $M$ lines each contain one operation.

Output

For each query operation, output one line representing the minimum cost calculated.

Examples

Input 1

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

Output 1

7
5

Constraints

For 40% of the data, $1 \le N, M \le 600$. For all data, $1 \le N, M \le 60000$, and the construction cost of any dedicated road at any time does not exceed $10^4$.