전선 연결하기

석환이는 "Lightballb"라는 상품을 판매합니다. Lightballb 한 세트에는 같은 자연수가 적힌 공이 두 개 들어 있습니다. 이 공은 평소에 그냥 공이지만, 같은 번호가 적힌 두 공을 전선으로 이으면 전구가 됩니다.

1. 같은 번호가 적힌 두 공이 전선으로 이어져 있으므로 전구가 켜집니다.
2. 한쪽 공에만 전선이 꽂혀 있으므로 전구가 켜지지 않습니다.
3. 전선이 꽂혀 있지 않으므로 전구가 켜지지 않습니다.
4. 서로 다른 번호가 적힌 두 공이 이어져 있으므로 전구가 켜지지 않습니다.

승현이는 석환이의 상품이 전혀 팔리지 않는다는 소식을 듣고, 석환이를 도우려고 Lightballb 세트를 $n$개 샀습니다. 그래서 승현이는 공을 $2n$개 가지고 있고, $1$ 이상 $n$ 이하의 모든 자연수 $k$에 대해 $k$가 적힌 공은 정확히 두 개입니다.

승현이는 이 많은 공을 보관할 곳을 찾다가 아래처럼 길쭉한 보관함을 발견하고, 그 안에 공을 아무렇게나 넣었습니다.

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

무턱대고 전선을 끼우면 고장이 날 수 있으므로, 승현이는 전선을 어떻게 이을지 미리 계획합니다. 우선 보관함과 전선이 움직이지 않도록 둘 다 바닥 위에 놓기로 했습니다. 이것만으로는 위험에 대비할 수 없다고 생각한 승현이는 다음 두 규칙을 세웁니다.

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

위 세 그림은 모두 보관함을 위에서 내려다본 모습입니다.

• (A)는 두 규칙을 모두 만족합니다.
• (B)는 2번 공을 잇는 전선과 3번 공을 잇는 전선이 교차하므로 규칙 1을 어깁니다.
• (C)는 4번 공을 잇는 전선이 보관함의 위와 아래에 걸쳐 있으므로 규칙 2를 어깁니다.

보관함에 들어 있는 공의 번호가 왼쪽부터 차례대로 주어집니다. 두 규칙을 지키면서 모든 공을 빛나게 할 수 있는지 판정하고, 할 수 있다면 각 공의 전선을 보관함 위에 둘지 아래에 둘지 정하는 프로그램을 작성하세요.

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

둘째 줄에 $a_1, a_2, \dots, a_{2n}$이 공백을 사이에 두고 차례대로 주어집니다. $a_i$는 보관함에서 왼쪽부터 $i$번째에 있는 공에 적힌 번호입니다.

• $1 \le n \le 300000$
• 모든 $i$ ($1 \le i \le 2n$)에 대해 $1 \le a_i \le n$
• 모든 $k$ ($1 \le k \le n$)에 대해 $k$는 수열 $a$에 정확히 두 번 나타납니다.

두 규칙을 지키면서 모든 공을 빛나게 하는 방법이 없으면 첫째 줄에 따옴표 없이 IMPOSSIBLE을 출력합니다.

방법이 있으면 첫째 줄에 길이가 $2n$인 문자열을 출력합니다. 이 문자열의 $i$번째 ($1 \le i \le 2n$) 글자는, 왼쪽부터 $i$번째에 있는 공에 꽂는 전선이 보관함 위에 있어야 하면 ^, 보관함 아래에 있어야 하면 v입니다.

두 규칙을 지키는 문자열이 여러 개면 그중 사전순으로 가장 앞서는 문자열 하나만 출력합니다. 문자 비교는 아스키 코드 순서를 따르므로 ^(0x5E)가 v(0x76)보다 앞섭니다.