Sum in sympathetic table
Given rectangular table A with n rows and m columns. This table has n × m cells, numbered sequentially with positive integers from top to bottom, from left to right. A[i][j] is a cell of rectangular table A at the cross of i-th row and j-th column. For the given value of x the sympathetic table is a table A with values in the cells equal to x in power of number of the corresponding cell. More formally A[i][j] = x^({i−1}∗m+j).
Given q queries of rectangular borders x1, x2, y1, y2 and modulo p, the answer for such query is the sum of numbers in corresponding rectangle by modulo.
More formally
Write a program to answer the queries.
The sympathetic table A, 3 by 4 for a given x looks like:
Input
First line contains three integers n, m, x (1 ≤ n, m, x ≤ 10^9). Next line contains one number q (1 ≤ q ≤ 10^4). Each of the next q lines contains a query that is given with five numbers x1, x2, y1, y2, p (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m, 1 ≤ p ≤ 10^9).
Output
Print q numbers, each in a separate line, the answers to the queries.