[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𝑘𝑥$1kx$ — Append the string 𝑥$x$ exactly 𝑘$k$ times at the end of string 𝑠$s$. In other words, 𝑠:=𝑠+𝑥+⋯+𝑥𝑘 times$s:=s+\underset{k\text{ times}}{\underbrace{x+\cdots +x}}$.
• 2𝑘𝑥$2kx$ — Append the string 𝑥$x$ exactly 𝑘$k$ times at the end of string 𝑡$t$. In other words, 𝑡:=𝑡+𝑥+⋯+𝑥𝑘 times$t:=t+\underset{k\text{ times}}{\underbrace{x+\cdots +x}}$.

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<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, 𝚊𝚋𝚍𝚌<𝚊𝚋𝚎$\mathtt{\text{abdc}}<\mathtt{\text{abe}}$ and 𝚊𝚋𝚌<𝚊𝚋𝚌𝚍$\mathtt{\text{abc}}<\mathtt{\text{abcd}}$, where we write 𝑝<𝑞$p<q$ if 𝑝$p$ is lexicographically smaller than 𝑞$q$.

Input

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

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

Then 𝑞$q$ lines follow, each containing two positive integers 𝑑$d$ and 𝑘$k$ (1≤𝑑≤2$1\le d\le 2$; 1≤𝑘≤105$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 105${10}^5$ and that the sum of lengths of all strings 𝑥$x$ in the input doesn't exceed 5⋅105$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".