题目描述

<v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"> <v:stroke joinstyle="miter"></v:stroke> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0"></v:f> <v:f eqn="sum @0 1 0"></v:f> <v:f eqn="sum 0 0 @1"></v:f> <v:f eqn="prod @2 1 2"></v:f> <v:f eqn="prod @3 21600 pixelWidth"></v:f> <v:f eqn="prod @3 21600 pixelHeight"></v:f> <v:f eqn="sum @0 0 1"></v:f> <v:f eqn="prod @6 1 2"></v:f> <v:f eqn="prod @7 21600 pixelWidth"></v:f> <v:f eqn="sum @8 21600 0"></v:f> <v:f eqn="prod @7 21600 pixelHeight"></v:f> <v:f eqn="sum @10 21600 0"></v:f> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"></v:path> <o:lock v:ext="edit" aspectratio="t"></o:lock> </v:shapetype><v:shape id="_x0000_s1026" type="#_x0000_t75" style="margin-top: 9.75pt; z-index: 1; left: 0px; margin-left: -18pt; width: 473.4pt; position: absolute; height: 132.9pt; text-align: left"> <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image001.png" o:title=""></v:imagedata> <w:wrap type="square"></w:wrap> </v:shape>神秘好人一开始会告诉Bdcxq每条边的权值。 <o:p></o:p>

       然后神秘好人会做这样的事情： <o:p></o:p>

1．神秘好人会修改某条边的权值； <o:p></o:p>

2．神秘老人会问你从一个点走到另一个点所需经过边权和最小的权值和。 <o:p></o:p>

<o:p>   </o:p>

如果Bdcxq一直能答对问题，那么他就完成了游戏，也能得到礼物。 <o:p></o:p>

现在他请你编一个程序来帮他完成游戏。 <o:p></o:p>

输入格式

输入文件的第一行包含一个整数N，表示梯子总共含有2N个点，第一行从左至右分别标号为1，3，……，2N-1，第二行从左至右分别标号为2，4，……，2N。 <o:p></o:p>

接下来有三行。 <o:p></o:p>

第一行有N-1个整数，依次表示上层相邻两点间的初始权值。 <o:p></o:p>

第二行有N个整数，依次表示两层之间的边的初始权值。 <o:p></o:p>

第三行有N-1个整数，依次表示下层相邻两点间的初始权值。 <o:p></o:p>

接下来一行包含一个整数M，表示神秘好人在游戏开始后的操作。 <o:p></o:p>

接下来M行： <o:p></o:p>

每行第一个整数若是0，表示这是一个修改操作，接下来会有3个整数A_i，B_i，C_i，A_i为0，1，2分别代表这条边属于上层边，中间边和下层边，B_i表示这条边是这一层从左向右数的第B_i条边，C_i表示要修改成的边权。 <o:p></o:p>

每行第一个整数若是1，表示这是一个询问操作，接下来会有2个整数A_i，B_i，询问A_i到B_i的经过边的最小权值和。 <o:p></o:p>

<o:p>   </o:p>

输出格式

对于每次询问操作你需要输出一行包含一个整数，为最小的边权值和。 <o:p></o:p>

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

数据范围与约定

100%的数据满足N，M≤ 100000。