暂无测试数据。

蒜头君拥有一份蒜国的国家地图，他发现蒜国的城市布局非常奇怪，城市布局可以看作是一个两行 $n$ 列的网格状图（列下标从 $1$ 开始）。如今城市之间缺少互通的道路，现在蒜国的领导人想要请蒜头君为城市之间修建双向通行的道路的方案做出最优的规划。

由于资金的限制，蒜国领导人只想确保 在某两列之间修建一些双向通行的道路让这两列之间的所有城市能够相互到达 即可。蒜头君已经了解到蒜国每一对相邻城市之间修建道路的花费，所以蒜头君能够通过这些信息计算出实现领导人的目的的最少花费。

但是现在还有一个更大的困难，随着时间的变化，在某些相邻城市之间修建双向通信的道路的花费会发生改变，蒜头君需要在规划道路修建方案的时候及时处理这些变化。

由于蒜国领导人之间在选择某两列的时候发生了分歧，所以蒜国领导人会多次询问蒜头君保证第 $i\sim j$ 列的所有城市之间能够相互通行的最少花费是多少。

注：询问是遵循时间顺序的，随着时间的改变，某些相邻的城市之间修建道路的花费也会发生改变。蒜头君在规划修建方案的时候，不能涉及到除 $i\sim j$ 范围内的其他城市。

输入格式

第一行两个正整数 $n,m$，表示蒜国的城市布局为 $2$ 行 $n$ 列，蒜头君有 $m$ 个询问或修建道路花费的更新。

第二行 $3n-2$ 个数，前 $n-1$ 个数依次表示要修建第一行的 $n-1$ 条双向通行的道路的花费。接下来 $n-1$ 个数，依次表示要修建第二行的 $n-1$ 条双向通行的道路的花费。最后 $n$ 个数，第 $i$ 个数表示，第 $i$ 列中第一行到第二行两个城市之间修建双向通行的道路的花费。

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

1. 若 $K=1$，表示领导人一次询问，蒜头君需要计算第 $S\sim T$ 列之间的所有城市能够相互通行的最少花费。
2. 若 $K=2$，则表示修建位于第 $1$ 行第 $S$ 列的城市到第 $1$ 行第 $S+1$ 列的城市之间双向通行道路的花费变为 $T$。
3. 若 $K=3$，则表示修建位于第 $2$ 行第 $S$ 列的城市到第 $2$ 行第 $S+1$ 列的城市之间双向通行道路的花费变为 $T$。
4. 若 $K=4$，则表示修建位于第 $S$ 列的第一行到第二行两个城市之间双向通行的道路的花费变为 $T$。

输出格式

输出若干行，每行输出一个整数，第 $i$ 行输出的整数表示领导人第 $i$ 次询问时，蒜头君计算的最少花费。

数据范围

• 对于 $30\%$ 的数据：$1\leq n,m\le 2000$。
• 另有 $30\%$ 的数据：所有竖边的代价为 $0$ 且永不改变。
• 对于 $100\%$ 的数据：$1\leq 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