import java.util.Arrays;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
class Alphametic
{
public static void main
(String[] args
) {
try (Scanner in
= new Scanner
(System.
in)) {
while (in.hasNextLine())
{
new Alphametic(in.nextLine()).print();
}
}
}
private static Pattern pat = Pattern.compile("([0-9A-Z]+)([+-\\\\*])([0-9A-Z]+)=([0-9A-Z]+)");
private final Op operator;
private final int e;
private final int[] map = new int[256];
private final boolean[] used = new boolean[10];
private Alphametic
(String exp
) {
Matcher mat = pat.matcher(exp);
this.sa = mat.group(1);
this.op = mat.group(2);
this.sb = mat.group(3);
this.sc = mat.group(4);
this.
st = new String[] { sa, sb, sc
}; switch(op)
{
case "+": operator = (a, b) -> a + b; break;
case "-": operator = (a, b) -> a - b; break;
case "*": operator = (a, b) -> a * b; break;
}
// ここから
used[0] = true;
used[3] = true;
used[4] = true;
// ここまで追加
for (int i = 0; i <= 9; i++) map['0' + i] = i;
for (int i = 'A'; i <= 'Z'; i++) map[i] = i;
e
= Math.
max(Math.
max(sa.
length(), sb.
length()), sc.
length()) * 3; solve(0, new long[3], 1);
}
private void solve(int p, long[] ls, long d)
{
if (p == e)
{
if (!operator.
test(ls
[0], ls
[1], ls
[2],
Long.
MAX_VALUE)) return; for (String s
: st
) if (map
[s.
charAt(0)] <= 0) return; result
= Arrays.
copyOf(result, result.
length + 1); result
[result.
length - 1] = String.
format("%d%s%d=%d", ls
[0], op, ls
[1], ls
[2]); return;
}
int i = p / 3;
int j = p % 3;
if (p > 0 && j == 0)
{
d *= 10;
if (!operator.test(ls[0], ls[1], ls[2], d)) return;
}
int n = ch(st[j], i);
long l = ls[j];
if (n >= 'A' && n <= 'Z')
{
for (int k = 0; k < 10; k++)
{
if (used[k]) continue;
used[k] = true;
map[n] = k;
ls[j] = l + k * d;
solve(p + 1, ls, d);
used[k] = false;
}
map[n] = n;
}
else
{
ls[j] += n * d;
solve(p + 1, ls, d);
}
ls[j] = l;
}
private int ch
(String s,
int i
) {
return s.length() <= i ? 0 : map[s.charAt(s.length() - i - 1)];
}
void print()
{
System.
out.
printf("%s%s%s=%s%n", sa, op, sb, sc
); }
private interface Op
{
long op(long a, long b);
default boolean test(long a, long b, long c, long d)
{
return Math.
abs(op
(a, b
) - c
) % d
== 0; }
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheXM7CmltcG9ydCBqYXZhLnV0aWwuU2Nhbm5lcjsKaW1wb3J0IGphdmEudXRpbC5yZWdleC5NYXRjaGVyOwppbXBvcnQgamF2YS51dGlsLnJlZ2V4LlBhdHRlcm47CiAKY2xhc3MgQWxwaGFtZXRpYwp7CiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKQogICAgewogICAgICAgIHRyeSAoU2Nhbm5lciBpbiA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbikpCiAgICAgICAgewogICAgICAgICAgICB3aGlsZSAoaW4uaGFzTmV4dExpbmUoKSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbmV3IEFscGhhbWV0aWMoaW4ubmV4dExpbmUoKSkucHJpbnQoKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KIAogICAgcHJpdmF0ZSBzdGF0aWMgUGF0dGVybiBwYXQgPSBQYXR0ZXJuLmNvbXBpbGUoIihbMC05QS1aXSspKFsrLVxcXFwqXSkoWzAtOUEtWl0rKT0oWzAtOUEtWl0rKSIpOwogICAgcHJpdmF0ZSBmaW5hbCBTdHJpbmcgc2E7CiAgICBwcml2YXRlIGZpbmFsIFN0cmluZyBzYjsKICAgIHByaXZhdGUgZmluYWwgU3RyaW5nIHNjOwogICAgcHJpdmF0ZSBmaW5hbCBTdHJpbmcgb3A7CiAgICBwcml2YXRlIGZpbmFsIFN0cmluZ1tdIHN0OwogICAgcHJpdmF0ZSBmaW5hbCBPcCBvcGVyYXRvcjsKICAgIHByaXZhdGUgZmluYWwgaW50IGU7CiAKICAgIHByaXZhdGUgZmluYWwgaW50W10gbWFwID0gbmV3IGludFsyNTZdOwogICAgcHJpdmF0ZSBmaW5hbCBib29sZWFuW10gdXNlZCA9IG5ldyBib29sZWFuWzEwXTsKICAgIHByaXZhdGUgU3RyaW5nW10gcmVzdWx0ID0gbmV3IFN0cmluZ1swXTsKIAogICAgcHJpdmF0ZSBBbHBoYW1ldGljKFN0cmluZyBleHApCiAgICB7CiAgICAgICAgTWF0Y2hlciBtYXQgPSBwYXQubWF0Y2hlcihleHApOwogICAgICAgIGlmICghbWF0Lm1hdGNoZXMoKSkgdGhyb3cgbmV3IElsbGVnYWxBcmd1bWVudEV4Y2VwdGlvbigpOwogCiAgICAgICAgdGhpcy5zYSA9IG1hdC5ncm91cCgxKTsKICAgICAgICB0aGlzLm9wID0gbWF0Lmdyb3VwKDIpOwogICAgICAgIHRoaXMuc2IgPSBtYXQuZ3JvdXAoMyk7CiAgICAgICAgdGhpcy5zYyA9IG1hdC5ncm91cCg0KTsKICAgICAgICB0aGlzLnN0ID0gbmV3IFN0cmluZ1tdIHsgc2EsIHNiLCBzYyB9OwogICAgICAgIHN3aXRjaChvcCkKICAgICAgICB7CiAgICAgICAgY2FzZSAiKyI6IG9wZXJhdG9yID0gKGEsIGIpIC0+IGEgKyBiOyBicmVhazsKICAgICAgICBjYXNlICItIjogb3BlcmF0b3IgPSAoYSwgYikgLT4gYSAtIGI7IGJyZWFrOwogICAgICAgIGNhc2UgIioiOiBvcGVyYXRvciA9IChhLCBiKSAtPiBhICogYjsgYnJlYWs7CiAgICAgICAgZGVmYXVsdDogdGhyb3cgbmV3IElsbGVnYWxBcmd1bWVudEV4Y2VwdGlvbigpOwogICAgICAgIH0KCiAgICAgICAgLy8g44GT44GT44GL44KJCiAgICAgICAgdXNlZFswXSA9IHRydWU7CiAgICAgICAgdXNlZFszXSA9IHRydWU7CiAgICAgICAgdXNlZFs0XSA9IHRydWU7CiAgICAgICAgLy8g44GT44GT44G+44Gn6L+95YqgCiAKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8PSA5OyBpKyspIG1hcFsnMCcgKyBpXSA9IGk7CiAgICAgICAgZm9yIChpbnQgaSA9ICdBJzsgaSA8PSAnWic7IGkrKykgbWFwW2ldID0gaTsKICAgICAgICBlID0gTWF0aC5tYXgoTWF0aC5tYXgoc2EubGVuZ3RoKCksIHNiLmxlbmd0aCgpKSwgc2MubGVuZ3RoKCkpICogMzsKICAgICAgICBzb2x2ZSgwLCBuZXcgbG9uZ1szXSwgMSk7CiAgICB9CiAKICAgIHByaXZhdGUgdm9pZCBzb2x2ZShpbnQgcCwgbG9uZ1tdIGxzLCBsb25nIGQpCiAgICB7CiAgICAgICAgaWYgKHAgPT0gZSkKICAgICAgICB7CiAgICAgICAgICAgIGlmICghb3BlcmF0b3IudGVzdChsc1swXSwgbHNbMV0sIGxzWzJdLCBMb25nLk1BWF9WQUxVRSkpIHJldHVybjsKICAgICAgICAgICAgZm9yIChTdHJpbmcgcyA6IHN0KSBpZiAobWFwW3MuY2hhckF0KDApXSA8PSAwKSByZXR1cm47CiAgICAgICAgICAgIHJlc3VsdCA9IEFycmF5cy5jb3B5T2YocmVzdWx0LCByZXN1bHQubGVuZ3RoICsgMSk7CiAgICAgICAgICAgIHJlc3VsdFtyZXN1bHQubGVuZ3RoIC0gMV0gPSBTdHJpbmcuZm9ybWF0KCIlZCVzJWQ9JWQiLCBsc1swXSwgb3AsIGxzWzFdLCBsc1syXSk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAKICAgICAgICBpbnQgaSA9IHAgLyAzOwogICAgICAgIGludCBqID0gcCAlIDM7CiAgICAgICAgaWYgKHAgPiAwICYmIGogPT0gMCkKICAgICAgICB7CiAgICAgICAgICAgIGQgKj0gMTA7CiAgICAgICAgICAgIGlmICghb3BlcmF0b3IudGVzdChsc1swXSwgbHNbMV0sIGxzWzJdLCBkKSkgcmV0dXJuOwogICAgICAgIH0KIAogICAgICAgIGludCBuID0gY2goc3Rbal0sIGkpOwogICAgICAgIGxvbmcgbCA9IGxzW2pdOwogCiAgICAgICAgaWYgKG4gPj0gJ0EnICYmIG4gPD0gJ1onKQogICAgICAgIHsKICAgICAgICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCAxMDsgaysrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZiAodXNlZFtrXSkgY29udGludWU7CiAgICAgICAgICAgICAgICB1c2VkW2tdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIG1hcFtuXSA9IGs7CiAgICAgICAgICAgICAgICBsc1tqXSA9IGwgKyBrICogZDsKICAgICAgICAgICAgICAgIHNvbHZlKHAgKyAxLCBscywgZCk7CiAgICAgICAgICAgICAgICB1c2VkW2tdID0gZmFsc2U7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgbWFwW25dID0gbjsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgbHNbal0gKz0gbiAqIGQ7CiAgICAgICAgICAgIHNvbHZlKHAgKyAxLCBscywgZCk7CiAgICAgICAgfQogICAgICAgIGxzW2pdID0gbDsKICAgIH0KIAogICAgcHJpdmF0ZSBpbnQgY2goU3RyaW5nIHMsIGludCBpKQogICAgewogICAgICAgIHJldHVybiBzLmxlbmd0aCgpIDw9IGkgPyAwIDogbWFwW3MuY2hhckF0KHMubGVuZ3RoKCkgLSBpIC0gMSldOwogICAgfQogCiAgICB2b2lkIHByaW50KCkKICAgIHsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50ZigiJXMlcyVzPSVzJW4iLCBzYSwgb3AsIHNiLCBzYyk7CiAgICAgICAgZm9yIChTdHJpbmcgcyA6IHJlc3VsdCkgU3lzdGVtLm91dC5wcmludGxuKHMpOwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigpOwogICAgfQogCiAgICBwcml2YXRlIGludGVyZmFjZSBPcAogICAgewogICAgICAgIGxvbmcgb3AobG9uZyBhLCBsb25nIGIpOwogCiAgICAgICAgZGVmYXVsdCBib29sZWFuIHRlc3QobG9uZyBhLCBsb25nIGIsIGxvbmcgYywgbG9uZyBkKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIE1hdGguYWJzKG9wKGEsIGIpIC0gYykgJSBkID09IDA7CiAgICAgICAgfQogICAgfQp9