CF2036E.Reverse the Rivers

一群古代贤者密谋，为了自身的便利，决定改道河流，这让世界濒临危机。但在实施宏伟计划之前，他们决定仔细思考策略——贤者们总是如此。

有 $n$ 个国家，每个国家恰好有 $k$ 个地区。对于第 $i$ 个国家的第 $j$ 个地区，他们计算出了一个值 $a_{i,j}$，表示该地区的水量。

贤者们打算在所有 $1 \leq i \leq (n-1)$ 和所有 $1 \leq j \leq k$ 的情况下，在第 $i$ 个国家的第 $j$ 个地区与第 $(i+1)$ 个国家的第 $j$ 个地区之间修建渠道。

由于所有 $n$ 个国家都位于一个大斜坡上，水会流向编号最大的国家。根据贤者们的预测，在渠道系统建成后，第 $i$ 个国家的第 $j$ 个地区的新值将变为 $b_{i,j} = a_{1,j} | a_{2,j} | \dots | a_{i,j}$，其中 $|$ 表示按位“或”运算。

在水重新分配后，贤者们希望选择最适合居住的国家，因此他们会向你提出 $q$ 个查询。

每个查询包含 $m$ 个要求。

每个要求包含三个参数：地区编号 $r$，符号 $o$（可以是“$<$”或“$>$”），以及数值 $c$。如果 $o = "<"$，那么你选择的国家的第 $r$ 个地区的新值必须严格小于 $c$；如果 $o = ">"$，则必须严格大于 $c$。

换句话说，所选的国家 $i$ 必须满足所有 $m$ 个要求。如果当前要求 $o = "<"$，则必须有 $b_{i,r} < c$；如果 $o = ">"$，则必须有 $b_{i,r} > c$。

对于每个查询，你需要输出一个整数——满足条件的最小国家编号。如果有多个国家满足条件，输出编号最小的那个。如果没有满足条件的国家，输出 $-1$。

第一行包含三个整数 $n$、$k$ 和 $q$（$1 \leq n, k, q \leq 10^5$），分别表示国家数、地区数和查询数。

接下来有 $n$ 行，每行包含 $k$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,k}$（$1 \leq a_{i,j} \leq 10^9$），表示第 $i$ 个国家各地区的水量。

然后描述 $q$ 个查询。

每个查询的第一行包含一个整数 $m$（$1 \leq m \leq 10^5$），表示要求的数量。

接下来 $m$ 行，每行包含一个整数 $r$、一个字符 $o$ 和一个整数 $c$（$1 \leq r \leq k$，$0 \leq c \leq 2 \cdot 10^9$），其中 $r$ 和 $c$ 分别为地区编号和值，$o$ 为“$<$”或“$>$”中的一个符号。

保证 $n \cdot k \leq 10^5$，所有查询中 $m$ 的总和也不超过 $10^5$。

对于每个查询，输出一个整数，表示满足条件的最小国家编号。如果没有满足条件的国家，输出 $-1$。

在示例中，各地区的初始值如下：

$1$ $3$ $5$ $9$
$4$ $6$ $5$ $3$
$2$ $1$ $2$ $7$

渠道建成后，新值如下：

$1$ $3$ $5$ $9$
$1|4$ $3|6$ $5|5$ $9|3$
$1|4|2$ $3|6|1$ $5|5|2$ $9|3|7$

$\downarrow$

$1$ $3$ $5$ $9$
$5$ $7$ $5$ $11$
$7$ $7$ $7$ $15$

在第一个查询中，需要输出最小的国家编号（即行号），使得水重新分配后，第一个地区（即列）新值大于 $4$ 且小于 $6$，第二个地区新值小于 $8$。只有编号为 $2$ 的国家满足要求。

在第二个查询中，没有国家满足指定要求。

在第三个查询中，只有编号为 $3$ 的国家合适。

在第四个查询中，所有三个国家都满足条件，因此答案是最小编号 $1$。

由 ChatGPT 4.1 翻译