题目描述

有一个神秘好人跟Bdcxq玩一个游戏，如果Bdcxq成功完成了这个游戏，那么他将会得到一件礼物。 这个游戏是这样的： 有一个梯子形的图如下，每条边都有一个权值。 </v:formulas><o:lock v:ext="edit" aspectratio="t"></o:lock></v:shapetype><w:wrap type="square"></w:wrap></v:shape>神秘好人一开始会告诉 Bdcxq 每条边的权值。 **       ** 然后神秘好人会做这样的事情： 1． 神秘好人会修改某条边的权值； 2． 神秘老人会问你从一个点走到另一个点所需经过边权和最小的权值和。 ** ** 如果 Bdcxq 一直能答对问题，那么他就完成了游戏，也能得到礼物。 现在他请你编一个程序来帮他完成游戏。

输入格式

输入文件的第一行包含一个整数 N ，表示梯子总共含有 2N 个点，第一行从左至右分别标号为 1 ， 3 ，……， 2N-1 ，第二行从左至右分别标号为 2 ， 4 ，……， 2N 。 接下来有三行。 第一行有 N-1 个整数，依次表示上层相邻两点间的初始权值。 第二行有 N 个整数，依次表示两层之间的边的初始权值。 第三行有 N-1 个整数，依次表示下层相邻两点间的初始权值。 接下来一行包含一个整数 M ，表示神秘好人在游戏开始后的操作。 接下来 M 行： 每行第一个整数若是 0 ，表示这是一个修改操作，接下来会有 3 个整数 A_{i} ， B_{i} ， C_{i} ， A_{i} 为 0 ， 1 ， 2 分别代表这条边属于上层边，中间边和下层边， B_{i} 表示这条边是这一层从左向右数的第 B_{i} 条边， C_{i} 表示要修改成的边权。 每行第一个整数若是 1 ，表示这是一个询问操作，接下来会有 2 个整数 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

 


 

 

提示

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

题目来源

Day1