전선 연결하기 Batch 컴파일 명령

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

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

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

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

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

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

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

<small>위 3개의 그림 모두 보관함을 위에서 내려다본 모습을 나타낸 것입니다.
(A)는 모든 규칙을 만족합니다.
(B)는 2번 공을 잇는 전선과 3번 공을 잇는 전선이 교차하므로 1번 규칙을 만족하지 않습니다.
(C)는 4번 공을 잇는 전선이 보관함의 위에 있기도 하면서 보관함의 아래에도 있기도 하므로(?) 2번 규칙을 만족하지 않습니다.</small>

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

입력 형식

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

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

출력 형식

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

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

제약 조건

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

부분문제

예제

참고로, 맨 위의 예제는 그림 (A)와 같습니다.