CF1861C.Queries for the Array

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

Monocarp 有一个由整数组成的数组 $a$。最初，该数组为空。

Monocarp 对该数组执行了三种类型的查询：

• 选择一个整数，并将其追加到数组末尾。每次 Monocarp 执行此类查询时，他都会写出一个字符 +；
• 删除数组的最后一个元素。每次 Monocarp 执行此类查询时，他都会写出一个字符 -。Monocarp 从未在空数组上执行过此类查询；
• 检查数组是否按非降序排列，即 $a_1 \le a_2 \le \dots \le a_k$，其中 $k$ 是当前数组中元素的个数。任何元素个数少于 $2$ 的数组均被视为已排序。若 Monocarp 执行该查询时数组已排序，则他写出字符 1；否则，他写出字符 0。

你将得到一个长度为 $q$ 的字符串 $s$，其字符仅包含 0、1、+ 和 -。该字符串即为 Monocarp 写出的字符序列，且按其书写顺序给出。

你需要判断该序列是否一致，即：是否存在一种查询执行方式，使得 Monocarp 写出的字符序列恰好为 $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 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$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例由一行组成，包含字符串 $s$（$1 \le |s| \le 2 \cdot 10^5$）。该字符串仅由字符 0、1、+ 和/或 - 组成。这是 Monocarp 书写的字符序列，按其书写顺序给出。

输入的额外约束条件：

• 对于 $s$ 的每一个前缀，其中字符 + 的数量不少于字符 - 的数量。换言之，若 Monocarp 实际执行这些操作，则他永远不会尝试从空数组中删除最后一个元素；
• 所有测试用例的 $|s|$ 之和不超过 $2 \cdot 10^5$。

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.

对于每个测试用例，如果存在一种方式使得 Monocarp 执行这些查询后所写出的字符序列恰好为 $s$，则输出 YES；否则输出 NO。

你可以以任意大小写形式输出每个字母。

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 可以执行以下查询序列：

• 添加整数 $13$；
• 添加整数 $37$；
• 检查当前数组 $[13, 37]$ 是否按非降序排列（该数组确实已按非降序排列）。

在第五个测试用例中，Monocarp 可以执行以下查询序列：

• 添加整数 $3$；
• 添加整数 $2$；
• 检查当前数组 $[3, 2]$ 是否已排序（该数组未排序）；
• 删除最后一个元素；
• 添加整数 $3$；
• 检查当前数组 $[3, 3]$ 是否已排序（该数组已排序）；
• 删除最后一个元素；
• 添加整数 $-5$；
• 检查当前数组 $[3, -5]$ 是否已排序（该数组未排序）。

在示例测试的其余所有测试用例中，Monocarp 均无法按照题面所述的查询方式写出序列 $s$。