Злий Вчитель
Містер О'Круел викладає математику дев'ятикласникам. Учні, як завжди, не надто старанні, тому їм не подобається виконувати домашні завдання. Водночас, містер О'Круел не терпить ледачих учнів.
Нещодавно Андрій знову не виконав своє домашнє завдання, і тепер йому дали особливе завдання. Якщо він не впорається, його виключать зі школи. Завдання виглядає простим, але є досить технічним і потребує багато часу. Андрію дано многочлен p(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0 з цілими коефіцієнтами.
Йому потрібно обчислити значення цього многочлена для k послідовних цілих чисел, починаючи з l. Звісно, записати всі ці числа займе надто багато паперу. Тому, як доказ виконання завдання, для кожного числа від l до l+k-1 Андрія просять надати суму квадратів m останніх цифр у десятковій нотації p(x).
Оскільки Андрій не хоче виконувати завдання самостійно, він просить вас написати програму, яка обчислить потрібні значення.
Вхідні дані
Перша строка вхідних даних містить n, l, k та m (0 ≤ n ≤ 10, 0 ≤ l ≤ 10^1000, 1 ≤ k ≤ 1000, 1 ≤ m ≤ 1000).
Наступні n+1 рядків містять коефіцієнти многочлена: a_n, a_{n-1}, ..., a_1, a_0 (0 ≤ a_i ≤ 10^1000).
Вихідні дані
Виведіть k рядків — для кожного x від l до l+k-1 виведіть суму квадратів останніх m цифр p(x).