CF2145B Deck of Cards

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 翻译