(RankList for this Question)
Monocarp began with an initially empty array 𝑎 of integers. He conducted three types of operations on this array:
1. Addition Operation: Monocarp appended an integer to the end of the array, and for each such operation, he recorded a "+" character.
2. Removal Operation: Monocarp removed the last element from the array. He only performed this operation when the array was not empty, and for each removal, he wrote a "-" character.
3. Sorting Check Operation: Monocarp verified if the array was sorted in non-decreasing order, where 𝑎₁ ≤ 𝑎₂ ≤ ⋯ ≤ 𝑎ₖ, with 𝑘 being the number of elements in the array at that moment. If the array was sorted, he recorded a "1" character; otherwise, he wrote a "0" character. Arrays with fewer than 2 elements were always considered sorted.
You are given a sequence 𝑠 of 𝑞 characters, including 0, 1, +, and/or -. These characters represent the actions Monocarp performed in the exact order he executed them. Your task is to determine if this sequence is logically consistent, meaning that it was possible for Monocarp to perform the operations in a way that results in the sequence of characters being exactly 𝑠.
Constraints
- For every prefix of 𝑠, the number of characters "+" is not less than the number of characters "-" on it. In other words, Monocarp never attempts to remove the last element from an empty array.
- The sum of |𝑠| over all test cases does not exceed 2 × 10^5.
Input Format
- The first line of the input contains one integer 𝑡 (1 ≤ 𝑡 ≤ 10^4) — the number of test cases.
- Each of the following 𝑡 lines contains a string 𝑠 (1 ≤ |𝑠| ≤ 2 × 10^5), which represents the sequence of characters written by Monocarp. The string 𝑠 consists of characters 0, 1, +, and/or -.
Output Format
For each test case, print "YES" if it was possible for Monocarp to perform the queries in a way that the sequence of characters he wrote is exactly 𝑠. Otherwise, print "NO". The letter case (uppercase or lowercase) does not matter, so you can print each letter in any register.
Example 1
Input:
7
++1
+++1--0
+0
0
++0-+1-+0
++0+-1+-0
+1-+0
Output:
YES
NO
NO
NO
YES
NO
NO
Explanation:
In the first test case, Monocarp could perform the following sequence of queries:
1. add the integer 13
- 13;
2. add the integer 37
- 37;
3. check that the current array
- [13,37]
- [13,37] is sorted in non-descending order (and it is sorted).
In the fifth test case, Monocarp could perform the following sequence of queries:
1. add the integer 3
- 3;
2. add the integer 2
- 2;
3. check that the current array
- [3,2]
- [3,2] is sorted (it is not);
4. remove the last element;
5. add the integer 3
- 3;
6. check that the current array
- [3,3]
- [3,3] is sorted (it is);
7. remove the last element;
8. add the integer −5
- (−5);
9. check that the current array
- [3,−5]
- [3,−5] is sorted (it is not).
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.
Log In to solve the Question