Monocarp had an array $$$a$$$ consisting of integers. Initially, this array was empty.
Monocarp performed three types of queries to this array:
You are given a sequence $$$s$$$ of $$$q$$$ characters 0, 1, + and/or -. These are the characters that were written out by Monocarp, given in the exact order he wrote them out.
You have to check if this sequence is consistent, i. e. it was possible for Monocarp to perform the queries so that the sequence of characters he wrote out is exactly $$$s$$$.
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$). This string consists of characters 0, 1, + and/or -. This is the sequence of characters written by Monocarp, in the order he wrote them.
Additional constraints on the input:
For each test case, print YES if it was possible for Monocarp to perform the queries so that the sequence of characters he wrote is exactly $$$s$$$. Otherwise, print NO.
You can print each letter in any register.
7++1+++1--0+00++0-+1-+0++0+-1+-0+1-+0
YES NO NO NO YES NO NO
In the first test case, Monocarp could perform the following sequence of queries:
In the fifth test case, Monocarp could perform the following sequence of queries:
In all other test cases of the example test, it is impossible for Monocarp to write the sequence $$$s$$$ when performing the queries according to the statement.
Name |
---|