图腾
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在某款游戏中，地图被抽象成了一条长度为 n 的数轴。


初始时，数轴上有 m 个图腾，第 i 个图腾位置为 X_i，其拥有能量值 V_i。


每个整数点的能量 c_i 由该点 左侧最近 图腾的能量值 V_l 和 右侧最近 图腾的能量值V_r 共同决定：c_i = V_l\times V_r (若整数点上有图腾，那么该点的能量 c_i 为 0 )。


现在 charan 作为游戏的控制者，他会进行 q 次操作，操作仅有两种方式：



  • 1 x v - 在 x 的位置插入一个新的图腾，该图腾的能源值为 v (保证不会和已经存在的图腾重复)。

  • 2 l r - 输出\sum_{i=l}^r c_i。


保证第一个整数点和最后一个整数点初始时会有图腾存在。

输入描述:

第一行包含三个整数 n,m,q (2 \le m \le n \le 3 \times 10^5,1 \le q \le 3 \times 10^5)，分别表示 数轴长度、图腾数量、操作次数 。

第二行包含 m 个不同的整数 X_1, X_2, \ldots, X_m(1 = X_1 < X_2 <...< X_m = n)，X_i 表示第 i 个图腾所在的 位置。

第三行包含 m 个整数 V_1, V_2, \ldots, V_m(1 \le V_i \le 10^5)，表示第 
i 个图腾的 能源值 。

接下来的 q 行，每行包含三个整数。

第一个整数是 t ( 1\le t \le 2 )，表示 操作类型。
如果 t=1 ，那么接下来的两个整数是 x 和 v (2 \le x \le n - 1,1 \le v \le 10^5)，表示 第一类操作。
如果 t=2 ，那么接下来的两个整数是 l 和 r (1 \le l \le r \le n)，表示 第二类操作 。

输出描述:

对于每一个第二类操作，输出查询到的答案。

每个答案之间用换行间隔。
示例1

输入

复制 
8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8

输出

复制 
552
0
150

说明

保证至少有一个第二类操作。

对于样例进行解释：

初始时整数点的能量值及能量：



第一次查询区间 [2,5] 的能量 72+240×2 = 552。

第二次修改V_5 = 15 后图整数点的能量值及能量：


第三次查询区间 [5,5] 的能量 0

第四次查询区间 [7,8] 的能量150