eolymp
bolt
Try our new interface for solving problems
Problems

Sum in sympathetic table

Sum in sympathetic table

Time limit 1 second
Memory limit 122 MiB

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

prb7839.gif

Write a program to answer the queries.

The sympathetic table A, 3 by 4 for a given x looks like:

prb7839_1.gif

Input data

First line contains three integers n, m, x (1n, m, x10^9). Next line contains one number q (1q10^4). Each of the next q lines contains a query that is given with five numbers x1, x2, y1, y2, p (1x1x2n, 1y1y2m, 1p10^9).

Output data

Print q numbers, each in a separate line, the answers to the queries.

Examples

Input example #1
1 10 2
5
1 1 1 1 1000000007
1 1 1 2 1000000007
1 1 1 5 1000000007
1 1 2 4 1000000007
1 1 2 3 1000000007
Output example #1
2
6
62
28
12
Source 2014 Казахстан, 4-й этап Республиканской олимпиады по информатике, Усть-Каменогорск, Март, Задача E