#P18102. Fresh Cartridges

Fresh Cartridges

Fresh Cartridges

机器人位于一个 nn 维循环竞技场中,每一维坐标都是模 p=998244353p=998244353 的剩余类。

每盒弹药中装有一个指令:由 nn 个模 pp 的数构成的位移向量。使用一次弹药,就会使机器人按该向量移动,所有坐标均对 pp 取模。

一个遥控器恰好能装入 nn 盒弹药。如果只使用装入的弹药,且每盒可以使用任意多次,机器人就能从任意位置到达任意其他位置,我们称这个遥控器是通用的。

仓库中共有 mm 盒弹药,第 ii 盒的位移向量为 viv_i。

接下来有 qq 份相互独立的检查报告。第 jj 份报告中,只有下标位于 [lj,rj][l_j,r_j] 的弹药没有过期,可以免费取用;仓库中的其他弹药都已经过期,禁止使用。

对于每份报告,你还可以制造任意多盒新弹药。每盒花费1枚硬币,位移向量可以任意选择,也允许与已有向量相同。新制造的弹药不会保留到其他报告中。

对于每份报告,求组装两个通用遥控器最少需要花费多少枚硬币。**每盒弹药只能使用一次,并且只能装入其中一个遥控器。**不同的弹药即使向量相同,仍然是不同的盒子。

输入格式

第一行一个整数 TT(1≤T≤10001\le T\le1000),表示测试组数。

每组数据第一行包含三个整数 n,m,qn,m,q,满足

1≤n≤150,1≤m,q≤3×105.1\le n\le150,\qquad1\le m,q\le3\times10^5.

接下来 mm 行,每行 nn 个整数 vi,1,…,vi,nv_{i,1},\ldots,v_{i,n},表示第 ii 盒弹药的位移向量,满足 0≤vi,k<p0\le v_{i,k}<p。

接下来 qq 行,每行两个整数 lj,rjl_j,r_j,满足 1≤lj≤rj≤m1\le l_j\le r_j\le m。

保证所有测试组的 ∑(nm)≤3×105\sum(nm)\le3\times10^5,且 ∑q≤3×105\sum q\le3\times10^5。

输出格式

按输入报告的顺序,对每份报告输出一行一个整数,表示最少花费。

样例 1

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

在一维情形下,一个非零向量就能组成一台通用遥控器。零向量没有作用;若只有一盒非零弹药,还需为另一台制造一盒。

样例 2

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

即使取到全部四盒,也只有一盒提供第一坐标方向,所以仍需至少制造一盒;不能把这盒已有弹药同时装进两台遥控器。