Вам задана прямоугольная таблица 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, ответом на каждый запрос будет сумма чисел в соответствующем подпрямоугольнике по соответствующему модулю.

Более формально

Напишите программу, отвечающую на заданные запросы.

Симпатичная таблица A, 3 на 4, для числа x будет выглядеть следующим образом:

Входные данные

В первой строке заданы три целых числа n, m, x (1 ≤ n, m, x ≤ 109). В следующей строке задано единственное целое число q (1 ≤ q ≤ 104). В следующих q строках заданы запросы, каждый запрос задается пятью числами x1, x2, y1, y2, p (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m, 1 ≤ p ≤ 109).

Выходные данные

Выведите q чисел, по одному на каждой строке, ответы на соответствующие запросы.