A. Another A+B Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Just before the 2022 Shanghai Collegiate Programming Contest, you decide to play some games to chill out. Today, your friend Tommy introduces a game called Nerdle to you. This game is about to guess some equations.

A game in Nerdle.

You can present an equation to the jury each time. The jury will send back results by the colors:

  • If it's green, as the +, = and 5 in the first line of the figure, the digit or operator are in the solution and in the correct spot.
  • If it's purple, as the 4 and the first two 1s in the first line of the figure, the digit is in the solution but in the wrong spot.
  • If it's black, the digit is not in the solution in any spot, or
  • If your guess includes a digit that appears more times than it is in the answer, you will get color tiles exactly as the number of appearances in the answer, and the remaining tiles are black. Therefore, the first equation in the figure contains exactly two 1s, but none of them are in the two middle spots and the last spot. Purple and black tiles can be chosen arbitrarily if both exist for a digit.

After playing for a while, you found that you spent a lot of time just trying to make the left-hand side equal to the right-hand side. As a strong competitive programmer, it's so much a waste of time for you. You decide to use your computer to analyze the result of one equation so that the remaining possible equation can be obtained. The equation and answer have the following restrictions:

  • The third and the sixth character are fixed with '+' and '=' respectively, and they are all green.
  • The only allowed operator is the binary plus sign. Here, 'binary' is for involving two operands. So, the answer is always in the form "??+??=??" where '?' can be replaced by a digit (0...9).
  • Leading zeros are allowed here, so "01+02=03" is a valid equation.

Write a program to find out all possible remaining equations by a given result.

Input

The input contains two strings $$$E, C$$$ of length $$$8$$$ in two lines, denoting the equation asked and the color returned by the jury, respectively. $$$C$$$ consists of 'GPB', denoting green, purple, and black of the corresponding spot.

It's guaranteed that:

  • $$$E$$$ is a valid equation.
  • The third and the sixth character of $$$E$$$ are fixed with '+' and '=' respectively, and the other positions are digits (0...9).
  • The third and the sixth character of $$$C$$$ are 'G'.
Output

Print an integer $$$R$$$ in the first line, denoting the number of different remaining possible equations. Two equations are considered different if they are different on at least one character.

For the next $$$R$$$ lines, print a string in each line denoting a valid equation corresponding to the input.

You can print your solution in any order. It's guaranteed that at least one valid equation exists.

Examples
Input
40+11=51
PBGPPGGB
Output
7
11+42=53
11+43=54
11+44=55
11+45=56
11+46=57
11+47=58
11+48=59
Input
12+46=58
GBGGPGGB
Output
6
11+45=56
13+43=56
15+41=56
16+40=56
16+41=57
16+43=59
Input
11+22=33
PBGPPGGP
Output
1
22+13=35
Input
11+22=33
BPGPPGGP
Output
1
22+13=35
Input
01+02=03
PPGPPGPP
Output
2
10+20=30
20+10=30
Note

From the first and the second example, one can conclude that the only solution for the game in the figure is 11+45=56.

The third and the fourth sample are the same, yet the black and purple tiles are chosen differently.