你可能已经知道这个故事了。你早上醒来，感觉头大了一倍。你隐约记得老板让你写的一个程序。登录后，你看到了你昨天写的一段核心代码。

unsigned int checksum (char str[], int len) {
    unsigned int r = 0;
    for (int k=0; k<8*len; k++) {          // iterate over bits of str
        if ((r & (1<<31)) != 0) r = (r << 1) ^ 0x04c11db7;
        else r = (r << 1);                 // do some magic
        if (str[k/8] & 1<<(7-k%8))         // if the k-th bit of str is set,
            r ^= 1;                        // then flip the last bit of r
    }
    return r;
}

“不错，”你想，“我注释写得挺好。” 尽管如此，你对“执行一些魔法（do some magic）”那部分还是有点不太理解。不过没关系，这个函数名叫 checksum，而且——瞧啊——它确实计算了给定字符串的某种校验和。

你回想起了任务的其余部分。你本来应该计算一个给定字符串的校验和，然后计算该字符串经过轻微修改后的版本的校验和。实际上，你程序的其余部分看起来也挺像样的。

#include <stdio.h>

int main()
{
    char str[1000001],c;
    int TESTS,n,changes,p;
    for (scanf ("%d", &TESTS); TESTS>0; TESTS--) {
        scanf ("%d %s", &n, str); // read the input
        printf ("%u\n", checksum(str, n)); // compute checksum for original string
        for (scanf ("%d", &changes); changes>0; changes--) {
            scanf ("%d %c", &p, &c); // apply the change
            str[p-1] = c;
            printf ("%u\n", checksum(str, n)); // compute checksum for modified string
        }
    }
}

然后你记起了最后一个问题。该程序运行得非常完美，但速度却极其缓慢。你必须让它运行得更快。快得多。由于你听说 Java 是一种更好、更安全的编程语言，你甚至写了一个等价的 Java 版本（见下文），但它运行得甚至更慢（奇怪吧？）。

输入格式

输入包含多个测试用例。输入的第一行包含一个正整数 $Z \le 20$，表示测试用例的数量。接下来是 $Z$ 个测试用例，每个测试用例都符合以下格式：

在每个测试用例的第一行中，包含一个自然数 $n$ ($1 \le n \le 10^6$) 和一个字符串 $s$，它们之间用一个空格隔开。字符串 $s$ 由 $n$ 个字符组成。在下文中，字符是指单个小写或大写字母，或数字。

第二行包含一个整数 $t$ ($0 \le t \le 10^5$)，表示要对字符串 $s$ 进行的修改次数。

接下来的 $t$ 行中，每行包含一个自然数 $p \in [1, n]$ 和一个字符 $c$，它们之间用一个空格隔开。它表示对字符串的一次修改：将 $s$ 的第 $p$ 个字符替换为 $c$。

输出格式

你必须输出与上述程序相同的输出。换句话说，你必须输出 $t + 1$ 行，每行包含一个作为校验和的自然数。第一个校验和必须针对原始字符串 $s$ 计算，其余的校验和在对 $s$ 进行每次修改后计算。

样例

输入样例 1

1
5 ABcd3
3
1 B
2 A
1 d

输出样例 1

1914964467
2137468714
2087137066
4274181240

程序的 Java 版本

import java.util.Scanner;

public class Compute {

    static long checksum (byte[] str, int len) {
        int r = 0;
        for (int k=0; k<8*len; k++) { // iterate over bits of str
            if ((r & (1<<31)) != 0) r = (r << 1) ^ 0x04c11db7;
            else r = (r << 1); // do some magic
            if ((str[k/8] & 1<<(7-k%8)) != 0) // if the k-th bit of str is set,
                r ^= 1; // then flip the last bit of r
        }
        long rr = (r<0 ? r+0x100000000L : r); // Java does not have unsigned int
        return rr;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int TESTS = in.nextInt(); TESTS>0; TESTS--) {
            int n = in.nextInt(); // read the input
            byte[] str = in.next().getBytes(); // compute checksum for
            System.out.println (checksum(str,n)); // original string
            for (int changes = in.nextInt(); changes>0; changes--) {
                int p = in.nextInt(); // apply the change
                byte c = in.next().getBytes()[0];
                str[p-1] = c;
                System.out.println (checksum(str,n)); // compute checksum for
            } // modified string
        }
    }
}