在一个网格中有 $n \times m$ 个单元格，左上角单元格为 $(1, 1)$，右下角单元格为 $(n, m)$。

如果两个单元格共享一条边，则认为它们相邻。注意网格是循环的：$(i, m)$ 也与 $(i, 1)$ 相邻。然而，第一行和最后一行之间没有这种连接规则。

在两个相邻单元格之间恰好有一条双向道路： 对于每个满足 $1 \le i \le n$ 和 $1 \le j \le m$ 的单元格 $(i, j)$，它与 $(i, j \bmod m + 1)$ 之间有一条道路。注意网格是循环的，所以当 $j = m$ 时，$(i, m)$ 和 $(i, 1)$ 之间有一条道路。 对于每个满足 $1 \le i < n$ 和 $1 \le j \le m$ 的单元格 $(i, j)$，它与 $(i + 1, j)$ 之间有一条道路。

这些道路构成了一个加权图，每条道路都有其权重。你将收到 $q$ 次询问。在第 $i$ 次询问中，你会得到两个整数 $l_i$ 和 $r_i$。考虑移除所有满足 $1 \le x \le n$ 且 $l_i \le y \le r_i$ 的单元格 $(x, y)$ 以及与它们相连的道路后剩余的图。你需要求出该剩余图的最小生成树（MST）的总权重。

注意，不同的询问是独立的。换句话说，在回答完一个询问后，被移除的单元格和道路会恢复。

输入格式

每个测试点仅包含一组测试数据。

第一行包含六个整数 $n, m, SA, SB, SC$ 和 $lim$ ($1 \le n \le 100, 4 \le m \le 10\,000$ 以及 $1 \le SA, SB, SC, lim \le 10^9$)。

由于网格可能非常大，你必须使用以下 C/C++ 代码生成输入，其中 addedge(a, b, c, d, w) 表示我们在 $(a, b)$ 和 $(c, d)$ 之间添加一条权重为 $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);
        }
}

其他语言的编码者请注意：int 是 32 位有符号整数类型，而 unsigned int 是 32 位无符号整数类型。对 unsigned int 进行的每次运算结果都会截断为最后 32 位。这实际上意味着每个结果都对 $2^{32}$ 取模。

第二行包含一个整数 $q$ ($1 \le q \le 10\,000$)，表示询问次数。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 < l_i \le r_i < m$)，描述一个询问。

输出格式

对于每个询问，输出一行，包含一个整数：对应图的 MST 总权重。

样例

输入 1

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

输出 1

9
5
13

说明

样例中生成的图。