У Монокарпа был массив $$$a$$$, состоящий из целых чисел. Изначально массив был пустым.
Монокарп выполнял три типа запросов к этому массиву:
Вам задана строка $$$s$$$, состоящая из $$$q$$$ символов 0, 1, + и/или -. Это символы, выписанные Монокарпом, строго в том порядке, в каком он их выписывал.
Вам нужно выяснить, является ли эта строка непротиворечивой, т. е. мог ли Монокарп выполнять такие запросы, что выписанная после них строка равна строке $$$s$$$.
Первая строка входных данных содержит одно число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Единственная строка каждого набора входных данных содержит строку $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$). Это строка состоит из символов 0, 1, + и/или -. Это символы, выписанные Монокарпом, строго в том порядке, в каком он их выписывал.
Дополнительные ограничения на входные данные:
Для каждого набора входных данных выведите YES, если Монокарп мог выполнить такие запросы, в результате которых будет выписана строка $$$s$$$. Иначе выведите NO.
Вы можете выводить символы в ответе в любом регистре.
7++1+++1--0+00++0-+1-+0++0+-1+-0+1-+0
YES NO NO NO YES NO NO
В первом наборе входных данных Монокарп мог выполнить следующие запросы:
В пятом наборе входных данных Монокарп мог выполнить следующие запросы:
В остальных наборах входных данных Монокарп не мог выписать строку $$$s$$$, выполняя свои запросы.
Название |
---|