Адиль, как полагается нонконформисту, отрицает существование всех известных бинарных операторов (даже $$$\mathbb{XOR}$$$!) и предпочитает пользоваться своими собственными. Среди них есть ещё не известный в широких кругах оператор $$$\mathbb{GOR}$$$, с которым он знакомит всех, кто попадается ему на глаза. Со слов автора, $$$z = x \ \mathbb{GOR} \ y$$$ действует так: $$$$$$z_k = (x_k + y_k) \mod g, $$$$$$ где $$$p_k$$$ — $$$k$$$-я справа цифра в записи числа $$$p$$$ в системе счисления с основанием $$$g$$$. Чтобы убедить весь мир в значимости придуманного им оператора, Адиль готов показать, что может за считанные секунды высчитать $$$\mathbb{GOR}$$$ всех чисел от $$$A$$$ до $$$B$$$. Вот только он оставил свою программу дома, и торжественная презентация под угрозой срыва. Вся надежда только на Вас! Вы ведь сможете спасти положение и написать эту программу?
На первой строке даны целые числа $$$A$$$ и $$$B$$$ — границы оперирования ($$$1 \le A \le B \le 10^{18}$$$). На второй строке дано число $$$g$$$ — основание системы оперирования ($$$2 \le g \le 10$$$).
Целое положительное число — значение выражения: $$$A \ \mathbb{GOR} \ (A+1) \ \mathbb{GOR} \ (A+2) \ \mathbb{GOR} \ \dots \ \mathbb{GOR} \ B$$$.
1 4 2
4
4 9 3
15
8 11 10
28
В примере 3 при $$$g = 10$$$: $$$8 \ \mathbb{GOR} \ 9 \ \mathbb{GOR} \ 10 \ \mathbb{GOR} \ 11 = 7 \ \mathbb{GOR} \ 10 \ \mathbb{GOR} \ 11 = 17 \ \mathbb{GOR} \ 11 = 28$$$.
