Hirsli Müəllim#3856
Mr. O'Cruel doqquzuncu sinif şagirdlərinə Riyaziyyat dərsi keçir. Şagirdlər təbii ki, çox tənbəldirlər, ona görə də ev tapşırıqlarını yerinə yetirməyi sevmirlər. Digər tərəfdən, Mr. O'Cruel tənbəl şagirdləri sevmir.
Son zamanlarda Endryu yenidən ev tapşırığını etmədi, ona görə də ona xüsusi bir vəzifə verildi. Əgər bunu etməsə, məktəbdən qovulacaq. Vəzifə çox asan görünür, amma çox texniki olduğundan çox vaxt aparacaq. Endryuya tam ədədi əmsallarla verilmiş p(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0 polinomu verilib.
O, l-dən başlayaraq ardıcıl k tam ədəd üçün polinomun dəyərini hesablamalıdır. Təbii ki, bu ədədlərin hamısını yazmaq çox kağız tələb edərdi. Buna görə də, vəzifəni yerinə yetirdiyini sübut etmək üçün, l-dən l+k-1-ə qədər olan hər bir x üçün p(x)-in onluq yazılışında son m rəqəminin kvadratlarının cəmini təqdim etməsi tələb olunur.
Endryu tənbəl olduğundan, vəzifəni özü yerinə yetirmək istəmir. Ona görə də, sizdən tələb olunan dəyərləri hesablayan proqram yazmağı xahiş edir.
Girişin ilk sətri n, l, k və m (0 ≤ n ≤ 10, 0 ≤ l ≤ 10^1000, 1 ≤ k ≤ 1000, 1 ≤ m ≤ 1000) ehtiva edir.
Sonrakı n+1 sətir polinomun əmsallarını ehtiva edir: a_n, a_{n-1}, ..., a_1, a_0 (0 ≤ a_i ≤ 10^1000).
k sətir çıxış edin — l-dən l+k-1-ə qədər olan x üçün p(x)-in son m rəqəminin kvadratlarının cəmini çıxış edin.
Nümunə 1