Chemistry
Create a program that:
identifies the smallest natural coefficients, each not exceeding 30, to be placed before each substance in a chemical equation, ensuring the number of atoms for each element remains constant throughout the reaction;
outputs the correctly balanced chemical reaction equation.
Input
The input consists of the chemical formulas of the reactants, separated by a + sign and positioned to the left of the = sign, and the products, also separated by a + sign, positioned to the right of the = sign. The total number of substances (both reactants and products) does not exceed 10. All chemical element symbols (in the 1-st line) begin with uppercase Latin letters. If a compound contains more than 1 atom of an element, this is indicated with a subscript number (in the 2-nd line). A single formula may contain multiple occurrences of the same element symbol. If a compound includes several identical groups of atoms, these are enclosed in parentheses, with the number of repetitions indicated as a subscript to the right of the closing parenthesis. Spaces in the first line appear only above the numbers in the second line, and the first line does not end with spaces. The input guarantees a unique solution exists.
Output
The output is generated by inserting coefficients, other than 1, into the first line and aligning the corresponding number of spaces in the second line beneath these coefficients.