在 Pigeland 有 $n$ 所大学，编号为 $1$ 到 $n$。每年都有若干排名机构发布这些大学的排名。今年共有 $k$ 个排名列表，每个列表都是 $1$ 到 $n$ 的一个排列，代表这些大学的排名。在每个排名中，大学在排列中越靠前，其排名就越好。

Supigar 是一名想在 Pigeland 申请博士学位的四年级学生，他有自己的一套方法来综合评估这 $n$ 所大学。他认为大学 $x$ 优于另一所大学 $y$，当且仅当：

• 在至少一个列表中，$x$ 的排名优于 $y$，或者
• 在至少一个列表中，$x$ 的排名优于 $z$ ($z \neq x, z \neq y$)，且 $z$ 优于 $y$。

显然，根据这个定义，可能存在某些大学对 $x$ 和 $y$ ($x < y$)，使得 $x$ 优于 $y$ 的同时 $y$ 也优于 $x$。Supigar 将这样的对称为“模糊对”（fuzzy）。

Supigar 有 $q$ 个询问，第 $i$ 个询问由三个整数 $id_i, l_i$ 和 $r_i$ ($l_i \le r_i$) 表示。对于每个询问，他会考虑第 $id_i$ 个排名列表，以及该列表中处于第 $l_i$ 位到第 $r_i$ 位（包含两端）之间的所有大学。他想知道，在这些大学中，有多少对是模糊对。注意，模糊对的定义需要考虑所有 $k$ 个排名列表中的优劣关系。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 2 \times 10^5$)，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $n, k$ 和 $q$ ($1 \le n, k, q \le 2 \times 10^5, 1 \le n \times k \le 2 \times 10^5$)，分别表示大学数量、排名列表数量和询问数量。

接下来的 $k$ 行，第 $i$ 行包含 $n$ 个不同的整数 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n$)，表示第 $i$ 个排名列表。

接下来的 $q$ 行，第 $i$ 行包含三个整数 $id'_i, l'_i$ 和 $r'_i$ ($0 \le id'_i < k, 0 \le l'_i, r'_i < n$)，表示第 $i$ 个询问的加密索引和查询范围。

• $id_i$ 的真实值等于 $((id'_i + v_{i-1}) \pmod k) + 1$。
• $l_i$ 的真实值等于 $((l'_i + v_{i-1}) \pmod n) + 1$。
• $r_i$ 的真实值等于 $((r'_i + v_{i-1}) \pmod n) + 1$。

其中 $v_{i-1}$ 是第 $(i-1)$ 个询问的答案。特别地，定义 $v_0 = 0$。通过加密的询问，你必须在处理下一个询问之前计算出当前询问的答案。保证解码后 $1 \le id_i \le k$ 且 $1 \le l_i \le r_i \le n$。

同时保证所有测试数据的 $n \times k$ 之和以及 $q$ 之和均不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出 $q$ 行。每行包含一个整数，表示对应询问的模糊对数量。

样例

样例输入 1

2
5 2 2
1 2 3 4 5
5 4 3 2 1
1 0 2
1 2 1
5 3 3
1 2 3 4 5
1 3 2 4 5
1 2 3 5 4
0 0 2
0 2 3
1 0 3

样例输出 1

3
10
1
1
2

说明

对于第一个样例测试数据，两个解码后的询问分别为 $2\ 1\ 3$ 和 $1\ 1\ 5$。

对于第二个样例测试数据，三个解码后的询问分别为 $1\ 1\ 3$、$2\ 4\ 5$ 和 $3\ 2\ 5$。