D - Send More Money Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 400

問題文

英小文字からなる文字列 S_1,S_2,S_3 が与えられます。覆面算 S_1+S_2=S_3 を解いてください。

正確には、次の 3 つの条件をすべて満たすような正の整数の組 N_1,N_2,N_3 が存在するか判定し、存在するならばそのうち 1 つを求めてください。
ここで、N_1, N_2, N_3 を (先頭に余分な 0 をつけないで) 十進表記した文字列をそれぞれ N'_1, N'_2, N'_3 とします。

  • N'_i の文字数は、S_i の文字数に等しい
  • N_1+N_2=N_3 を満たす
  • S_ix 文字目と S_jy 文字目が等しいとき、またその時に限り、N'_ix 文字目と N'_jy 文字目が等しい

制約

  • S_1,S_2,S_3 は英小文字のみからなる長さ 1 以上 10 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

S_1
S_2
S_3

出力

条件を満たすような正整数の組 N_1,N_2,N_3 が存在するならば、そのような組の 1 つを改行区切りで出力せよ。 存在しないなら、代わりに UNSOLVABLE と出力せよ。


入力例 1

a
b
c

出力例 1

1
2
3

(N_1, N_2, N_3) = (4,5,9) などを出力しても正解となります。(1,1,2)3 つ目の条件を満たしていない (a,b がともに 1 に対応している) ため、不正解となります。


入力例 2

x
x
y

出力例 2

1
1
2

(N_1, N_2, N_3) = (3,3,6) などを出力しても正解となります。(1,2,3)3 つ目の条件を満たしていない (1,2 がともに x に対応している) ため、不正解となります。


入力例 3

p
q
p

出力例 3

UNSOLVABLE

入力例 4

abcd
efgh
ijkl

出力例 4

UNSOLVABLE

入力例 5

send
more
money

出力例 5

9567
1085
10652

Score : 400 points

Problem Statement

Given strings S_1,S_2,S_3 consisting of lowercase English letters, solve the alphametic S_1+S_2=S_3.

Formally, determine whether there is a triple of positive integers N_1, N_2, N_3 satisfying all of the three conditions below, and find one such triple if it exists.
Here, N'_1, N'_2, N'_3 are strings representing N_1, N_2, N_3 (without leading zeros) in base ten, respectively.

  • N'_i and S_i have the same number of characters.
  • N_1+N_2=N_3.
  • The x-th character of S_i and the y-th character of S_j is the same if and only if the x-th character of N'_i and the y-th character of N'_j are the same.

Constraints

  • Each of S_1, S_2, S_3 is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S_1
S_2
S_3

Output

If there is a triple of positive integers N_1, N_2, N_3 satisfying the conditions, print one such triple, using newline as a separator. Otherwise, print UNSOLVABLE instead.


Sample Input 1

a
b
c

Sample Output 1

1
2
3

Outputs such as (N_1, N_2, N_3) = (4,5,9) will also be accepted, but (1,1,2) will not since it violates the third condition (both a and b correspond to 1).


Sample Input 2

x
x
y

Sample Output 2

1
1
2

Outputs such as (N_1, N_2, N_3) = (3,3,6) will also be accepted, but (1,2,3) will not since it violates the third condition (both 1 and 2 correspond to x).


Sample Input 3

p
q
p

Sample Output 3

UNSOLVABLE

Sample Input 4

abcd
efgh
ijkl

Sample Output 4

UNSOLVABLE

Sample Input 5

send
more
money

Sample Output 5

9567
1085
10652