## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Smaller Codeforces Solution | Solution Codeforces

F. Smaller
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{thickmathspace}{0ex}}k\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{thickmathspace}{0ex}}x$ — Append the string $x$ exactly $k$ times at the end of string $s$. In other words, .
• $2\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{thickmathspace}{0ex}}k\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{thickmathspace}{0ex}}x$ — Append the string $x$ exactly $k$ times at the end of string $t$. In other words, .

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

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

${}^{†}$ 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${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, $\mathtt{\text{abdc}}<\mathtt{\text{abe}}$ and $\mathtt{\text{abc}}<\mathtt{\text{abcd}}$, where we write $p if $p$ is lexicographically smaller than $q$.

Input

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

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

Then $q$ lines follow, each containing two positive integers $d$ and $k$ ($1\le d\le 2$$1\le k\le {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

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.

Note

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

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

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

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

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

After the fifth operation the string $b$ becomes "aaaaaaabcaabcaabca", and we can rearrange the strings to: "baaa" and "caaaaaabcaabcaabaa" so that $a$ is lexicographically smaller than $b$, so we should answer "YES".