#939 Pepero Delivery

Statement

Statement language

Dadas has $N$ Pepero sticks to deliver to Mog. Each stick has one of three types, $1,2,3$ . The original order is $A_1,A_2,\ldots,A_N$ , and Mog wants to receive them in the order $B_1,B_2,\ldots,B_N$ .

There are two initially empty stacks. The following commands are available.

0: Put the next unread input stick onto the first stack.
1: Move the top stick of the first stack onto the second stack.
2: Remove the top stick of the second stack and deliver it to Mog.

Only the last stick placed on a stack may be removed. Command 0 is unavailable when no input sticks remain. Commands 1 and 2 are unavailable when their source stack is empty.

Determine whether every stick can be delivered in the desired order, and if so, construct a command sequence.

Input

The input is given in the following format:

$N$ $A_1\ A_2\ \cdots\ A_N$

Output

If it is impossible, print -1. Otherwise, print a string of length $3N$ listing the commands in execution order. The string must contain only 0, 1, and 2, and every command must be executable when used. The delivery order must be exactly $B_1,B_2,\ldots,B_N$ , and no input or stack contents may remain at the end. If multiple answers exist, print any of them.

Constraints

$1 \leq N \leq 200\ 000$ .
$1 \leq A_i,B_i \leq 3$ ().

Subtasks

#	Score	Constraints
1	20	$N \leq 8$ .
2	25	$A_i,B_i\leq2$ ().

Samples

Sample 1

Input

3
1 2 3
2 1 3

Output

001212012

Sample 2

Input

2
1 1
1 2

Output

-1

Sample 3

Input

1
3
3

Output

012