On the distant planet of Elephant, there is a prosperous Elephant civilization. Like Earthlings, the Elephant people use latitude and longitude to mark every location on the planet. They divide the planet into $n$ latitudes from north to south and $m$ longitudes from west to east. There is a country at every intersection of a meridian and a parallel, which they denote as $(i, j)$ for the country at latitude $i$ and longitude $j$. Clearly, there are $n \times m$ countries in total.

The Elephant people have built a two-way road between any two countries that are adjacent in either longitude or latitude.

Considering longitude adjacency: For any country $(i, j)$ ($1 \le i \le n, 1 \le j \le m$), there is a road between it and country $(i, j + 1)$. Specifically, when $j = m$, there is also a road between $(i, m)$ and $(i, 1)$.

Considering latitude adjacency: For any country $(i, j)$ ($1 \le i < n, 1 \le j \le m$), there is a road between it and country $(i + 1, j)$. Note: The North and South Poles are not adjacent.

The planet of Elephant is not peaceful, and some countries have been drawn into a world war. In the $i$-th century of the next $q$ centuries, all countries with longitude in the range $[l_i, r_i]$ are involved in the world war occurring in that century. When a world war occurs, the countries involved in the war are dangerous. If a country is not involved in the war, it is a peaceful country; if both endpoints of a road are peaceful countries, it is a peaceful road. For security reasons, the Elephant United Government chooses to open only some peaceful roads such that any two peaceful countries can be connected directly or indirectly through these open peaceful roads during the war.

For any road, the security cost required to maintain it varies. Please write a program to help the United Government find a plan with the minimum total security cost.

Note: After a century ends, the world war of that century will end, and there is no connection between the warring countries of the next war and the current war.

Input

The first line contains 6 positive integers $n, m, SA, SB, SC, lim$, where $n$ represents the range of latitudes and $m$ represents the range of longitudes.

To reduce the input size, the security cost of each road will be generated by the following code, where addedge(a, b, c, d, w) indicates that the security cost of the road between $(a, b)$ and $(c, d)$ is $w$:

unsigned int SA, SB, SC;int lim;
int getweight() {
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC % lim + 1;
}

void gen() {
    scanf("%d%d%u%u%u%d", &n, &m, &SA, &SB, &SC, &lim);
    int i, j, w;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++) {
            w = getweight();
            if (j < m) {
                addedge(i, j, i, j + 1, w);
            } else {
                addedge(i, j, i, 1, w);
            }
        }
    for(i = 1; i < n; i++)
        for(j = 1; j <= m; j++) {
            w = getweight();
            addedge(i, j, i + 1, j, w);
        }
}

The second line contains a positive integer $q$, representing the number of queries.

The next $q$ lines each contain 2 positive integers $l_i, r_i$, representing each query in order.

Output

Output $q$ lines, each containing an integer, answering each query in order, which is the minimum total security cost.

Examples

Input 1

2 4 1 2 3 5
3
2 2
2 3
3 3

Output 1

9
5
13

Note

Security cost of each road in the example

Constraints

For 100% of the data, $1 < l_i \le r_i < m$, $1 \le SA, SB, SC \le 10^9$.