暂无测试数据。

X 国的地图可以被看作一个两行 $n$ 列的网格状图。现在 X 国需要修建铁路，然而该国的国王非常小气，他只想保证位于某两列之间的所有城市互相可以到达就行了，在此基础上，他希望所花费的代价最小。

铁路可以建在任何两个相邻的点之间，使他们可以互相到达。可以作为工作人员，你已经整理出了为每一对相邻城市架设铁路所需要的花费。你需要准备好回答国王如下形式的问题。

对于 $(i,j)$：当前情况下，使第 $i$ 列到第 $j$ 列之间的所有城市连通的最小代价是多少（列下标从 $1$ 开始）？注意不能用其他列的城市。

然而你还有更大的困难，随着时间变化，使用某些边作为铁路的代价会发生改变，你必须有效率地处理这些变化。

输入格式

第一行两个正整数 $n,m$，表示该国有 $2$ 行 $n$ 列以及 $m$ 个询问或者操作。

第二行 $3n-2$ 个数，前 $n-1$ 个数依次表示在第一行的 $n-1$ 条边上修建铁路的代价。

接下来 $n-1$ 个数，依次表示在第二行的 $n-1$ 条边上修建铁路的代价。

最后 $n$ 个数，依次表示在第 $1$ 列到第 $n$ 列的边上修建铁路的代价。

接下来 $m$ 行的输入具有如下形式，$K,S,T$，其中

1. 若 $K=1$，则表示询问当前状态下，使所有第 $S$ 列到第 $T$ 列之间的城市连通需要的最小代价。

2. 若 $K=2$，则表示位于第 $1$ 行第 $S$ 列的点到第 $1$ 行第 $S+1$ 列的点之间的边上修建铁路的代价变为 $T$。

3. 若 $K=3$，则表示位于第 $2$ 行第 $S$ 列的点和第 $2$ 行第 $S+1$ 列的点之间的边上修建铁路的代价变为 $T$。

4. 若 $K=4$，则表示第 $S$ 列的边上修建铁路的代价变为 $T$。

输出格式

依次对每个询问，用一行输出相应的答案。

数据范围与约定

对于 $30\%$ 的数据：$n,m\le 2000$。

另有 $30\%$ 的数据：所有竖边的代价为 $0$ 且永不改变。

对于全部数据：$n,m \le 10^5$。

所有输入和输出数据保证合法，且不超过 $2^{31}-1$。

4 14
2 3 4 3 1 1 1 5 4 7
1 1 2
1 2 3
1 1 3
1 2 4
2 1 5
1 1 4
4 2 1
1 1 3
1 2 3
1 2 4
3 3 100
1 3 4
1 2 4
1 1 4

6
8
10
13
17
9
5
10
15
16
20