Сума в симпатичній таблиці
Вам надано прямокутну таблицю A розміром n рядків на m стовпців. У цій таблиці є рівно n × m клітинок, які пронумеровані послідовно натуральними числами зверху вниз і зліва направо. Позначимо A[i][j] як клітинку таблиці A, що знаходиться на перетині i-го рядка та j-го стовпця. Для заданого числа x симпатичною таблицею буде така таблиця A, в якій значення в клітинках дорівнюють x у степені номера відповідної клітинки. Формально це записується як A[i][j] = x^({i−1}∗m+j).
Вам потрібно обробити q запитів, кожен з яких задає межі підпрямокутника x1, x2, y1, y2 та модуль p. Відповіддю на кожен запит буде сума чисел у відповідному підпрямокутнику, взята за модулем p.
Більш формально
Напишіть програму, яка обробить ці запити.
Приклад симпатичної таблиці A розміром 3 на 4 для числа x виглядає так:
Вхідні дані
У першому рядку задано три цілі числа n, m, x (1 ≤ n, m, x ≤ 10^9). У наступному рядку задано одне ціле число q (1 ≤ q ≤ 10^4). У наступних q рядках наведено запити, кожен з яких складається з п'яти чисел x1, x2, y1, y2, p (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m, 1 ≤ p ≤ 10^9).
Вихідні дані
Виведіть q чисел, по одному в кожному рядку, які є відповідями на відповідні запити.