CF2022E2.Billetes MX (Hard Version)

这是该问题的困难版本。在本版本中，保证 $q \leq 10^5$。只有在你解决了两个版本的问题后，才能进行 hack。

一个有 $p$ 行 $q$ 列的整数网格 $A$ 被称为美丽的，如果：

• 网格中的所有元素都是 $0$ 到 $2^{30}-1$ 之间的整数，并且
• 对于任意子矩阵，其四个角的值的异或和等于 $0$。形式化地说，对于任意四个整数 $i_1$、$i_2$、$j_1$、$j_2$（$1 \le i_1 < i_2 \le p$；$1 \le j_1 < j_2 \le q$），都有 $A_{i_1, j_1} \oplus A_{i_1, j_2} \oplus A_{i_2, j_1} \oplus A_{i_2, j_2} = 0$，其中 $\oplus$ 表示按位异或运算。

现在有一个部分填充的整数网格 $G$，它有 $n$ 行 $m$ 列，其中只有 $k$ 个格子被填充。Polycarp 想知道有多少种方法可以给未填充的格子赋值，使得整个网格是美丽的。

然而，Monocarp 认为这个问题太简单了。因此，他会对网格进行 $q$ 次更新。每次更新，他会选择一个未填充的格子并赋予一个整数。注意，这些更新是持久化的，也就是说，对网格的更改会影响后续的所有更新。

对于每个网格的状态（初始状态以及每次 $q$ 次更新后的状态），请你计算 Polycarp 可以给未填充格子赋值，使网格美丽的方案数。由于答案可能非常大，你只需要输出其对 $10^9+7$ 取模的结果。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。

每个测试用例的第一行包含四个整数 $n$、$m$、$k$ 和 $q$（$2 \le n, m \le 10^5$；$0 \le k, q \leq 10^5$）——表示行数、列数、已填充格子的数量和更新次数。

接下来的 $k$ 行，每行包含三个整数 $r$、$c$ 和 $v$（$1 \le r \le n, 1 \le c \le m$；$0 \le v < 2^{30}$），表示 $G_{r, c}$ 被赋值为 $v$。

接下来的 $q$ 行，每行包含三个整数 $r$、$c$ 和 $v$（$1 \le r \le n, 1 \le c \le m$；$0 \le v < 2^{30}$），表示 $G_{r, c}$ 被赋值为 $v$。

保证所有赋值的 $(r, c)$ 坐标都是不同的。

保证所有测试用例中 $n$、$m$、$k$ 和 $q$ 的总和分别不超过 $10^5$。

对于每个测试用例，输出 $q+1$ 行。第 $i$ 行输出第 $i$ 个网格状态下的答案，对 $10^9+7$ 取模。

在示例的第一个测试用例中，初始网格如下：

$0$ $6$ $10$ $6$ $0$ $12$ $10$ $12$ $?$

可以证明，格子 $(3, 3)$ 的唯一合法取值是 $0$，因此第一个答案是 $1$。对于第二个查询，网格不再满足条件，因此答案是 $0$。

由 ChatGPT 4.1 翻译