using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("a");
WillReturn.Add("b");
WillReturn.Add("c");
//1
//2
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("x");
WillReturn.Add("x");
WillReturn.Add("y");
//1
//1
//2
}
else if (InputPattern == "Input3") {
WillReturn.Add("p");
WillReturn.Add("q");
WillReturn.Add("p");
//UNSOLVABLE
}
else if (InputPattern == "Input4") {
WillReturn.Add("abcd");
WillReturn.Add("efgh");
WillReturn.Add("ijkl");
//UNSOLVABLE
}
else if (InputPattern == "Input5") {
WillReturn.Add("send");
WillReturn.Add("more");
WillReturn.Add("money");
//9567
//1085
//10652
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int UB_X;
static int UB_Y;
static HashSet<char> mNonUseZeroSet = new HashSet<char>();
static void Main()
{
List<string> InputList = GetInputList();
string S1 = InputList[0];
string S2 = InputList[1];
string S3 = InputList[2];
var AppearCharSet = new HashSet<char>();
AppearCharSet.UnionWith(S1);
AppearCharSet.UnionWith(S2);
AppearCharSet.UnionWith(S3);
// 1対1に対応するので、10文字以上あったらNG
if (AppearCharSet.Count > 10) {
Console.WriteLine("UNSOLVABLE");
return;
}
// 0を使えないcharのSet
mNonUseZeroSet.Add(S1[0]);
mNonUseZeroSet.Add(S2[0]);
mNonUseZeroSet.Add(S3[0]);
// 前ゼロを補完する
int MaxLen = Math.Max(S1.Length, S2.Length);
MaxLen = Math.Max(MaxLen, S3.Length);
S1 = S1.PadLeft(MaxLen, '0');
S2 = S2.PadLeft(MaxLen, '0');
S3 = S3.PadLeft(MaxLen, '0');
// 二次元配列を作成
var StringList = new List<string>() { S1, S2, S3 };
char[,] BanArr = CreateBanArr(StringList);
UB_X = BanArr.GetUpperBound(0);
UB_Y = BanArr.GetUpperBound(1);
Solve(BanArr);
}
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal char[,] BanArr;
internal HashSet<char> UseNumSet;
}
static void Solve(char[,] pBanArr)
{
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = UB_X;
WillPush.CurrY = 0;
WillPush.BanArr = pBanArr;
WillPush.UseNumSet = new HashSet<char>();
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
// 繰り上がりの対応
if (Popped.CurrY > UB_Y) {
// 無効な盤面なら枝切り
if (IsValid(Popped.BanArr, Popped.CurrX, true) == false) {
continue;
}
Popped.CurrX--;
Popped.CurrY = 0;
}
if (Popped.CurrX < 0) {
if (IsValid(Popped.BanArr, 0, false)) {
PrintAnswer(Popped.BanArr);
return;
}
continue;
}
char CurrChar = Popped.BanArr[Popped.CurrX, Popped.CurrY];
WillPush.CurrX = Popped.CurrX;
WillPush.CurrY = Popped.CurrY + 1;
// 既に決定している場合
if ('0' <= CurrChar && CurrChar <= '9') {
WillPush.BanArr = Popped.BanArr;
WillPush.UseNumSet = Popped.UseNumSet;
Stk.Push(WillPush);
continue;
}
// 未決定の文字の場合
for (char I = '0'; I <= '9'; I++) {
if (Popped.UseNumSet.Contains(I)) continue;
if (I == '0' && mNonUseZeroSet.Contains(CurrChar)) continue;
char[,] NewBanArr = (char[,])Popped.BanArr.Clone();
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (NewBanArr[LoopX, LoopY] == CurrChar) {
NewBanArr[LoopX, LoopY] = I;
}
}
}
WillPush.BanArr = NewBanArr;
WillPush.UseNumSet = new HashSet<char>(Popped.UseNumSet);
WillPush.UseNumSet.Add(I);
Stk.Push(WillPush);
}
}
Console.WriteLine("UNSOLVABLE");
}
// 盤面を引数として解を出力する
static void PrintAnswer(char[,] pBanArr)
{
Func<int, string> GetLineAllStrFunc = pY =>
{
var CharList = new List<char>();
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
CharList.Add(pBanArr[LoopX, pY]);
}
return new string(CharList.ToArray());
};
string S1 = GetLineAllStrFunc(0);
string S2 = GetLineAllStrFunc(1);
string S3 = GetLineAllStrFunc(2);
// 前ゼロは消す
S1 = Regex.Replace(S1, "^0+", "");
S2 = Regex.Replace(S2, "^0+", "");
Console.WriteLine(S1);
Console.WriteLine(S2);
Console.WriteLine(S3);
}
// XStaIndからUB_Xまでの、足し算で、有効盤面かを返す
static bool IsValid(char[,] pBanArr, int pXStaInd, bool pEnableCut)
{
int StrLen = UB_X - pXStaInd + 1;
Func<int, string> GetLinePartStrFunc = pY =>
{
var CharList = new List<char>();
for (int LoopX = pXStaInd; LoopX <= UB_X; LoopX++) {
CharList.Add(pBanArr[LoopX, pY]);
}
return new string(CharList.ToArray());
};
string S1 = GetLinePartStrFunc(0);
string S2 = GetLinePartStrFunc(1);
string S3 = GetLinePartStrFunc(2);
long S1Long = long.Parse(S1);
long S2Long = long.Parse(S2);
long S3Long = long.Parse(S3);
// 指定桁に10進数をカットする
Func<int, long, long> CutFunc = (pKeta, pVal) =>
{
if (pKeta == 1) return pVal % 10;
if (pKeta == 2) return pVal % 100;
if (pKeta == 3) return pVal % 1000;
if (pKeta == 4) return pVal % 10000;
if (pKeta == 5) return pVal % 100000;
if (pKeta == 6) return pVal % 1000000;
if (pKeta == 7) return pVal % 10000000;
if (pKeta == 8) return pVal % 100000000;
if (pKeta == 9) return pVal % 1000000000;
return pVal % 10000000000;
};
long Sum = S1Long + S2Long;
// 指定桁までしか見ない場合
if (pEnableCut) {
Sum = CutFunc(StrLen, Sum);
S3Long = CutFunc(StrLen, S3Long);
}
return Sum == S3Long;
}
// stringのListをcharの2次元配列に設定する
static char[,] CreateBanArr(List<string> pStringList)
{
if (pStringList.Count == 0) {
return new char[0, 0];
}
int UB_X = pStringList[0].Length - 1;
int UB_Y = pStringList.Count - 1;
char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = pStringList[Y][X];
}
}
return WillReturn;
}
// 2次元配列のデバッグ出力
static void PrintBan(char[,] pBanArr)
{
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
Console.Write(pBanArr[X, Y]);
}
Console.WriteLine();
}
}
}