У Альперена есть две строки, \(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\).
Выходные данные
Для каждой операции выведите «YES», если возможно расположить элементы в обеих строках таким образом, что \(s\) будет лексикографически меньше \(t\) и «NO» в противном случае.
Примечание
В первом примере строки изначально являются \(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».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|