角色巴士中有 $$$n$$$ 排座位,每排有 $$$2$$$ 个座位。第 $$$i$$$ 排的两个座位的宽度均为 $$$w_i$$$ 厘米。所有整数 $$$w_i$$$ 都是不同的。
最初巴士是空的。每个 $$$2n$$$ 站都有一名乘客上车。乘客有两种类型:
- 内向的人总是选择两个座位都空的一排。在这些排中,他选择座位宽度最小的一排,并占据其中的一个座位;
- 外向的人总是选择恰好有一个座位(被内向的人占据)的那排。在这些排中,他选择座位宽度最大的一排并占据其中的空位。
您将获得每排座位的宽度以及乘客上车的顺序。确定每位乘客将乘坐哪排。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$) — 总线中的行数。
第二行包含整数序列 $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 10^{9}$$$),其中 $$$w_i$$$ 是第 $$$i$$$ 行中每个座位的宽度。保证所有 $$$w_i$$$ 都是不同的。
第三行包含一个长度为$$$2n$$$的字符串,由数字“0”和“1”组成——描述乘客上车的顺序。如果第 $$$j$$$ 个字符为“0”,则在第 $$$j$$$ 个车站上车的乘客是内向者。如果第 $$$j$$$ 个字符为“1”,则在第 $$$j$$$ 个车站上车的乘客是外向的。保证外向者的数量等于内向者的数量(即两个数字都等于 $$$n$$$),并且对于每个外向者总是有一个合适的行。
输出
打印 $$$2n$$$ 整数 — 乘客将乘坐的行数。乘客的顺序应与输入时的顺序相同。
示例
输入 #1
2 3 1 0011
输出 #1
2 1 1 2
输入 #2
6 10 8 9 11 13 5 010010011101
输出 #2
6 6 2 3 3 1 4 4 1 2 5 5
注意
在第一个示例中,第一位乘客(性格内向)选择 $$$2$$$ 行,因为它的座位宽度最小。第二位乘客(性格内向)选择 $$$1$$$ 行,因为它是现在唯一的空行。第三位乘客(性格外向)选择$$$1$$$这一排,因为它只有一个座位,而且座位宽度是该排中最大的。第四位乘客(外向)选择 $$$2$$$ 行,因为它是唯一有空位的行。