CF1742F.Smaller

Alperen has two strings, $s$ and $t$ which are both initially equal to "a".

He will perform $q$ operations of two types on the given strings:

• $1 \;\; k \;\; x$ — Append the string $x$ exactly $k$ times at the end of string $s$. In other words, $s := s + \underbrace{x + \dots + x}_{k \text{ times}}$.
• $2 \;\; k \;\; x$ — Append the string $x$ exactly $k$ times at the end of string $t$. In other words, $t := t + \underbrace{x + \dots + x}_{k \text{ times}}$.

After each operation, determine if it is possible to rearrange the characters of $s$ and $t$ such that $s$ is lexicographically smaller$^{\dagger}$ than $t$.

Note that the strings change after performing each operation and don't go back to their initial states.

$^{\dagger}$ Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. A formal definition is as follows: string $p$ is lexicographically smaller than string $q$ if there exists a position $i$ such that $p_i \lt q_i$, and for all $j \lt i$, $p_j = q_j$. If no such $i$ exists, then $p$ is lexicographically smaller than $q$ if the length of $p$ is less than the length of $q$. For example, $\texttt{abdc} \lt \texttt{abe}$ and $\texttt{abc} \lt \texttt{abcd}$, where we write $p \lt q$ if $p$ is lexicographically smaller than $q$.

阿尔佩伦有两个字符串 $s$ 和 $t$，初始时二者均等于 "a"。

他将对这两个字符串执行 $q$ 次操作，操作分为两类：

• $1 \;\; k \;\; x$ —— 将字符串 $x$ 恰好重复 $k$ 次并拼接到字符串 $s$ 的末尾。即：$s := s + \underbrace{x + \dots + x}_{k \text{ 次}}$。
• $2 \;\; k \;\; x$ —— 将字符串 $x$ 恰好重复 $k$ 次并拼接到字符串 $t$ 的末尾。即：$t := t + \underbrace{x + \dots + x}_{k \text{ 次}}$。

每次操作后，请判断是否可能通过重新排列 $s$ 和 $t$ 中的字符（各自独立重排），使得重排后的 $s$ 在字典序上严格小于重排后的 $t$。

注意：字符串在每次操作后都会发生改变，且不会恢复至初始状态。

$^{\dagger}$ 简单来说，字典序即单词在字典中的排列顺序。其形式化定义如下：字符串 $p$ 在字典序上小于字符串 $q$，当且仅当存在某个位置 $i$，使得 $p_i \lt q_i$，且对所有 $j \lt i$ 均有 $p_j = q_j$；若不存在这样的 $i$，则当且仅当 $p$ 的长度小于 $q$ 的长度时，$p$ 在字典序上小于 $q$。例如，$\texttt{abdc} \lt \texttt{abe}$ 且 $\texttt{abc} \lt \texttt{abcd}$，其中我们用 $p \lt q$ 表示 $p$ 在字典序上小于 $q$。

The first line of the input contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains an integer $q$ $(1 \leq q \leq 10^5)$ — the number of operations Alperen will perform.

Then $q$ lines follow, each containing two positive integers $d$ and $k$ ($1 \leq d \leq 2$; $1 \leq k \leq 10^5$) and a non-empty string $x$ consisting of lowercase English letters — the type of the operation, the number of times we will append string $x$ and the string we need to append respectively.

It is guaranteed that the sum of $q$ over all test cases doesn't exceed $10^5$ and that the sum of lengths of all strings $x$ in the input doesn't exceed $5 \cdot 10^5$.

输入的第一行包含一个整数 $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$。

For each operation, output "YES", if it is possible to arrange the elements in both strings in such a way that $s$ is lexicographically smaller than $t$ and "NO" otherwise.

对于每个操作，如果能够以某种方式重新排列两个字符串中的元素，使得 $s$ 的字典序小于 $t$，则输出 “YES”，否则输出 “NO”。

In the first test case, the strings are initially $s = $ "a" and $t = $ "a".

After the first operation the string $t$ becomes "aaa". Since "a" is already lexicographically smaller than "aaa", the answer for this operation should be "YES".

After the second operation string $s$ becomes "aaa", and since $t$ is also equal to "aaa", we can't arrange $s$ in any way such that it is lexicographically smaller than $t$, so the answer is "NO".

After the third operation string $t$ becomes "aaaaaa" and $s$ is already lexicographically smaller than it so the answer is "YES".

After the fourth operation $s$ becomes "aaabb" and there is no way to make it lexicographically smaller than "aaaaaa" so the answer is "NO".

After the fifth operation the string $t$ becomes "aaaaaaabcaabcaabca", and we can rearrange the strings to: "bbaaa" and "caaaaaabcaabcaabaa" so that $s$ is lexicographically smaller than $t$, so we should answer "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"。