---

C2. 调整演示（困难版本）

时间限制：每个测试 $5$ 秒
内存限制：$256$ MB

这是本题的困难版本。在两个版本中，$q$ 的约束和时间限制不同。在此版本中，$0 \le q \le 2 \cdot 10^5$。只有解决了所有版本的题目，你才能进行 Hack。

---

题目描述

一个由 $n$ 名成员组成的团队（编号从 $1$ 到 $n$）将在一个大型会议上进行幻灯片演示。幻灯片共有 $m$ 张。

有一个长度为 $n$ 的数组 $a$。初始时，成员们按照 $a_1, a_2, \dots, a_n$ 的顺序从前到后站成一排。幻灯片将按照从第 $1$ 张到第 $m$ 张的顺序依次演示。每个部分将由队伍最前面的成员来演示。每张幻灯片演示完毕后，你可以将当前队伍最前面的成员移动到队伍中的任意位置（其余成员的相对顺序保持不变）。例如，假设队伍为 $[3,1,2,4]$。在成员 $3$ 演示完当前幻灯片后，你可以将队伍变为 $[3,1,2,4]$、$[1,3,2,4]$、$[1,2,3,4]$ 或 $[1,2,4,3]$。

还有一个长度为 $m$ 的数组 $b$。如果存在一种移动方式，使得对于所有 $i$（$1 \le i \le m$），都能让成员 $b_i$ 演示幻灯片 $i$，则称该演示是好的。

然而，你烦人的老板希望对数组 $b$ 进行 $q$ 次更新。在第 $i$ 次更新中，他会选择一个幻灯片 $s_i$ 和一个成员 $t_i$，并将 $b_{s_i}$ 设置为 $t_i$。注意这些更新是持久性的，即对数组 $b$ 的修改会应用于后续的更新处理中。

对于数组 $b$ 的 $q+1$ 种状态（初始状态以及每次更新后的状态），分别判断演示是否是好的。

---

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, m \le 2 \cdot 10^5$，$0 \le q \le 2 \cdot 10^5$），分别表示成员数量和幻灯片数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示成员从前往后的初始顺序。保证 $a$ 中 $1$ 到 $n$ 的每个整数恰好出现一次。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \le b_i \le n$），表示应该演示每个幻灯片的成员。

接下来的 $q$ 行，每行包含两个整数 $s_i$ 和 $t_i$（$1 \le s_i \le m$，$1 \le t_i \le n$），表示一次更新的参数。

保证所有测试用例的 $n$ 之和、$m$ 之和以及 $q$ 之和分别不超过 $2 \cdot 10^5$。

---

输出格式

对于每个测试用例，输出 $q+1$ 行，对应数组 $b$ 的 $q+1$ 种状态（初始状态和每次更新后）。如果演示是好的，输出 "YA"，否则输出 "TIDAK"。

你可以以任意大小写输出答案（大小写不敏感）。例如，字符串 "yA"、"Ya"、"ya" 和 "YA" 都会被识别为肯定回答。

---

示例

输入

3
4 2 2
1 2 3 4
1 1
1 2
1 1
3 6 2
1 2 3
1 1 2 3 3 2
3 3
2 2
4 6 2
3 1 4 2
3 1 1 2 3 4
3 4
4 2

输出

YA
TIDAK
YA
YA
TIDAK
YA
TIDAK
YA
YA

---

样例解释

第一个测试用例：初始时，两张幻灯片都由成员 $1$ 演示，成员 $1$ 已经在队伍最前面，因此不需要移动成员。之后，设置 $b_1 := 2$，现在幻灯片 $1$ 必须由成员 $2$ 演示，但这是不可能的，因为成员 $1$ 会先演示幻灯片 $1$。然后，设置 $b_1 = 1$，此时 $b$ 与初始 $b$ 相同，使得演示可行。