题目描述

Monocarp 有一副从 $1$ 到 $n$ 编号的牌。起初，这些牌按照从小到大的顺序排列，$1$ 在顶部，$n$ 在底部。

Monocarp 对这副牌进行了 $k$ 次操作。每次操作类型有三种：

• 移除顶部的牌；
• 移除底部的牌；
• 移除顶部或底部的任意一张牌。

你的任务是判断每张牌的状态：它现在是否仍在牌堆中，已经被移除，还是可能两种情况都有可能。

输入格式

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

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$）。

第二行是一个长度为 $k$ 的字符串 $s$，由字符 $0$、$1$ 和/或 $2$ 组成。字符串 $s$ 描述了 Monocarp 的操作。如果第 $i$ 个字符是 $0$，第 $i$ 次操作移除顶部牌；如果是 $1$，则移除底部牌；如果是 $2$，可以移除顶部或底部的任意一张牌。

输入还保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个长度为 $n$ 的字符串。第 $i$ 个字符如果该牌仍在牌堆中则为加号（+），如果已被移除则为减号（-），如果状态不确定则为问号（?）。

说明/提示

由 ChatGPT 5 翻译

样例

4
4 2
01
3 2
22
1 1
2
7 5
01201

-++-
???
-
--?+?--