You are still in need of some green dye and head to the robotics station. The robots tell you they know how to make some green dye if they can follow the program to make some verdigris. But they also tell you that the current program code is too much for their instruction cache so you need to reduce it. You are given a list of rules on how to reduce the code followed by the code itself. Each rule consists of two parts separated by a blank line. The first part are the targets, which is a sequence of instructions which all have to match for that rule to fire. The second part are the the replacements. As the name suggests these are the new instructions which should be used instead of the targets. Take for example the following input:

123

456

456
789

1337

123
789

The last block of numbers is your program. The pair of blocks before it are the rules which help to minimize the program. In this instance it means that whenver you see a 123 in your code it has to be replaced with 456, and whenever you see 456 followed by a 789 it should be replaced by 1337. Do note though that freshly replaced codes are not considered again for replacement in the current optimization step. That means if you let run your optimizer once it should produce the following output

456
789

If you were to run the optimizer one more time it should then produce 1337. Let's look at another example:

1290
3224
066
398
5535

72
00
3286
89
14

601
329
066
394
839

1290
3224

601
329
066
394
839
022
396
5535

Again this has two rules and an input and if you run the optimizer on it, it should produce the following output after one step:

1290
3224
022
396
5535

To check if your program is properly optimized compute the checksum of it. The checksum is the sum of all instructions, so for this example 1290 + 3224 + 022 + 396 + 5535 = 10467. What is the checksum of your input after optimizing it once?