310621: CF1861C. Queries for the Array

C. Queries for the Arraytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Monocarp had an array $a$ consisting of integers. Initially, this array was empty.

Monocarp performed three types of queries to this array:

• choose an integer and append it to the end of the array. Each time Monocarp performed a query of this type, he wrote out a character +;
• remove the last element from the array. Each time Monocarp performed a query of this type, he wrote out a character -. Monocarp never performed this query on an empty array;
• check if the array is sorted in non-descending order, i.,e. $a_1 \le a_2 \le \dots \le a_k$, where $k$ is the number of elements in the array currently. Every array with less than $2$ elements is considered sorted. If the array was sorted by the time Monocarp was performing that query, he wrote out a character 1. Otherwise, he wrote out a character 0.

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$.

Input

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 every prefix of $s$, the number of characters + on it is not less than the number of characters - on it. In other words, if Monocarp actually performed these queries, he would never try to remove the last element from the empty array;
• the sum of $|s|$ over all test cases does not exceed $2 \cdot 10^5$.

Output

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.

ExampleInput

7
++1
+++1--0
+0
0
++0-+1-+0
++0+-1+-0
+1-+0

Output

YES
NO
NO
NO
YES
NO
NO

Note

In the first test case, Monocarp could perform the following sequence of queries:

• add the integer $13$;
• add the integer $37$;
• check that the current array $[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:

• add the integer $3$;
• add the integer $2$;
• check that the current array $[3, 2]$ is sorted (it is not);
• remove the last element;
• add the integer $3$;
• check that the current array $[3, 3]$ is sorted (it is);
• remove the last element;
• add the integer $-5$;
• check that the current array $[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.

题目大意：
Monocarp有一个初始为空的整数数组a。他会对这个数组执行三种类型的操作：
1. 选择一个整数并把它添加到数组末尾。每次进行这种操作时，Monocarp会记录一个"+"字符。
2. 删除数组的最后一个元素。每次进行这种操作时，Monocarp会记录一个"-"字符。Monocarp不会在数组为空时执行这种操作。
3. 检查数组是否按非降序排序，即a1 <= a2 <= ... <= ak，其中k是数组当前元素的数量。任何少于2个元素的数组都被认为是排序的。如果数组在Monocarp执行该操作时已经排序，他会记录一个"1"字符。否则，他会记录一个"0"字符。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 <= t <= 10^4），表示测试用例的数量。
- 每个测试用例包含一行，是一个字符串s（1 <= |s| <= 2 * 10^5）。这个字符串由字符"0"、"1"、"+"和"/"组成，按Monocarp记录的顺序排列。

输出：
- 对于每个测试用例，如果可能按照Monocarp记录的顺序执行操作得到字符串s，则输出"YES"。否则，输出"NO"。

示例输入输出：
输入：
```
7
++1
+++1--0
+0
0
++0-+1-+0
++0+-1+-0
+1-+0
```
输出：
```
YES
NO
NO
NO
YES
NO
NO
```

注意：
- 在第一个测试用例中，Monocarp可以执行以下操作序列：添加整数13，添加整数37，检查当前数组[13, 37]是否按非降序排序（是）。
- 在第五个测试用例中，Monocarp可以执行以下操作序列：添加整数3，添加整数2，检查当前数组[3, 2]是否排序（否），删除最后一个元素，添加整数3，检查当前数组[3, 3]是否排序（是），删除最后一个元素，添加整数-5，检查当前数组[3, -5]是否排序（否）。
- 在示例测试的所有其他测试用例中，根据题目描述，Monocarp无法在执行操作时得到序列s。题目大意： Monocarp有一个初始为空的整数数组a。他会对这个数组执行三种类型的操作： 1. 选择一个整数并把它添加到数组末尾。每次进行这种操作时，Monocarp会记录一个"+"字符。 2. 删除数组的最后一个元素。每次进行这种操作时，Monocarp会记录一个"-"字符。Monocarp不会在数组为空时执行这种操作。 3. 检查数组是否按非降序排序，即a1 <= a2 <= ... <= ak，其中k是数组当前元素的数量。任何少于2个元素的数组都被认为是排序的。如果数组在Monocarp执行该操作时已经排序，他会记录一个"1"字符。否则，他会记录一个"0"字符。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 <= t <= 10^4），表示测试用例的数量。 - 每个测试用例包含一行，是一个字符串s（1 <= |s| <= 2 * 10^5）。这个字符串由字符"0"、"1"、"+"和"/"组成，按Monocarp记录的顺序排列。 输出： - 对于每个测试用例，如果可能按照Monocarp记录的顺序执行操作得到字符串s，则输出"YES"。否则，输出"NO"。 示例输入输出： 输入： ``` 7 ++1 +++1--0 +0 0 ++0-+1-+0 ++0+-1+-0 +1-+0 ``` 输出： ``` YES NO NO NO YES NO NO ``` 注意： - 在第一个测试用例中，Monocarp可以执行以下操作序列：添加整数13，添加整数37，检查当前数组[13, 37]是否按非降序排序（是）。 - 在第五个测试用例中，Monocarp可以执行以下操作序列：添加整数3，添加整数2，检查当前数组[3, 2]是否排序（否），删除最后一个元素，添加整数3，检查当前数组[3, 3]是否排序（是），删除最后一个元素，添加整数-5，检查当前数组[3, -5]是否排序（否）。 - 在示例测试的所有其他测试用例中，根据题目描述，Monocarp无法在执行操作时得到序列s。