#902 Cryptarithm

Statement

Statement language

A cryptarithm replaces the digits of numbers in an arithmetic expression with letters. Different letters must represent different digits, and every occurrence of the same letter represents the same digit.

You are given the following equation consisting of $N+1$ strings:

\sum_{i=1}^{N}s_i=t

Assign a distinct digit from $0$ to $9$ to every distinct letter so that the equation holds. The first digit of the number represented by any string must not be $0$ . Interpret each converted string as a decimal integer.

If multiple assignments exist, output any one of them.

Input

The input is given in the following format:

$N$ $s_1$ $s_2$

Output

If a valid one-to-one assignment exists, print $N+1$ decimal integers, one per line, corresponding to $s_1,s_2,\cdots,s_N,t$ in this order.

Constraints

$2 \le N \le 10\,000$ .
$1 \le |s_i| \le 18$ ().

Subtasks

#	Score	Constraints
1	30	$N \le 5$ .
2	70	No additional constraints.

Samples

Sample 1

Input

2
A
A
B

Output

1
1
2

Sample 2

Input

2
A
A
A

Output

-1

Sample 3

Input

2
AB
C
AC

Output

10
2
12