P17598 「RiOI-8」二階堂 ヒロ

**请注意本题不同寻常的时空限制。** 

希罗最信奉的就是正确。 这个世界上有 $n$ 种元素。希罗喜欢秩序，于是给它们标号为 $0,1,2,\cdots,n-1$。 有些事物注定无法共存，因为一旦共存，便会成为一对矛盾，一对不正确的存在。希罗的评判标准可表示为大小为 $n\times n$ 的 $0/1$ 矩阵 $F$，下标从 $0$ 开始。有些事物生来便是不正确，所以**不保证** $F_{i,i}=0$。矛盾亦有攻受之分，所以**不一定有** $F_{i,j}=F_{j,i}$。 给定长度为 $n$ 的序列 $a_i$，下标从 $0$ 开始。保证 $0\le a_i

样例采用如下输入格式： 第一行两个正整数 $n,q$。 接下来一行 $n$ 个非负整数表示 $a_i$。 接下来 $n$ 行，每行一个长度为 $n$ 的 $01$ 串，第 $i$ 行第 $j$ 个字符表示 $F_{i,j}$。 接下来 $q$ 行，每行两个非负整数 $l_i,r_i$，表示一次询问。

样例采用如下输出格式： 共 $q$ 行，每行一个非负整数，表示答案。

**请重视常数因子对程序效率的影响**。 由于评测机波动极大，如果你有充足的理由认为你的代码可以通过，尝试多交几次。