Monocarp 有一个由整数组成的数组 $$$a$$$。最初,这个数组是空的。
Monocarp 对此数组执行了三种类型的查询:
- 选择一个整数并将其附加到数组的末尾。每次 Monocarp 执行此类查询时,他都会写出一个字符 +;
- 从数组中删除最后一个元素。每次 Monocarp 执行此类查询时,他都会写出一个字符 -。 Monocarp 从未对空数组执行此查询;
- 检查数组是否按非降序排序,即$$$a_1 \le a_2 \le \dots \le a_k$$$,其中 $$$k$$$ 是当前数组中的元素数量。每个元素少于 $$$2$$$ 的数组都被视为已排序。如果该数组是按 Monocarp 执行该查询的时间排序的,他会写出一个字符 1。否则,他会写出一个字符 0。
给定一个由 $$$q$$$ 字符 0、1、+ 和/或 - 组成的序列 $$$s$$$。这些是由 Monocarp 写出的字符,按照他写出的顺序给出。
你必须检查这个序列是否一致,即。 e. Monocarp 可以执行查询,以便他写出的字符序列恰好是 $$$s$$$。
输入
输入的第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,如果 Monocarp 可以执行查询,则打印 YES,以便他编写的字符序列恰好是 $$$s$$$。否则,打印NO。
您可以打印任何寄存器中的每个字母。
示例
输入 #1
7 ++1 +++1--0 +0 0 ++0-+1-+0 ++0+-1+-0 +1-+0
输出 #1
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$$$。