[BeiJing2011]神秘好人

有一位神秘好人正在与 Bdcxq 玩一个游戏。如果 Bdcxq 能够成功完成游戏，就会得到一件礼物。

游戏在一个梯子形的带权无向图上进行。图中共有 $2N$ 个点，分为上下两层，每层各有 $N$ 个点。上层各点从左到右依次编号为 $1,3,\ldots,2N-1$，下层各点从左到右依次编号为 $2,4,\ldots,2N$。每层相邻的两个点之间均有一条边，同一列的上下两个点之间也有一条边。

神秘好人会进行以下两类操作：

• 修改某一条边的权值；
• 询问从一个点到另一个点所经过边的权值之和的最小值。

如果 Bdcxq 能够回答所有询问，就可以完成游戏。请编写程序帮助他完成这个游戏。

输入格式

第一行包含一个整数 $N$，表示梯子形图的每层有 $N$ 个点，图中共有 $2N$ 个点。

接下来输入三行：

• 第一行包含 $N-1$ 个整数，依次表示上层相邻两点之间的初始边权；
• 第二行包含 $N$ 个整数，依次表示每一列上下两点之间的初始边权；
• 第三行包含 $N-1$ 个整数，依次表示下层相邻两点之间的初始边权。

接下来一行包含一个整数 $M$，表示操作次数。

随后输入 $M$ 行，每行描述一次操作：

• 若行首整数为 $0$，表示修改操作。接下来输入三个整数 $A_i,B_i,C_i$。其中，$A_i$ 为 $0,1,2$ 时，分别表示上层边、中间边和下层边；$B_i$ 表示该类边从左向右数的第 $B_i$ 条；$C_i$ 表示将该边的权值修改为 $C_i$。
• 若行首整数为 $1$，表示询问操作。接下来输入两个整数 $A_i,B_i$，询问从点 $A_i$ 到点 $B_i$ 的最短路径长度。

输出格式

对于每次询问操作，输出一行一个整数，表示两点之间的最短路径长度。

样例输入

4

1 2 7

1 3 4 8

4 5 6

5

1 1 2

1 2 6

1 1 8

0 1 3 1

1 1 8

样例输出

1
8
13
10

数据范围

• $1\le N,M\le 10^5$；
• 所有初始边权及修改后的边权均满足 $0\le w\le 10^6$；
• 对于询问操作，$1\le A_i,B_i\le 2N$；
• 对于修改操作，当 $A_i=0$ 或 $A_i=2$ 时，$1\le B_i<N$；
• 对于修改操作，当 $A_i=1$ 时，$1\le B_i\le N$。

来源与许可

本题为 Beijing 2011 试题「神秘好人」，题面与测试数据整理自 BZOJ。

样例 1

输入

4

1 2 7

1 3 4 8

4 5 6

5

1 1 2

1 2 6

1 1 8

0 1 3 1

1 1 8

输出

1
8
13
10