在地牢谜题游戏 更高还是更低 中，初始有 $n$ 只血量不同烈焰人排列成一列，第 $i$ 只烈焰人是所有烈焰人中血量第 $p_i$ 小的。你需要按血量从低到高或从高到低的顺序（由谜题规则确定）击杀所有的烈焰人。

你有一把魔法弓，每次射击可以击杀不超过 $k$ 只相邻的烈焰人，你可以自由决定在同一次射击中烈焰人死亡的顺序。两只烈焰人是相邻的当且仅当它们之间的烈焰人都已经死亡。

你和你的同伴需要完成该地牢谜题 $m$ 次。作为一个队伍，你自然不需要独自解决谜题。在第 $i$ 次进行谜题游戏时，你的任务是击杀血量第 $l_i$ 小，第 $l_i+1$ 小，...，第 $r_i$ 小的烈焰人。 这意味着，在你开始任务之前，若谜题规则是按照血量从低到高击杀烈焰人，则血量第 $1,2,⋯,l_i −1$ 小的烈焰人已经全部被队友击杀；若谜题规则是按照血量从高到低击杀烈焰人，则血量第 $r_i+1,r_i+2,⋯,n$ 小的烈焰人已经全部被队友击杀。

同时，你可以超额完成任务。例如，若谜题规则是按血量从低到高击杀烈焰人，且你的任务是击杀血量第 $3$ 小和第 $4$ 小的烈焰人，那么，击杀血量第 $3,4$ 小 或 击杀血量第 $3,4,5$ 小的烈焰人都被视为完成任务，而 击杀血量第 $3,5$ 和 击杀血量第 $3,4,6$ 的烈焰人 被视为任务失败。

你惊奇地发现，每次谜题游戏中，烈焰人的血量关系 $p$ 是固定的，区别在于谜题规则和需要击杀的烈焰人范围不同。请你对于每次地牢谜题，计算完成任务所需的最小射击数。

输入包含多组测试数据。

第一行包含一个整数 $T (1≤T≤10)$，表示数测试数据的组数。

对于每组测试数据，

第一行包含两个整数 $n,k (1≤k≤n≤2×10^5 )$，表示烈焰人的数量和魔法弓每次击杀烈焰人的最大数量。

第二行包含 $n$ 个整数 $p_1,p_2,…,p_n (1≤p_i ≤n)$，表示烈焰人血量大小关系。保证 $p$ 是一个排列。

第三行包含一个整数 $m (2≤m≤2×10^5 )$，表示需要完成谜题的次数。

接下来 $m$ 行，第 $i$ 行包含两个整数与一个字符 $l_i , r_i ,c_i (1≤l_i≤r_i≤n,c_i∈H,L)$，表示在第 $i$ 次谜题游戏中，你需要击杀的烈焰人范围，以及谜题规则。其中， $c_i =H$ 表示你需要按血量从低到高击杀烈焰人；

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