Сümə cazibədar cədvəldə

Sizə n sətir və m sütundan ibarət düzbucaqlı A cədvəli verilib. Bu cədvəldə dəqiq olaraq n × m hüceyrə var və onlar yuxarıdan aşağıya, soldan sağa doğru ardıcıl olaraq təbii ədədlərlə nömrələnib. A[i][j] düzbucaqlı cədvəl A-nın i-ci sətir və j-ci sütunun kəsişməsində yerləşən hüceyrəni ifadə edəcək. Müəyyən bir x ədədi üçün cəlbedici cədvəl, cədvəldəki hüceyrələrin dəyərlərinin həmin hüceyrənin nömrəsinin x qüvvətinə bərabər olduğu cədvəl olacaq. Daha dəqiq desək, A[i][j] = x^({i−1}∗m+j).

q sorğusu verilib, hər biri x1, x2, y1, y2 sərhədləri və modul p olan alt-düzbucaqlının sorğusudur, hər bir sorğunun cavabı müvafiq alt-düzbucaqlının müvafiq modul üzrə ədədlərinin cəmi olacaq.

Daha dəqiq desək

Verilən sorğulara cavab verən proqram yazın.

x ədədi üçün 3 x 4 ölçülü cəlbedici cədvəl A aşağıdakı kimi görünəcək:

Giriş məlumatları

Birinci sətirdə üç tam ədəd n, m, x (1 ≤ n, m, x ≤ 10^9) verilib. Növbəti sətirdə tək tam ədəd q (1 ≤ q ≤ 10^4) verilib. Növbəti q sətirdə sorğular verilib, hər sorğu beş ədəd x1, x2, y1, y2, p (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m, 1 ≤ p ≤ 10^9) ilə təyin edilir.

Çıxış məlumatları

Müvafiq sorğuların cavablarını hər sətirdə bir ədəd olmaqla q ədəd çıxış verin.