C. Запросы к массиву
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа был массив $$$a$$$, состоящий из целых чисел. Изначально массив был пустым.

Монокарп выполнял три типа запросов к этому массиву:

  • выбрать число и добавить его в конец массива. Каждый раз, когда Монокарп выполнял этот запрос, он выписывал символ +;
  • удалить последний элемент из массива. Каждый раз, когда Монокарп выполнял этот запрос, он выписывал символ -. Монокарп не выполнял этот запрос, если массив был пуст;
  • проверить, отсортирован ли массив в порядке неубывания, т. е. выполняется ли $$$a_1 \le a_2 \le \dots \le a_k$$$, где $$$k$$$ — количество элементов в массиве на данный момент. Любой массив, содержащий меньше $$$2$$$ элементов, считается отсортированным. Если массив отсортирован в момент запроса, Монокарп выписывал символ 1. Иначе он выписывал символ 0.

Вам задана строка $$$s$$$, состоящая из $$$q$$$ символов 0, 1, + и/или -. Это символы, выписанные Монокарпом, строго в том порядке, в каком он их выписывал.

Вам нужно выяснить, является ли эта строка непротиворечивой, т. е. мог ли Монокарп выполнять такие запросы, что выписанная после них строка равна строке $$$s$$$.

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

Первая строка входных данных содержит одно число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит строку $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$). Это строка состоит из символов 0, 1, + и/или -. Это символы, выписанные Монокарпом, строго в том порядке, в каком он их выписывал.

Дополнительные ограничения на входные данные:

  • для любого префикса $$$s$$$ количество символов + не меньше количества символов -. Другими словами, если бы Монокарп выполнял описанные в условии запросы, он никогда не пытался бы удалить элемент из пустого массива;
  • сумма $$$|s|$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите YES, если Монокарп мог выполнить такие запросы, в результате которых будет выписана строка $$$s$$$. Иначе выведите NO.

Вы можете выводить символы в ответе в любом регистре.

Пример
Входные данные
7
++1
+++1--0
+0
0
++0-+1-+0
++0+-1+-0
+1-+0
Выходные данные
YES
NO
NO
NO
YES
NO
NO
Примечание

В первом наборе входных данных Монокарп мог выполнить следующие запросы:

  • добавить число $$$13$$$;
  • добавить число $$$37$$$;
  • проверить, что массив $$$[13, 37]$$$ отсортирован в порядке неубывания (и он действительно отсортирован).

В пятом наборе входных данных Монокарп мог выполнить следующие запросы:

  • добавить число $$$3$$$;
  • добавить число $$$2$$$;
  • проверить, что массив $$$[3, 2]$$$ отсортирован (он не отсортирован);
  • удалить последний элемент;
  • добавить число $$$3$$$;
  • проверить, что массив $$$[3, 3]$$$ отсортирован (он отсортирован);
  • удалить последний элемент;
  • добавить число $$$-5$$$;
  • проверить, что массив $$$[3, -5]$$$ отсортирован (он не отсортирован);

В остальных наборах входных данных Монокарп не мог выписать строку $$$s$$$, выполняя свои запросы.