도로 관리자

격자에 $n \times m$ 개의 칸이 있다. 왼쪽 위 칸은 $(1, 1)$이고 오른쪽 아래 칸은 $(n, m)$이다.

두 칸이 변을 공유하면 인접하다고 한다. 격자는 원형이어서 $(i, m)$도 $(i, 1)$과 인접한다. 첫 행과 마지막 행은 연결되지 않는다.

인접한 두 칸 사이에는 양방향 도로가 정확히 하나 있다.

• 모든 $(i, j)$ ($1 \le i \le n$, $1 \le j \le m$)에 대해 $(i, j)$와 $(i, j \bmod m + 1)$ 사이에 도로가 있다.
• 모든 $(i, j)$ ($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 10000$, $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 10000$)가 주어진다. 이어서 $q$개의 줄에 $l_i$와 $r_i$ ($1 < l_i \le r_i < m$)가 주어진다.

각 질의마다 해당 그래프의 MST 가중치 합을 한 줄에 출력한다.

예시에서 생성된 그래프다.