Для додатнього числа \textbf{a} визначимо функцію \textbf{S(a)}, рівну сумі його цифр у системі числення з основою \textbf{l}. Крім того, нехай \textbf{L(a)} - мінімальне \textbf{k}, для якого \textbf{S^k(a)} не перевищує \textbf{l-1}. Потрібно знайти мінімальне \textbf{a}, таке що \textbf{L(a)=N} для заданого \textbf{N} і вивести його по модулю \textbf{m}. \InputFile \textbf{N} \textbf{m} \textbf{l} \textbf{0} ≤ \textbf{N} ≤ \textbf{10} \textbf{^5} ^\{ \} \textbf{1} ≤ \textbf{m} ≤ \textbf{10} \textbf{^9} \textbf{2} ≤ \textbf{l} ≤ \textbf{10} \textbf{^9} Вхідний файл містить декілька тестів і завершується рядком "\textbf{0 0 0}". Кожен тест задано у окремому рядку, який містить трійку чисел , , (, , ). \OutputFile Для кожного тесту виведіть його номер та мінімальне значення \textbf{a} по модулю m.