시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)43218215952.824%

문제

때는 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$ 이하여야 한다.
  • 퇴근이 불가능한 입력은 주어지지 않는다.

예제 입력 1

6 1
1 1 1 1 1 2
++0-

예제 출력 1

-+00+

먼저, 전달받은 출근 커맨드를 살펴보자.

가속기 성능 커맨드 속도 변화 층 변화
$1$ $1$ + $0 \xrightarrow{+1} 1$ $1 \xrightarrow{+1} 2$
$2$ $1$ + $1 \xrightarrow{+1} 2$ $2 \xrightarrow{+2} 4$
$4$ $1$ 0 $2 \xrightarrow{\pm 0} 2$ $4 \xrightarrow{+2} 6$
$6$ $2$ - $2 \xrightarrow{-2} 0$ $6 \xrightarrow{\pm 0} 6$

모든 커맨드가 처리되고 난 후 $6$층에 속도 $0$으로 도착했음을 알 수 있다.

이제 예시로 주어진 퇴근 커맨드를 살펴보자.

가속기 성능 커맨드 속도 변화 층 변화
$6$ $2$ - $0 \xrightarrow{-2} -2$ $6 \xrightarrow{-2} 4$
$4$ $1$ + $-2 \xrightarrow{+1} -1$ $4 \xrightarrow{-1} 3$
$3$ $1$ 0 $-1 \xrightarrow{\pm 0} -1$ $3 \xrightarrow{-1} 2$
$2$ $1$ 0 $-1 \xrightarrow{\pm 0} -1$ $2 \xrightarrow{-1} 1$
$1$ $1$ + $-1 \xrightarrow{+1} 0$ $1 \xrightarrow{\pm 0} 1$

해당 커맨드로 $6$층에서 $1$층으로 무사히 퇴근할 수 있음을 알 수 있다.

예제 입력 2

10 3
5 3 2 7 1 4 3 1 6 5
++--+

예제 출력 2

-0+-

출처

Contest > AI Network Scholarium > AI Network Scholarium I A번