地牢谜题：更高还是更低

Problem Description

在地牢谜题游戏 更高还是更低 中，初始有 $n$ 只血量不同烈焰人排列成一列，第 $i$ 只烈焰人是所有烈焰人中血量第 $p_i$ 小的。你需要按血量从低到高或从高到低的顺序（由谜题规则确定）击杀所有的烈焰人。 你有一把魔法弓，每次射击可以击杀不超过 $k$ 只相邻的烈焰人，你可以自由决定在同一次射击中烈焰人死亡的顺序。两只烈焰人是相邻的当且仅当它们之间的烈焰人都已经死亡。 你和你的同伴需要完成该地牢谜题 $m$ 次。作为一个队伍，你自然不需要独自解决谜题。在第 $i$ 次进行谜题游戏时，你的任务是击杀血量第 $l_i$ 小，第 $l_i+1$ 小，...，第 $r_i$ 小的烈焰人。 这意味着，在你开始任务之前，若谜题规则是按照血量从低到高击杀烈焰人，则血量第 $1, 2, \cdots, l_i - 1$ 小的烈焰人已经全部被队友击杀；若谜题规则是按照血量从高到低击杀烈焰人，则血量第 $r_i+1, r_i+2, \cdots, n$ 小的烈焰人已经全部被队友击杀。 同时，你可以超额完成任务。例如，若谜题规则是按血量从低到高击杀烈焰人，且你的任务是击杀血量第 $3$ 小和第 $4$ 小的烈焰人，那么，击杀血量第 $3, 4$ 小 或 击杀血量第 $3, 4, 5$ 小的烈焰人都被视为完成任务，而 击杀血量第 $3, 5$ 和 击杀血量第 $3, 4, 6$ 的烈焰人 被视为任务失败。 你惊奇地发现，每次谜题游戏中，烈焰人的血量关系 $p$ 是固定的，区别在于谜题规则和需要击杀的烈焰人范围不同。请你对于每次地牢谜题，计算完成任务所需的最小射击数。

Input

输入包含多组测试数据。 第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示数测试数据的组数。 对于每组测试数据， 第一行包含两个整数 $n$, $k$ ($1 \le k \le n \le 2 \times 10^5$)，表示烈焰人的数量和魔法弓每次击杀烈焰人的最大数量。 第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le n$)，表示烈焰人血量大小关系。保证 $p$ 是一个排列。 第三行包含一个整数 $m$ ($2 \le m \le 2 \times 10^5$)，表示需要完成谜题的次数。 接下来 $m$ 行，第 $i$ 行包含两个整数与一个字符 $l_i$, $r_i$, $c_i$ ($1 \le l_i \le r_i \le n, c_i \in \{\text{H},\text{L}\}$)，表示在第 $i$ 次谜题游戏中，你需要击杀的烈焰人范围，以及谜题规则。其中， $c_i=\text{H}$ 表示你需要按血量从低到高击杀烈焰人；$c_i=\text{L}$ 表示你需要按血量从高到低击杀烈焰人。

Output

对于每组测试数据，输出 $m$ 行，第 $i$ 行包含一个整数，表示在第 $i$ 次谜题游戏中，完成任务所需的最小射击数。

Sample Input

2
5 3
1 4 5 3 2
2
1 3 H
3 4 L
5 4
1 2 5 3 4
2
1 4 H
1 4 L

Sample Output

2
1
2
1

Source

2024“钉耙编程”中国大学生算法设计超级联赛（9）