作为一名 ACM-ICPC 的新手，Aishah 正在学习计算机科学中的数据结构。她已经知道栈（stack）作为一种数据结构，可以作为元素的集合，并支持两种操作：

• push，将一个元素插入集合中；
• pop，删除最近插入且尚未被删除的元素。

现在，Aishah 希望有一个更智能的栈，能够动态地显示栈中的最大元素。请编写一个程序来帮助她实现这个目标，并完成包含若干操作的测试。

Aishah 假设栈最初是空的。你的程序需要在每次操作后输出栈中的最大元素。如果此时栈为空，则输出应为零。

输入格式

输入包含多个测试用例，第一行是一个正整数 $T$，表示测试用例的数量，最多为 50 个。

为了避免读取数据时产生不必要的耗时，每个测试用例由七个整数描述：$n$ ($1 \le n \le 5 \times 10^6$)，$p, q, m$ ($1 \le p, q, m \le 10^9$)，$SA, SB$ 和 $SC$ ($10^4 \le SA, SB, SC \le 10^6$)。其中 $n$ 是操作次数，你的程序应使用以下 C++ 代码生成所有操作：

int n, p, q, m;
unsigned int SA, SB, SC;
unsigned int rng61(){
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC = t ^ SA;
    return SC;
}
void gen(){
    scanf("%d%d%d%d%u%u%u", &n, &p, &q, &m, &SA, &SB, &SC);
    for(int i = 1; i <= n; i++){
        if(rng61() % (p + q) < p)
            PUSH(rng61() % m + 1);
        else
            POP();
    }
}

代码中使用的过程 PUSH(v) 将一个值为 $v$ 的新元素插入栈中，过程 POP() 弹出栈顶元素，如果栈为空则不进行任何操作。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是从 1 开始的测试用例编号，$y$ 等于 $\bigoplus_{i=1}^{n} (i \cdot a_i)$，其中 $a_i$ 是第 $i$ 次操作后的答案，$\oplus$ 表示按位异或。

样例

样例输入 1

2
4 1 1 4 23333 66666 233333
4 2 1 4 23333 66666 233333

样例输出 1

Case #1: 19
Case #2: 1

说明

第一个测试用例包含 4 次操作：

• POP();
• POP();
• PUSH(1);
• PUSH(4);

第二个测试用例也包含 4 次操作：

• PUSH(2);
• POP();
• PUSH(1);
• POP();