Sum in sympathetic table#7839
Given rectangular table with rows and columns. This table has n \times m cells, numbered sequentially with positive integers from top to bottom, from left to right. A_{i,j} is a cell of rectangular table at the cross of -th row and -th column. For the given value of the sympathetic table is a table with values in the cells equal to in power of number of the corresponding cell. More formally A_{i,j} = x^{(i-1) \cdot m + j}.
Given queries of rectangular borders x_1, x_2, y_1, y_2 and modulo , 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 , by for a given looks like:
First line contains three integers , , (1 \le n, m, x \le 10^9). Next line contains one number (1 \le q \le 10^4). Each of the next lines contains a query that is given with five numbers 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).
Print numbers, each in a separate line, the answers to the queries.
Example 1