Сердитый учитель
Мистер О'Круэл преподает математику в девятом классе. Ученики, как это часто бывает, не любят делать домашние задания, а мистер О'Круэл не терпит лени.
Недавно Андрей снова не выполнил домашнее задание, и ему дали особое задание. Если он не справится, его могут исключить из школы. Задание выглядит простым, но оно требует много времени из-за своей технической сложности. Андрею дан многочлен 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).