1347: 小朋友的身高

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:4 Solved:1

Description

卷王有 n 个朋友,最初,第 i 位朋友的身高为 ai

时光飞逝,一转眼就过去了 m 年。在第 i 年第 j 位朋友的身高增长了 bi,j

卷王有 q 次询问,每一次询问包含 3 个数 x,y,z,表示询问过了 x 年后第 y 位朋友和第 z 位朋友的身高差(即第 y 位朋友 x 年后的身高减第 z 位朋友 x 年后的身高)。特别的,若 x=0,表示询问最初时第 y 位朋友和第 z 位朋友的身高差

Input

读入数据共 m+q+2 行。

第一行三个正整数 n,m,q,含义见题意。
接下来一行 n 个正整数 ai,表示小朋友们最初的身高。
接下来 m 行,每行 n 个正整数,表示 bi,j
最后 q 行,每行 3 个正整数 x,y,z,表示询问过了 x 年后第 y 个小朋友和第 z 个小朋友的身高差

Output

输出共 q 行。对于每组询问,输出对应的身高差。

Sample Input Copy

3 2 2
1 2 3
2 2 2
4 3 1
1 1 3
2 2 3

Sample Output Copy

-2
1

HINT

样例 1 解释

1 年后,第 1 位朋友身高为 3,第 3 位朋友身高为 5,身高差为 35=2
2 年后,第 2 位朋友身高为 7,第 3 位朋友身高为 6,身高差为 76=1

数据规模与约定

  • 对于 20% 的数据,满足所有 bi,j 都相等;
  • 对于 50% 的数据,满足 1n,m,q3001ai1051bi,j105
  • 对于 100% 的数据,满足 1n,m,q1030xm1y,zn1ai1091bi,j109