E2. 墨西哥比索（困难版本）

时间限制：每个测试 $2$ 秒
内存限制：$512$ MB

这是本题的困难版本。在此版本中，保证 $q \le 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$ 表示按位异或运算。

有一个 $n$ 行 $m$ 列的部分填充整数网格 $G$，其中只有 $k$ 个单元格被填充。Polycarp 想知道有多少种方式可以为未填充的单元格分配整数，使得网格变得美丽。

然而，Monocarp 认为这个问题太简单了。因此，他将执行 $q$ 次更新。在每次更新中，他会选择一个未填充的单元格并为其分配一个整数。注意这些更新是持久性的，即对网格所做的更改将应用于后续更新的处理中。

对于网格的 $q+1$ 种状态（初始状态以及每次查询后的状态），确定 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 \le 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$ 取模的结果。

---

示例

输入

3
3 3 8 1
2 1 6
3 2 12
1 2 6
2 2 0
1 3 10
1 1 0
2 3 12
3 1 10
3 3 1
2 5 2 0
1 1 10
1 2 30
2 5 0 2
1 1 10
1 2 30

输出

1
0
489373567
651321892
769740174
489373567

---

样例解释

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

可以证明，单元格 $(3,3)$ 的唯一有效值是 $0$，因此第一个答案为 $1$。对于第二次查询，网格不满足条件，因此答案为 $0$。