题目描述

城市中有 $N\times M$ 个车站。车站按 $N$ 个同心圆排列，每个圆上有 $M$ 个车站，记作 $(i,j)$：

• $0\le i<N$ 表示圆环编号；
• $0\le j<M$ 表示圆环上的位置。

第 $i$ 个圆环上的相邻车站首尾相连，走一条环向边需要 $S_i$ 分钟。

相同位置 $j$ 上、相邻圆环 $i$ 与 $i+1$ 之间也有双向边，耗时为 $T_i$。最内圈和最外圈之间没有径向边。

给出 $Q$ 个询问。每个询问给出两个车站 $(A,B)$ 和 $(C,D)$，求两站之间的最短时间。

公共交通网络示意图

输入格式

第一行包含三个整数 $N,M,Q$。

第二行包含 $N$ 个整数 $S_0,S_1,\ldots,S_{N-1}$。

第三行包含 $N-1$ 个整数 $T_0,T_1,\ldots,T_{N-2}$。

接下来 $Q$ 行，每行包含四个整数 $A,B,C,D$。

输出格式

对每个询问输出一行最短时间。

数据范围

• $3\le N,M\le100000$；
• $1\le Q\le200000$；
• $1\le S_i,T_i\le10^9$；
• 两个询问端点不同。