27868번 - On My Way Dorm 스페셜 저지

때는 2223년, 이제 인류는 화성을 테라포밍한 것을 넘어 그 표면에 수많은 궤도 엘리베이터를 건설했다.

2백 년이 넘는 역사를 자랑하는 범우주적 대기업 AI Network의 본사도 화성에 있다. AI Network의 본사는 총 $N$층이고, 역시 궤도 엘리베이터를 사용해 층간 이동을 한다.

오늘 처음으로 이곳에 출근을 한 아인(AIN)이는 기숙사가 있는 $S$층에서 궤도 엘리베이터를 작동시켰고, 회사로부터 전달받은 궤도 엘리베이터 작동 커맨드(Command)를 입력해서 무사히 사무실이 있는 층에 도착했다.

궤도 엘리베이터의 작동 방식은 다음과 같다.

• 엘리베이터는 다양한 속도로 움직일 수 있다. 처음에 엘리베이터의 속도는 $0$이며, 속도는 가속기를 사용해 변화시킬 수 있다. AI Network 본사에는 각 층에 가속기가 하나씩 설치되어 있으며, 이 중 $f$층에 있는 가속기의 성능은 $A_f$이다.
• 엘리베이터는 커맨드를 입력받으면 커맨드를 이루는 각각의 단일 커맨드를 순서대로 처리한다. 단일 커맨드는 엘리베이터가 현재 위치한 층의 가속기를 어떻게 사용할지를 나타내며, 세 가지 종류가 있다. 현재 $f$층에 있고 속도가 $v$인 엘리베이터가 단일 커맨드 하나를 처리하면 다음과 같은 일이 일어난다.
  1. 단일 커맨드의 종류에 따라 엘리베이터의 속도 $v$가 변화한다.
     • 속도 증가(+): $v$를 $A_f$만큼 증가시킨다.
     • 속도 감소(-): $v$를 $A_f$만큼 감소시킨다.
     • 속도 유지(0): $v$를 변화시키지 않는다.
  2. 엘리베이터가 $f+v$층으로 이동한다.
• 엘리베이터는 입력된 커맨드를 처리하기 전에 이를 미리 시뮬레이션한다. 만약, 커맨드를 처리하는 과정에서 엘리베이터가 $1$층에서 $N$층 사이를 벗어나게 되거나 커맨드를 끝까지 처리했을 때 엘리베이터의 속도가 $0$이 되지 않는다면 처음부터 작동이 허가되지 않는다.

퇴근 시간이 되었을 때, 아인이는 자신이 출근하는 커맨드는 받았지만 퇴근하는 커맨드는 받지 못했다는 것을 깨달았다. 아인이가 퇴근도 무사히 할 수 있도록 도와주자.

첫 번째 줄에 AI Network 본사의 총 층수 $N$과 아인이의 기숙사가 있는 층 $S$가 주어진다.

두 번째 줄에 각 층에 있는 가속기의 성능을 나타내는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 주어진다.

세 번째 줄에 아인이가 출근할 때 사용했던 커맨드가 주어진다. 커맨드는 +-0로 이루어진 문자열이며, 각 문자의 의미는 문제에서 설명된 것과 같다.

첫 번째 줄에 입력 형식과 같은 방법으로 사무실이 있는 층에서 아인이의 기숙사가 있는 층으로 퇴근하기 위한 커맨드를 출력한다. 가능한 커맨드가 여러 가지일 경우 그중 아무것이나 출력한다.

• $2 \leq N \leq 100\,000$
• $1 \leq A_i \leq 200\,000$
• 주어지는 커맨드의 길이는 $200\,000$ 이하이다.
• 주어지는 커맨드로 궤도 엘리베이터를 작동시키면 성공적으로 $S$층과는 다른 어느 층에 도착한다.
• 출력하는 커맨드의 길이는 $200\,000$ 이하여야 한다.
• 퇴근이 불가능한 입력은 주어지지 않는다.