F. Меньше
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Альперена есть две строки, $$$s$$$ и $$$t$$$, которые обе изначально равны «a».

Он выполнит $$$q$$$ операций двух видов над данными строками:

  • $$$1 \;\; k \;\; x$$$ — Добавить строку $$$x$$$ ровно $$$k$$$ раз в конец строки $$$s$$$. Другими словами, $$$s := s + \underbrace{x + \dots + x}_{k \text{ times}}$$$.
  • $$$2 \;\; k \;\; x$$$ — Добавить строку $$$x$$$ ровно $$$k$$$ раз в конец строки $$$t$$$. Другими словами, $$$t := t + \underbrace{x + \dots + x}_{k \text{ times}}$$$.

После каждой операции определите, можно ли переставить символы $$$s$$$ и $$$t$$$ так, чтобы $$$s$$$ была лексикографически меньше $$$^{\dagger}$$$, чем $$$t$$$.

Обратите внимание, что строки изменяются после выполнения каждой операции и не возвращаются в исходное состояние.

$$$^{\dagger}$$$ Проще говоря, лексикографический порядок - это порядок, в котором слова перечислены в словаре. Формальное определение таково: строка $$$p$$$ лексикографически меньше строки $$$q$$$, если существует позиция $$$i$$$ такая, что $$$p_i < q_i$$$, и для всех $$$j < i$$$, $$$p_j = q_j$$$. Если такой позиции $$$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$$$.

Выходные данные

Для каждой операции выведите «YES», если возможно расположить элементы в обеих строках таким образом, что $$$s$$$ будет лексикографически меньше $$$t$$$ и «NO» в противном случае.

Пример
Входные данные
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
Выходные данные
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».