시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 64 MB189161326.000%

문제

석환이는 "Lightballb"라는 상품을 판매합니다. Lightballb 한 세트에는 두 개의 같은 자연수 번호가 적혀 있는 공이 들어있습니다. 이 공은 평상시에는 공의 역할을 하다가, 같은 번호가 쓰여 있는 두 공을 전선으로 연결하면 전구의 역할을 한다고 합니다.

  1. 같은 번호가 쓰여 있는 두 개의 공이 전선으로 연결되어 있으므로 전구가 켜집니다.
  2. 한 공에 전선이 연결되어 있으므로 전구는 켜지지 않습니다.
  3. 전선이 연결되어 있지 않으므로 전구는 켜지지 않습니다.
  4. 서로 다른 번호가 쓰여 있는 두 개의 공이 전선으로 연결되어 있으므로 전구가 켜지지 않습니다.

승현이는 석환이의 상품이 전혀 팔리지 않는다는 소식을 듣고, 석환이를 돕기 위해 n개의 Lightballb 세트를 구매했습니다. 따라서 승현이는 2n개의 공을 가지고 있으며, 1 이상 n 이하의 모든 자연수 k에 대해 k가 적혀 있는 공은 정확히 2개입니다.

승현이는 방대한 공들을 보관할만한 장소를 찾다가, 아래와 같이 생긴 길쭉한 보관함을 찾고 그 안에 공을 무작위로 넣었습니다.

다음 날, 승현이는 공을 사용하기 위해 보관함에서 공을 꺼내려고 시도했지만, 공들은 꼼짝도 하지 않았습니다! 공이 반짝반짝 빛나는 모습을 보고 싶던 승현이는 절망감에 빠졌습니다. 낙담하고 있던 그 때, 승현이는 전선이 보관함을 뚫고 들어간다는 사실을 알아냈습니다! 승현이는 공들에 전선을 잘 꽂아 모든 공들이 빛나는 모습을 보고자 합니다.

무턱대고 전선을 끼우면 고장이 날 우려가 있기 때문에, 승현이는 미리 전선을 어떻게 연결할지에 대한 계획을 수립하려고 합니다. 우선, 승현이는 보관함과 전선이 움직이는 것을 방지하기 위해, 이들을 반드시 바닥 위에 놓기로 했습니다. 하지만, 이것만으로는 위험에 대비할 수 없다고 생각한 승현이는 다음과 같은 규칙을 세웁니다.

  1. 합선의 우려가 있으므로, 전선끼리 서로 교차하면 안 된다.
  2. 한 전선의 모든 부분은 보관함의 위에 있거나 보관함의 아래에 있어야 한다.

위 3개의 그림 모두 보관함을 위에서 내려다본 모습을 나타낸 것입니다.

  • (A)는 모든 규칙을 만족합니다.
  • (B)는 2번 공을 잇는 전선과 3번 공을 잇는 전선이 교차하므로 1번 규칙을 만족하지 않습니다.
  • (C)는 4번 공을 잇는 전선이 보관함의 위에 있기도 하면서 보관함의 아래에도 있기도 하므로(?) 2번 규칙을 만족하지 않습니다.

승현이는 위 규칙을 만족하면서 전선을 연결하여 모든 공이 빛나도록 할 수 있는 방법이 존재하는지 알고자 합니다. 하지만 전구의 개수가 너무 많아 스스로 해결할 수 없었고, 여러분에게 도움을 요청했습니다. 승현이의 보관함에 적혀 있는 공의 번호가 차례대로 주어질 때, 각 공의 전선이 보관함 위에 있어야 하는지, 아래에 있어야 하는지를 결정하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 자연수 n이 주어집니다.

두 번째 줄에 a1, a2, ..., a2n - 1, a2n이 공백을 사이로 두고 차례대로 주어집니다. 여기서 ai는 승현이의 보관함에서 왼쪽에서부터 i번째에 위치한 공에 적혀 있는 번호를 나타냅니다.

  • 1 ≤ n ≤ 300, 000
  • 모든 i (1 ≤ i ≤ 2n)에 대해, 1 ≤ ai ≤ n
  • 모든 k (1 ≤ k ≤ n)에 대해, k는 수열 a에서 정확히 2번 나타납니다.

 

출력

만약 주어진 조건을 만족하면서 모든 공을 빛나게 하는 방법이 존재하지 않는다면, "IMPOSSIBLE" (따옴표 제외)를 출력합니다.

만약 방법이 존재한다면, 첫 번째 줄에 길이가 2n인 문자열을 출력합니다. 이 중 i (1 ≤ i ≤ 2n)번째 글자는, 왼쪽에서 i번째에 위치한 공에 꽂는 전선이 보관함 위에 있어야 한다면 '^', 보관함 아래에 있어야 한다면 'v'이어야 합니다.

예제 입력 1

4
1 2 3 2 3 1 4 4

예제 출력 1

^^v^v^vv

예제 입력 2

3
1 2 3 3 2 1

예제 출력 2

^^^^^^

예제 입력 3

3
1 2 3 1 2 3

예제 출력 3

IMPOSSIBLE

채점 및 기타 정보

  • 예제는 채점하지 않는다.