Description

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

Elephants build a bidirectional road between any two countries that are adjacent in longitude or latitude.

Consider longitude adjacency: for any country $(i,j)$ $(1 \leq i \leq n, 1 \leq j \leq m)$, there is a road between it and country $(i,j+1)$. In particular, when $j=m$, there is also a road between $(i,m)$ and $(i,1)$.

Consider latitude adjacency: for any country $(i,j)$ $(1 \leq i < n, 1 \leq j \leq m)$, there is a road between it and country $(i+1,j)$. Note that the North Pole and the South Pole are not adjacent.

The Elephant planet is not peaceful, and some countries are involved in a world war. In the $i$-th century among the next $q$ centuries, all countries whose longitudes are in $[l_i, r_i]$ are involved in the world war of that century. When a world war happens, countries involved in the war are dangerous. If a country is not involved in the war, then it is a peaceful country. If both endpoints of a road are peaceful countries, then it is a peaceful road. For safety reasons, the Elephant United Government will choose to open only some peaceful roads, so that during the war, any two peaceful countries can be connected directly or indirectly using only these opened peaceful roads.

For any road, the security cost required to keep it is different. Please write a program to help the united government find a plan with the minimum total security cost.

Note that after a century ends, the world war of that century will end. The participants of the next war have no relation to those of the current war.

Input Format

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

To reduce the input size, the security cost of each road is generated by the following code, where $\texttt{addedge(a,b,c,d,w)}$ means 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$, indicating the number of queries.

In the next $q$ lines, each line contains $2$ positive integers $l_i, r_i$, describing each query in order.

Output Format

Output $q$ lines. Each line contains one integer, answering the corresponding query, i.e. the total security cost.

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

9
5
13

Hint

Translated by ChatGPT 5