Broken Calculator

Woojin bought a calculator for his number theory final exam. The calculator supports addition and multiplication of non-negative integers, along with grouping by parentheses, and it can compute the value of an expression that matches <expr> in the BNF below, modulo $P$.

• <expr> ::= <term> | <expr> + <term>
• <term> ::= <factor> | <term> * <factor>
• <factor> ::= <number> | ( <expr> )
• <number> ::= <digit> | <number> <digit>
• <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

A normal calculator evaluates multiplication before addition, evaluates operations inside parentheses before those outside, and evaluates operations of equal priority from left to right. This calculator is broken. It gives addition and multiplication equal priority, and it evaluates operations of equal priority in any order. For example, (2+2*2)+3 can evaluate to (4*2)+3 = 11 if the addition inside the parentheses runs first, or to (2+4)+3 = 9 if the multiplication runs first.

Ten minutes before the exam, Woojin realized the calculator is broken. As a quick fix, he will insert open parentheses ( and close parentheses ) into his expression so that the broken calculator always computes what he intended. Given the expression $S$ that Woojin wants to compute, write a program that inserts parentheses into $S$ so that the broken calculator always gives the result he intended.

The first line contains the length $N$ of the expression and the modulus $P$, separated by a space.

The second line contains the expression $S$ that Woojin wanted to compute.

The first line prints the length $M$ of the converted expression $T$.

The second line prints the converted expression $T$.

• $1\le N\le 50$
• $2\le P\le 20$
• $1\le M\le 100$
• $S$ and $T$ are strings made of digits and +, *, (, ).
• $S$ is an expression matching <expr> in the BNF above.
• $T$ is the string obtained by inserting only open and close parentheses into $S$.