Bus of Characters（栈和队列）

In the Bus of Characters there are nn rows of seat, each having 22 seats. The width of both seats in the ii-th row is wiwi centimeters. All integers wiwi are distinct.

Initially the bus is empty. On each of 2n2n stops one passenger enters the bus. There are two types of passengers:

• an introvert always chooses a row where both seats are empty. Among these rows he chooses the one with the smallest seats width and takes one of the seats in it;
• an extrovert always chooses a row where exactly one seat is occupied (by an introvert). Among these rows he chooses the one with the largest seats width and takes the vacant place in it.

You are given the seats width in each row and the order the passengers enter the bus. Determine which row each passenger will take.

Input

The first line contains a single integer nn (1≤n≤2000001≤n≤200000) — the number of rows in the bus.

The second line contains the sequence of integers w1,w2,…,wnw1,w2,…,wn (1≤wi≤1091≤wi≤109), where wiwi is the width of each of the seats in the ii-th row. It is guaranteed that all wiwi are distinct.

The third line contains a string of length 2n2n, consisting of digits '0' and '1' — the description of the order the passengers enter the bus. If the jj-th character is '0', then the passenger that enters the bus on the jj-th stop is an introvert. If the jj-th character is '1', the the passenger that enters the bus on the jj-th stop is an extrovert. It is guaranteed that the number of extroverts equals the number of introverts (i. e. both numbers equal nn), and for each extrovert there always is a suitable row.

Output

Print 2n2n integers — the rows the passengers will take. The order of passengers should be the same as in input.

Examples

input

Copy

2
3 1
0011

output

Copy

2 1 1 2 

input

Copy

6
10 8 9 11 13 5
010010011101

output

Copy

6 6 2 3 3 1 4 4 1 2 5 5 

Note

In the first example the first passenger (introvert) chooses the row 22, because it has the seats with smallest width. The second passenger (introvert) chooses the row 11, because it is the only empty row now. The third passenger (extrovert) chooses the row 11, because it has exactly one occupied seat and the seat width is the largest among such rows. The fourth passenger (extrovert) chooses the row 22, because it is the only row with an empty place.

在角色巴士中有n排座位，每排都有2个座位。 第i排的两个座位的宽度均为w _i厘米。 没有相同宽度的座椅。

 

公共汽车最初是空的。 每个2n站都会有一位乘客进入巴士。 有两种类型的乘客：

 

• 一个内向者总是选择两个座位都没人的一排。 在这些排中，他选择座位宽度最小的，并占据了其中的一个座位;
• 一个外向型的人总是选择有人的一排。 在这些排中，他选择了座位宽度最大的那个，并占据了空位。

 

你会得到每排座位的宽度和乘客进入公共汽车的顺序。 确定每位乘客将乘坐哪一排。

Input

第一行包含一个整数n（1 ≤ n ≤ 200000） - 总排数。

 

第二行包含整数w ₁，w ₂，...，w _n（1 ≤ w _i ≤ 10 ⁹）的序列，其中wi是第i行中每个座位的宽度。 保证所有 w _i 都不同。

 

第三行包含一个长度为 2n 的字符串，由数字“0”和“1”组成 - 描述乘客进入公共汽车的顺序。 如果第j个字符是 '0'，那么在第 j 个车站进入公共汽车的乘客是内向的。 如果第j个字符是 '1'，则在第j个车站进入公交车的乘客是外向型的。 保证外向者的数量等于内向者的数量（即两个数字等于 n），并且对于每个外向者总是有合适的行。

Output

打印 2n 个整数 - 乘客将坐的排。 乘客的顺序应与输入的顺序相同。

Sample Input

Input

2
3 1
0011

Output

2 1 1 2 

Input

6
10 8 9 11 13 5
010010011101

Output

6 6 2 3 3 1 4 4 1 2 5 5

Hint

在第一个例子中，第一个乘客（内向）选择第二排，因为它具有最小宽度的座位。 第二位乘客（内向）选择第1行，因为它现在是唯一的空行。 第三位乘客（外向型）选择第一排，因为它只有一个占用的座位，座位宽度是这些排中最大的。 第四位乘客（外向性）选择第二排，因为它是唯一一个有空位的排。

解题思路：我们知道内向的人会去选择那些空位并且宽度最小的座位，而外向的人却是选择有人的座位边的座位并且尽可能的座位宽度要大，这里其实是可以使用一个栈来模拟的，根据题目所给的信息，我们可以知道，肯定是先有内向的人上车再有外向的人上车，内向人上车就可以看做一个入栈的过程，记录内向人的座号，外向人上车必然会选择之前内向人做过的排位，而恰到好处的是这个题目的要求，内向人尽可能地选择宽度小的座位，而外向人尽可能选择宽度大的座位，在这里就可以现将座位的宽度升序排序，使内向上车的人尽可能得到宽度小的座位，而外向上车的人会得到靠近内向人并且座位宽度尽可能大的座位（栈中的第一个元素）

#include<stdio.h>
#include<algorithm>
#include<stack>
using namespace std;
struct node
{
    int val;
    int idx;
} a[200010];
char x[400010];
int my_cmp(node a,node b)
{
    if(a.val<b.val)
        return 1;
    else
        return 0;
}
stack<node>s;
int main()
{
    int n,i,j;
    struct node k;
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i].val);
        a[i].idx=i;
    }
    sort(a,a+n,my_cmp);
    getchar();
    gets(x);
    j=0;
    for(i=0; i<2*n; i++)
    {
        if(x[i]=='0')
        {
            s.push(a[j]);
            j++;
            printf("%d ",a[j-1].idx+1);
        }
        else
        {
            k=s.top();
            printf("%d ",k.idx+1);
            s.pop();
        }
    }
    return 0;
}