Smaller
Contest: Codeforces Round 827 (Div. 4)
Difficulty rating: 1500
Tags: constructive algorithms, greedy, strings

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 < q_i$$$, and for all $$$j < 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} < \texttt{abe}$$$ and $$$\texttt{abc} < \texttt{abcd}$$$, where we write $$$p < q$$$ if $$$p$$$ is lexicographically smaller than $$$q$$$.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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".

Example input:
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

Example output:
YES
NO
YES
NO
YES
NO
YES
NO
NO
YES

Editorial:
First of all, let's think about how we should rearrange the two strings in such a way that $$$a < b$$$ (if that is ever possible). It's always optimal to arrange $$$a$$$'s characters increasingly in lexicographic order and $$$b$$$'s characters decreasingly.
Since initially both $$$a$$$ and $$$b$$$ contain a character "a", the first time $$$b$$$ receives any other letter than "a" the answer will always be "YES", because that character will always be lexicographically larger than $$$a$$$'s first character which should be "a".
In the other case, we know that $$$b$$$ doesn't have any other characters than "a", so we can compare the string $$$a$$$ with multiple "a" characters and we know that $$$a$$$ will be smaller if and only if it's only formed of "a"s and has a smaller size than $$$b$$$.