P1773 Runeword

Legend has it that there is an ancient temple built by people of old beneath Mount Everest. In the temple’s basement lies the royal heritage, yet for thousands of years no one has ever reached it. The explorer Little FF dreams of becoming the richest person in the world and the most outstanding explorer, remembered forever. After proving that this cave does exist, Little FF made thorough preparations and arrived at the temple.

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).

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

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.

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