Alperen 有两个字符串,$$$s$$$ 和 $$$t$$$,它们最初都等于“a”。
他将对给定的字符串执行两种类型的 $$$q$$$ 操作:
- $$$1 \;\; k \;\; x$$$ — 在字符串 $$$s$$$ 末尾追加字符串 $$$x$$$ 恰好 $$$k$$$ 次。换句话说,$$$s := s + \underbrace{x + \dots + x}_{k \text{ times}}$$$。
- $$$2 \;\; k \;\; x$$$ — 在字符串 $$$t$$$ 末尾追加字符串 $$$x$$$ 恰好 $$$k$$$ 次。换句话说,$$$t := t + \underbrace{x + \dots + x}_{k \text{ times}}$$$。
每次操作后,确定是否可以重新排列 $$$s$$$ 和 $$$t$$$ 的字符,使得 $$$s$$$ 按字典顺序小于 $$$^{\dagger}$$$ 小于 $$$t$$$。
请注意,执行每个操作后字符串都会发生变化,并且不会返回到其初始状态。
$$$^{\dagger}$$$ 简单来说,字典顺序就是单词在字典中列出的顺序。正式定义如下:如果存在 $$$i$$$ 位置使得 $$$p_i < q_i$$$,并且对于所有 $$$j < i$$$,$$$p_j = q_j$$$,则字符串 $$$p$$$ 按字典顺序小于字符串 $$$q$$$。如果不存在这样的$$$i$$$,则如果$$$p$$$ 的长度小于$$$q$$$ 的长度,则$$$p$$$ 按字典顺序小于$$$q$$$。例如,$$$\texttt{abdc} < \texttt{abe}$$$ 和 $$$\texttt{abc} < \texttt{abcd}$$$,如果 $$$p$$$ 按字典顺序小于 $$$q$$$,则写为 $$$p < q$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ - Alperen 将执行的操作数。
接下来是 $$$q$$$ 行,每行包含两个正整数 $$$d$$$ 和 $$$k$$$ ($$$1 \leq d \leq 2$$$; $$$1 \leq k \leq 10^5$$$) 和一个由小写英文字母组成的非空字符串 $$$x$$$ — 操作的类型,我们追加字符串的次数$$$x$$$ 和我们需要分别附加的字符串。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$10^5$$$,并且输入中所有字符串 $$$x$$$ 的长度总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个操作,如果可以以 $$$s$$$ 按字典顺序小于 $$$t$$$ 的方式排列两个字符串中的元素,则输出“YES”,否则输出“NO”。
示例
输入 #1
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
输出 #1
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$$$ 变为“aaabb”,并且无法使其按字典顺序小于“aaaaaa”,因此答案为“NO”。
第五次操作后,字符串$$$t$$$变为“aaaaaaabcaabcaabca”,我们可以将字符串重新排列为:“bbaaa”和“caaaaaabcaabcaabaa”,以便$$$s$$$按字典顺序小于$$$t$$$,因此我们应该回答“YES”。