Multiplicative Partition Remainder

In a mysterious temple, a glowing stone pedestal displays a long string of digits. Inscribed above it are ancient runes which, when deciphered, reveal the following puzzle:

Given a string s consisting of digits, you are allowed to insert multiplication signs ('×') between some of its digits. Inserting k multiplication signs will partition the string into k+1 parts. Interpret each part as an integer (which may contain leading zeros) and compute the product of all these parts. Let x be the remainder when this product is divided by an integer m (i.e. x = (product mod m)).

Your task is to determine:

1. The minimum possible value of x along with the minimum number of multiplication signs (k) needed to achieve that remainder.
2. The maximum possible value of x along with the minimum number of multiplication signs (k) required for that remainder.

Note that if no multiplication sign is inserted (i.e. k = 0), then x is simply the value of the entire string modulo m.

If you provide the correct answer, the temple door to the lower levels will open!

inputFormat

The input consists of two lines:

1. The first line contains the non-negative integer s as a string of digits.
2. The second line contains an integer m.

outputFormat

Output four integers separated by spaces:

• The minimum remainder x_min and the corresponding minimum number of multiplication signs k_min needed to obtain x_min.
• The maximum remainder x_max and the corresponding minimum number of multiplication signs k_max needed to obtain x_max.

sample

123
5

1 1 3 0