题目描述

光头强有两个字符串，$s$ 和 $t$，它们最初都等于 a。

他将对给定字符串执行两种类型的 $q$ 操作：

• 1 $k$ $x$-在字符串 $s$ 的末尾附加 $k$ 次字符串 $x$。换句话说，$s:=s+x+…+x$ ($k$次)。
• 2 $k$ $x$-在字符串 $t$ 的末尾附加 $k$ 次字符串 $x$。换句话说，$t:=t+x+…+x$ ($k$次)。

每次操作后，确定是否可以重新排列 $s$ 和 $t$ 的字符，使 $s$ 在字典序上比 $t$ 小。

请注意，字符串在执行每个操作后都会发生变化，不会返回到初始状态。

简单地说，词典顺序是单词在词典中列出的顺序。一个正式的定义如下：如果存在一个位置 $i$ 使得 $p_i<q_i$，并且对于所有 $j<i，p_j=q_j$，则字符串 $p$ 在字典上小于字符串 $q$。如果不存在这样的 $i$，那么如果 $p$ 的长度小于 $q$ 的长度，则 $p$ 在字典上小于 $q$。例如，$abdc<abe$ 和 $abc<abcd$，其中如果 $p$ 在字典中小于 $q$，则我们写 $p<q$。

输入格式

输入的第一行包含整数 $t(1≤t≤10^4)$ 代表测试用例的数量。

每个测试用例的第一行包含一个整数 $q(1≤q≤10^5)$ 代表光头强将执行的操作数。

然后是 $q$ 行，每行包含两个正整数 $d$ 和 $k(1≤d≤2，1≤k≤10^5)$ 以及一个由小写英文字母组成的非空字符串 $x$ 分别代表操作类型、我们将追加字符串 $x$ 的次数以及我们需要追加的字符串。

保证所有测试用例的 $q$ 总和不超过 $10^5$，并且输入中所有字符串 $x$ 的长度总和不超过 $5⋅10^5$。

输出格式

对于每个操作，如果可以将两个字符串中的元素排列为 $s$ 在字典上小于 $t$，则输出 YES，否则输出 NO。大小写随意。

测试样例

3
5
2 1 aa
1 2 a
2 3 a
1 2 b
2 3 abca
2
1 5 mihai
2 2 buiucani
3
1 5 b
2 3 a
2 4 paiu

YES
NO
YES
NO
YES
NO
YES
NO
NO
YES

样例说明

在第一个测试用例中，字符串最初是 $s=$a 和 $t=$a。

第一次操作后，字符串 $t$ 变为 aaa。由于 a 在词典上已经小于 aaa，因此该操作的答案应该是 YES。

第二次操作字符串 $s$ 变为 aaa 之后，由于 $t$ 也等于 aaa，我们不能以任何方式排列 $s$，使其在字典上小于 $t$，因此答案是 NO。

第三次操作字符串 $t$ 变为 aaaaaa，并且 $s$ 在字典上已经比它小，所以答案是 YES。

第四次操作后，$s$ 变为 aaaabb，并且没有办法使其在字典上小于 aaaaaa，因此答案是 NO。

第五次操作后，字符串 $t$ 变为 aaaaaabcaabcaabca，我们可以将字符串 $s$ 和 $t$ 重新排列为：bbaaa 和 caaaaabcaabcaabaa，这样 $s$ 在字典上比 $t$ 小，所以我们应该回答 YES。