Сума в симпатичній таблиці#7839
Вам надано прямокутну таблицю розміром рядків на стовпців. У цій таблиці є рівно n \times m клітинок, які пронумеровані послідовно натуральними числами зверху вниз і зліва направо. Позначимо A_{i,j} як клітинку таблиці , що знаходиться на перетині -го рядка та -го стовпця. Для заданого числа симпатичною таблицею буде така таблиця , в якій значення в клітинках дорівнюють у степені номера відповідної клітинки. Формально це записується як A_{i,j} = x^{(i-1) \cdot m + j}.
Вам потрібно обробити запитів, кожен з яких задає межі підпрямокутника x_1, x_2, y_1, y_2 та модуль . Відповіддю на кожен запит буде сума чисел у відповідному підпрямокутнику, взята за модулем .
Більш формально
Напишіть програму, яка обробить ці запити.
Приклад симпатичної таблиці розміром на для числа виглядає так:
У першому рядку задано три цілі числа , , (1 \le n, m, x \le 10^9). У наступному рядку задано одне ціле число (1 \le q \le 10^4). У наступних рядках наведено запити, кожен з яких складається з п'яти чисел x_1, x_2, y_1, y_2, (1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le m, 1 \le p \le 10^9).
Виведіть чисел, по одному в кожному рядку, які є відповідями на відповідні запити.
Приклад 1