CF2145B.Deck of Cards

Monocarp has a deck of cards numbered from $1$ to $n$. Initially, the cards are arranged from smallest to largest, with $1$ on top and $n$ at the bottom.

Monocarp performed $k$ actions on the deck. Each action was one of three types:

• remove the top card;
• remove the bottom card;
• remove either the top or bottom card.

Your task is to determine the fate of each card: whether it remains in the deck, has been removed, or might be both.

Monocarp 有一副编号为 $1$ 到 $n$ 的牌。初始时，这些牌按从小到大的顺序排列，$1$ 在最上方，$n$ 在最下方。

Monocarp 对这副牌执行了 $k$ 次操作。每次操作是以下三种类型之一：

• 移除最上方的牌；
• 移除最下方的牌；
• 移除最上方或最下方的牌（即：移除顶部或底部的牌，具体是哪一个不确定）。

你的任务是确定每张牌的命运：它是否仍留在牌堆中、是否已被移除，或者两种情况均有可能。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$).

The second line contains a string $s$ of length $k$, consisting of characters 0, 1, and/or {2}. This string describes Monocarp's actions. If the $i$-th character is 0, Monocarp removes the top card on the $i$-th action. If it's 1, he removes the bottom card. If it's 2, either the top or bottom card can be removed.

Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

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

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

每个测试用例的第二行包含一个长度为 $k$ 的字符串 $s$，由字符 0、1 和/或 2 组成。该字符串描述了 Monocarp 的操作：若第 $i$ 个字符为 0，则 Monocarp 在第 $i$ 次操作中移除最上面的牌；若为 1，则移除最下面的牌；若为 2，则可任选移除最上面或最下面的牌。

输入的额外约束：所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, print a string consisting of $n$ characters. The $i$-th character should be + (plus sign) if the $i$-th card is still in the deck, - (minus sign) if it has been removed, or ? (question mark) if its state is unknown.

对于每个测试用例，输出一个由 $n$ 个字符组成的字符串。其中第 $i$ 个字符应为 +（加号），表示第 $i$ 张牌仍在牌堆中；为 -（减号），表示该牌已被移除；或为 ?（问号），表示其状态未知。