Description

When Little FF arrived, the temple was already in ruins. But at the center stood a stone pedestal that was bright and spotless. Little FF approached and found a string of digits on the pedestal, with a line of ancient runic words carved above it. Being fluent in ancient runes, Little FF easily understood the text, which roughly says:

Given the string of digits on the pedestal, you may insert multiplication signs at suitable positions (suppose you insert $k$ of them; you may also insert none, i.e., split into $k+1$ parts). Let the product of these $k+1$ parts (if $k=0$, the product is just the value of the original string) modulo $m$ be $x$ (that is, $\bmod\ m$).

Find the minimum possible $x$ and, among all ways achieving it, the smallest $k$; and find the maximum possible $x$ and, among all ways achieving it, the smallest $k$ (it is possible that the minimum and maximum $x$ are the same).

Little FF also knows that if he finds the correct answer, he can proceed to the lower level of the temple. But this problem seems hard, so he turns to you for help, and promises an eighty–twenty split of the treasure afterwards (you get twenty).

Input Format

The first line contains the string of digits, which does not contain the digit $0$.

The second line contains $m$.

Output Format

Output four numbers: the minimum value of $x$ and, in that case, the smallest $k$; then the maximum value of $x$ and, in that case, the smallest $k$. Separate adjacent numbers with a single space.

4421
22

0 1 21 0

Hint

Let $L$ be the length of the string.

• For $30\%$ of the testdata: $2 \le L \le 50$.
• For $100\%$ of the testdata: $2 \le L \le 1000$, $2 \le m \le 50$.

NOI Guide 2010 Senior (02).

Translated by ChatGPT 5