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}。该字符串描述了 Monocarp 的操作。如果第 $$$i$$$ 个字符是 0,Monocarp 在第 $$$i$$$ 个动作中移除了顶牌。如果是 1,他移除了底下的牌。如果是 2,可以移除顶部或底部的卡。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个由 $$$n$$$ 字符组成的字符串。第 $$$i$$$ 个字符应该是 + (加号)如果第$$$i$$$张牌仍在牌组中, - (减号)如果已被删除,或者 ? (问号)如果其状态未知。
示例
输入复制
44 2013 2221 127 501201
输出复制
-++-???---?+?--