← 返回题目列表

Codeforces · 1369/B

B. 准确李

中文机器翻译题面 查看原题

Lee 正在为聚会打扫房子,这时他在地毯下发现了一根凌乱的绳子。现在他想以一种时尚的方式准确地清洁它......

他找到的字符串 $$$s$$$ 是长度为 $$$n$$$ 的二进制字符串(即字符串仅由 0 和 1 组成)。

他一步可以选择两个连续的字符$$$s_i$$$和$$$s_{i+1}$$$,如果$$$s_i$$$为1且$$$s_{i + 1}$$$为0,他可以恰好删除其中一个(他可以选择删除哪一个,但不能同时删除两个字符)。擦除后字符串会收缩。

Lee 可以进行任意数量的移动(可能为零),并且他希望使字符串 $$$s$$$ 尽可能干净。他认为对于两个不同的字符串 $$$x$$$ 和 $$$y$$$,较短的字符串更干净,如果它们的长度相同,那么按字典顺序较小的字符串更干净。

现在你应该回​​答 $$$t$$$ 测试用例:对于第 $$$i$$$ 个测试用例,打印 Lee 通过执行一定次数的移动可以获得的最干净的字符串。

小提醒:如果我们有两个长度相同的字符串 $$$x$$$ 和 $$$y$$$,那么 $$$x$$$ 按字典顺序小于 $$$y$$$ 如果有一个位置 $$$i$$$ 使得 $$$x_1 = y_1$$$, $$$x_2 = y_2$$$,..., $$$x_{i - 1} = y_{i - 1}$$$ 且 $$$x_i < y_i$$$。

输入

第一行包含整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

接下来的 $$$2t$$$ 行包含测试用例 - 每两行一个。

每个测试用例的第一行包含整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串 $$$s$$$ 的长度。

第二行包含二进制字符串$$$s$$$。字符串 $$$s$$$ 是长度为 $$$n$$$ 的字符串,仅由零和一组成。

保证测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

打印 $$$t$$$ 答案 — 每个测试用例一个。

第 $$$i$$$ 测试用例的答案是 Lee 在进行一定次数的移动(可能为零)后可以获得的最干净的字符串。

示例

输入 #1

5
10
0001111111
4
0101
8
11001101
10
1110000000
1
1

输出 #1

0001111111
001
01
0
1

注意

在第一个测试用例中,Lee 无法执行任何动作。

在第二个测试用例中,Lee 应该删除 $$$s_2$$$。

在第三个测试用例中,Lee 可以按照以下顺序进行移动: 11001101 $$$\rightarrow$$$ 1100101 $$$\rightarrow$$$ 110101 $$$\rightarrow$$$ 10101 $$$\rightarrow$$$ 1101 $$$\rightarrow$$$ 101 $$$\右箭头$$$ 01。