Maximum Multiplicative Partition

This problem is based on the celebration of the "2000 - World Mathematics Year" and the 90th anniversary of the famous mathematician Hua Luogeng. In this contest, you are given a numeric string of length \(N\) and an integer \(K\). You are required to insert exactly \(K\) multiplication signs into the string to split it into \(K+1\) parts. Interpret each part as an integer and find a way to partition the string such that the product of these parts is maximized.

For example, consider the numeric string "312" with \(N=3\) and \(K=1\). There are two possible ways to split the string:

• Partition: 3 and 12, Product: \(3 \times 12 = 36\)
• Partition: 31 and 2, Product: \(31 \times 2 = 62\)

The correct answer is: 31 * 2 = 62.

inputFormat

The input consists of two lines. The first line contains two integers (N) and (K), where (N) is the length of the numeric string and (K) is the number of multiplication signs to be inserted. The second line contains the numeric string (consisting of digits only).

outputFormat

Output a single line representing the chosen partition and its product in the following format:

segment1 * segment2 * ... * segment(K+1) = product

Note: There will be no extra spaces except those around the '*' and '=' symbols.

sample

3 1
312

31 * 2 = 62