/* Import the Java I/O package */
import java.io.*;
import AppletConsoleApp;

/**
 * Solution to the 1998 British Informatics Olympiad exam
 * question 3: Alphametics
 *
 * Reads 3 to 6 lines of up to 6 characters each forming a sum (with
 * the last line as the total); each character represents a different
 * digit.  Let there be N lines and M characters.  Write the nth line
 * as Wn1 * X1 + ... + WnM * XM where Xm is the value assigned to
 * character m.  The solution is therefore to find appropriate X1..XM
 * satisfying W1 * X1 + ... + WM * XM = 0, where
 * Wm = W1m + W(N-1)m - WNm.  Solution vectors lie in the M-1
 * dimensional space that is orthogonal to W; additionally, if all
 * elements of a solution are less than or equal to 4, it can be
 * doubled, or if less than or equal to 3, it can also be tripled,
 * if less than or equal to 2, quadrupled.
 *
 * This representation is fast enough for exhaustive search of all
 * 10! combinations.
 *
 * This application that can be run either from the console
 * as a stand-alone application or from an in-applet
 * console created with the AppletConsole applet.
 *
 * Solution copyright (c) 1998 The British Informatics Olympiad (BIO).
 *
 * This program may be freely copied by persons or organisations
 * involved in the British Informatics Olympiad or the International
 * Olympiad in Informatics, on condition that no changes are made and
 * this notice is not altered. Distribution for profit is forbidden
 * unless permission is first obtained in writing from the BIO.
 *
 * This program is for educational purposes only and comes with no
 * warranty, implied or otherwise, as to its fitness for any purpose.
 *
 * Author:   Antony Rix
 * Internet: http://www.christs.cam.ac.uk/bio/
 * E-mail:   a.rix@lineone.net
 * S-mail:   The British Informatics Olympiad
 *           Christ's College
 *           Cambridge CB2 3BU
 *           United Kingdom
 *
 * @author  Antony Rix
 * @version 0.1
 * @see     AppletConsoleApp
 * @see     AppletConsole
 */
class BIO98R1Q3App extends AppletConsoleApp {
  /**
   * Start the application from the command line.
   */
  public static void main(String[] args) {
	  BIO98R1Q3App thisApp = new BIO98R1Q3App();
	  thisApp.redirectStreams(System.in, System.out);
	  thisApp.run();
	}

  /**
   * Data structure to store the lines to be summed
   */
  char[][] alphametic = new char[6][10];

  /**
   *  Number of lines
   */
  int N;

  /**
   *  Number of characters
   */
  int M;

  /**
   * Characters in the alphametic.
   */
  String Letters;
  
  /**
   * Weights of solution equation (use long as its accuracy,
   * 64 bits, is higher than int).
   */
  long[] W = new long[10];

  /**
   * Solution.
   */
  long[] X = new long[10];

  /**
   * Whether a specific digit has been allocated
   */
  boolean[] allocDigit = new boolean[10];

  /**
   * Number of solutions found
   */
  int S;

  /**
   * Number of valid combinations (for 3(d))
   */
  int P;
  
  /**
   * The implementation of this application.
   */
	public void run() {
    int i, j, L;
    
    try {
      out.println( "BIO'98 Question 3" );
  	  /* Create a StreamTokenizer to allow us to read in the two numbers */
  	  StreamTokenizer sin = new StreamTokenizer( in );

  	  /* Read in initial co-ordinates */
      out.print( "Number of lines:" );
	    sin.nextToken();
	    N = (int)sin.nval;
	    if( (N > 6) || (N < 3) ) {
	      if( N == -1 ) {
	        out.println( "Solution to 3(d)" );
	        try3d();
	      } else out.println( "Expected between 3 and 6 lines" );
	    } else {
  	    for( i = 0; i < N; i++ ) {
	        out.print( "Line " + (i+1) + ":" );
  	      sin.nextToken();
  	      for( j = 0; j < 10; j++ ) alphametic[i][j] = ' ';
  	      L = sin.sval.length();
    	    for( j = 1; j <= L; j++ )
    	      alphametic[i][L-j] = sin.sval.charAt( j - 1 );
	      }

        /* Compute solutions */
  	    tryMatch();
  	    if( S == 0 ) out.println( "Impossible" );
  	    if( S == 1 ) out.println( "Unique" );
  	  }
  	} catch (IOException e) { out.println("I/O failure"); };
	  out.println( "Program finished." );
	}

	/**
	 * Solution of the alphametic.  tryMatch() first converts
	 * alphametic[] to the weights form, then generates all
	 * permutations of X and trys them for a solution.
	 * Finally, solutions are verified using checkSolution()
	 * which discards those with leading zeros and displays
	 * and counts the rest.
	 */
	void tryMatch() {
	  int p, i, j, m;
	  long Sum, digit;
	  char c;

    /* Initialise the data */
    for( j = 0; j < 10; j++ ) {
      W[j] = 0L;
      X[j] = 0L;
      allocDigit[j] = false;
    }
    S = 0;
    Letters = "";
    M = 0;

    /* Find the different letters in the alphametic and their weights */
    for( i = 0; i < N; i++ ) {
      digit = 1L;
      for( j = 0; j < 10; j++ ) {
        c = alphametic[i][j];
        if( c != ' ' ) {
          m = Letters.indexOf( c );
          if( m < 0 ) {
            Letters = Letters + c;
            m = M;
            M++;
          }
          if( i < (N-1) ) W[m] += digit; else W[m] -= digit;
        }
        digit *= 10L;
      }
    }

    /* Generate possible solutions */
	  X[0] = 0;
	  Sum = 0L;
	  p = 0;
	  while( X[0] < 10 ) {
	    if( p == M ) {
	      if( Sum == 0L ) checkSolution();
	      p--;
	      allocDigit[(int)X[p]] = false;
	      Sum -= X[p] * W[p];
	      X[p]++;
	    }
      if( X[p] >= 10 ) {
        p--;
        if( p >= 0 ) {
  	      allocDigit[(int)X[p]] = false;
  	      Sum -= X[p] * W[p];
          X[p]++;
        }
        continue;
      }
      if( !allocDigit[(int)X[p]] ) {
        allocDigit[(int)X[p]] = true;
        Sum += X[p] * W[p];
        p++;
        if(p < M ) X[p] = 0;
      }
      else X[p]++;
	  }
	}

	/**
	 * Check a candidate solution
	 */
	void checkSolution() {
	  String answer = "";
	  int i, j;
	  for( i = 0; i < N; i++ ) {
	    if( i == 0 ) answer = " ";
	    else if( i < (N-1) ) answer = answer + " + ";
	    else answer = answer + " = ";
	    for( j = 9; j >= 0; j-- ) if( alphametic[i][j] != ' ' )
	      answer = answer +
	        ((char)(X[Letters.indexOf(alphametic[i][j])]+48L));
	  }
	  if( answer.indexOf( " 0" ) < 0 ) {
	    /* This is a valid solution */
	    out.println( answer );
	    S++;
	  }
	}

  /**
   * Solution to 3(d): ABC + DEA = X where X contains only
   * the letters A to E and forms a valid sum.
   * (i) How many letter combinations for X result in solutions?
   * (ii) How many different sums are represented?
   * For (i), there can be no more than 5^4 + 5*3 = 750
   * valid combinations (in fact there will be rather less);
   * we pre-compute the 750 candidate combinations
   */
	void try3d() {
	  long[][] Ws = new long[5][750];
	  int[] leftMostLetter = new int[750];
	  String[] solutions = new String[750];
	  boolean[] isValid = new boolean[750];
	  boolean solved;
	  int i, j, k, l, p, count, validCombinations, differentSums;
	  long Sum;
	  
	  Letters = "ABCDE";
	  M = 5;
	  /* Weights for ABC + DEA for these Letters */
	  W[0] = 101L;
	  W[1] = 10L;
	  W[2] = 1L;
	  W[3] = 100L;
	  W[4] = 10L;

	  /* Generate actual weights for each candidate combination */
	  for( i = 0; i < 10; i++ ) allocDigit[i] = false;
	  count = 0;
	  for( i = 0; i < M; i++ )
	    for( j = 0; j < M; j++ )
	      for( k = 0; k < M; k++ )
	        for( l = 0; l < M; l++ ) {
    	      /* i,j,k,l contains a permutation of 4 letters A to E */
    	      solutions[count] = "" +
    	        Letters.charAt( i ) + 
    	        Letters.charAt( j ) + 
    	        Letters.charAt( k ) + 
    	        Letters.charAt( l );
    	      leftMostLetter[ count ] = i;
    	      for( p = 0; p < M; p++ ) Ws[p][count] = W[p];
    	      Ws[i][count] -= 1000L;
    	      Ws[j][count] -= 100L;
    	      Ws[k][count] -= 10L;
    	      Ws[l][count] -= 1L;
    	      count++;
	        }
	  for( i = 0; i < M; i++ )
	    for( j = 0; j < M; j++ )
	      for( k = 0; k < M; k++ ) {
  	      /* i,j,k contains a permutation of 3 letters A to E */
  	      solutions[count] = "" +
  	        Letters.charAt( i ) + 
  	        Letters.charAt( j ) + 
  	        Letters.charAt( k );
  	      leftMostLetter[ count ] = i;
  	      for( p = 0; p < M; p++ ) Ws[p][count] = W[p];
  	      Ws[i][count] -= 100L;
  	      Ws[j][count] -= 10L;
  	      Ws[k][count] -= 1L;
  	      count++;
        }

    /* Investigate if the permutations solve the problem */
    validCombinations = 0;
    differentSums = 0;
    for( i = 0; i < count; i++ ) isValid[i] = false;
    for( j = 0; j < M; j++ ) {
      X[j] = 0L;
      allocDigit[j] = false;
    }

    /* Generate possible solutions */
	  X[0] = 0;
	  p = 0;
	  while( X[0] < 10 ) {
	    if( p == M ) {
	      /* Check if X contains a solution */
	      solved = false;
	      for( k = 0; k < count; k++ ) {
	        Sum = 0L;
  	      for( i = 0; i < M; i++ ) Sum += Ws[i][k] * X[i];
  	      if( (Sum == 0L) && (X[0] != 0L) && (X[3] != 0L) &&
  	          (X[leftMostLetter[k]] != 0L) ) {
  	        solved = true;
  	        isValid[k] = true;
  	        out.print( "ABC + DEA = " + solutions[k] );
  	        if( solutions[k].length() > 3 )
  	          out.print( " => " );
  	        else
  	          out.print( "  => " );
  	        out.print( X[0] );
            out.print( X[1] );
  	        out.print( X[2] + " + " + X[3] );
  	        out.print( X[4] );
  	        out.print( X[0] + " = " );
  	        out.print( X[(char)solutions[k].charAt( 0 ) - 65] );
  	        out.print( X[(char)solutions[k].charAt( 1 ) - 65] );
  	        out.print( X[(char)solutions[k].charAt( 2 ) - 65] );
  	        if( solutions[k].length() > 3 )
    	        out.println( X[(char)solutions[k].charAt( 3 ) - 65] );
    	      else
      	      out.println( " " );
  	      }
  	    }
  	    if( solved ) differentSums++;
	      p--;
	      allocDigit[(int)X[p]] = false;
	      X[p]++;
	    }
      if( X[p] >= 10 ) {
        p--;
        if( p >= 0 ) {
  	      allocDigit[(int)X[p]] = false;
          X[p]++;
        }
        continue;
      }
      if( !allocDigit[(int)X[p]] ) {
        allocDigit[(int)X[p]] = true;
        p++;
        if(p < M ) X[p] = 0;
      }
      else X[p]++;
	  }

    for( k = 0; k < count; k++ ) if( isValid[k] ) validCombinations++;
    out.println( validCombinations );
    out.println( differentSums );
	}
}