C. 无法逃离的梦境
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

在做出了正确的选择后，托姆渐渐感觉自己的意识离开了虚无之海。然而，当托姆以为自己即将醒来时，他发现他并没有回到现实，而是坠入了更深的一层梦境。这一次，他来到了一个由 hsq 精心设计的迷宫。

这个迷宫中共有 $$$n$$$ 个房间，编号为 $$$1, 2, \ldots, n$$$。每个房间中都有一条无法改变的单向通道：如果托姆当前位于房间 $$$i$$$，那么在 hsq 对他进行一次操控后，他必然会沿着通道进入房间 $$$p_i$$$。

除了所在的房间，托姆还拥有一种梦境状态。梦境状态共有 $$$c$$$ 种，编号为 $$$0, 1, \ldots, c-1$$$。

在每一次操控时，若托姆当前位于房间 $$$i$$$，且当前的梦境状态为 $$$a$$$，hsq 可以将其梦境状态切换为任意状态 $$$b$$$（$$$b$$$ 可以与 $$$a$$$ 相同），并为此付出 $$$w_i(a, b)$$$ 的代价。这个代价可能为负数，表示这次操控反而让 hsq 获得了某种收益。在状态切换完成之后，托姆会立刻沿着房间 $$$i$$$ 的通道进入房间 $$$p_i$$$。

现在有 $$$q$$$ 次询问。每次询问给出四个整数 $$$x, k, s, t$$$，表示托姆初始位于房间 $$$x$$$，初始梦境状态为 $$$s$$$。hsq 需要恰好操控托姆 $$$k$$$ 次，并希望在 $$$k$$$ 次操控结束后，托姆的梦境状态恰好为 $$$t$$$。

请你求出，对于每次询问，hsq 达成目标所需要付出的最小总代价。

Input

第一行包含三个整数 $$$n,c,q$$$ ($$$1 \le n,q \le 10^5$$$，$$$2 \le c \le 5$$$)，分别表示迷宫中的房间数量，梦境状态数量和询问次数。

第二行包含 $$$n$$$ 个整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$)。其中 $$$p_i$$$ 表示如果托姆当前位于房间 $$$i$$$，那么 hsq 操控他一次之后，托姆会进入房间 $$$p_i$$$。

接下来输入 $$$n$$$ 个代价矩阵。

对于每个房间 $$$i$$$ ($$$1 \le i \le n$$$)，输入 $$$c$$$ 行，每行包含 $$$c$$$ 个整数。

第 $$$a+1$$$ 行第 $$$b+1$$$ 个整数表示 $$$w_i(a, b)$$$ ($$$0 \le a,b \lt c$$$，$$$-10^9 \le w_i(a, b) \le 10^9$$$)，即当托姆位于房间 $$$i$$$，且当前梦境状态为 $$$a$$$ 时，hsq 将他的梦境状态切换为 $$$b$$$ 所需付出的代价。

接下来 $$$q$$$ 行，每行包含四个整数 $$$x,k,s,t$$$ ($$$1 \le x \le n$$$，$$$1 \le k \le 10^9$$$，$$$0 \le s,t \lt c$$$)，表示一次询问。

Output

对于每次询问，输出一行一个整数，表示 hsq 恰好操控托姆 $$$k$$$ 次，并使他的最终梦境状态为 $$$t$$$ 时，需要付出的最小总代价。

Example
Input
3 2 3
2 3 2
0 3
-2 1
4 -1
-4 0
1 5
3 -3
1 1 0 1
1 2 0 0
2 3 1 0
Output
3
-1
-7
Note

在样例中，共有 $$$3$$$ 个房间和 $$$2$$$ 种梦境状态。

房间中的通道为：

$$$1 \to 2$$$，$$$2 \to 3$$$，$$$3 \to 2$$$。

对于第一次询问，$$$x=1,k=1,s=0,t=1$$$。

托姆初始位于房间 $$$1$$$，梦境状态为 $$$0$$$。hsq 只需要操控他一次，并让他的梦境状态变为 $$$1$$$。

此时代价为 $$$w_1(0, 1)=3$$$，所以答案为 $$$3$$$。

对于第二次询问，$$$x=1,k=2,s=0,t=0$$$。

托姆经过的房间依次为：

$$$1 \to 2 \to 3$$$。

一种最优方案为：

第一次操控，在房间 $$$1$$$，将梦境状态从 $$$0$$$ 切换为 $$$1$$$，代价为 $$$w_1(0, 1)=3$$$；

第二次操控，在房间 $$$2$$$，将梦境状态从 $$$1$$$ 切换为 $$$0$$$，代价为 $$$w_2(1, 0)=-4$$$。

总代价为 $$$3+(-4)=-1$$$，所以答案为 $$$-1$$$。