# 题目背景

在 Baymax 的计算世界中，有一位勇敢的程序员探险家，名叫 Gino。他决定挑战一座神秘的数字山，山上镇守着一座溢出宝库。只有解开这座宝库的溢出密码，才能获得传说中的数字宝藏。

密码是由一串巨大的二进制数字表示，而这个二进制串描述了山峰上每个位置的数字。Gino 发现，山峰的神秘力量会对每个位置上的数字进行补码运算，但是如果计算结果的数值超过了补码所能表示的数据范围，就会触发溢出，使得密码变得不可预测。

你的任务是设计一个程序来模拟这个溢出密码的解析过程，帮助 Gino 获取宝库中的数字宝藏。

# 题目描述

给出两个数字的补码表示，请你判断这两个数字相加时是否会发生溢出。

# 输入格式

输入共三行。

第一行为两个正整数 $t, n$，其中 $t$ 代表输入数据的组数，$n$ 代表进行运算时计算机所能使用的最多 bit 位，假设存在最大可以储存 $10^4$ 个字节的整型。

第二、三行每行 $n$ 个数字，分别代表两个有符号数的补码表示，保证 $t \le 100, n \le 10^4$。

# 输出格式

对于每组数据，输出一行，一个字符串。

如果两数相加发生溢出，输出 0verFLOW! 。

如果两数相加未发生溢出，输出 Not 0verFLOW 。

# 输入样例

2 8

11111111

11111111

10000000

10000000

# 输出样例

Not 0verFLOW

0verFLOW!

# 样例解释

对于样例数据，$n$ 为 $8$，代表运算时最多使用 $8$ 个 bit 位，所能表示的数据范围为 $−128 \sim 127$。

补码 11111111 为数字 $−1$，$−1−1=−2$，未发生溢出。

补码 10000000 为数字 $−128$，$−128−128=−256$, 发生溢出。

# 提示

试着从符号位和数值位最高位运算时的进位情况入手考虑吧～

# 题解：位运算

一个很暴力的想法就是符号位和数字为单独分析，这样也能做，但是代码写起来非常麻烦。那么整型的相加与补码的直接相加能不能统一起来呢？

一个很显然的事实是，正数加负数是不可能溢出的，这种情况直接无脑输出 Not 0verFLOW 即可。

对于同号数相加，我们考虑计算机溢出的实际含义。实际上计算机在计算加法的时候就是直接将补码相加，舍去多出来的位数。对于两个正数相加，符号位原本是 $0 + 0 = 0$，如果溢出了，符号位就会变成 $1$，也就是我们常说的 “正数相加溢出为负数”。

对于两个负数相加，符号位原本就是 $1 + 1$，肯定会溢出，那如何判断两个负数相加会不会实际上发生溢出呢？考虑四位补码表示下不溢出的情况：$-6 - 2$，我们会发现结果的第五位和第四位都是 $1$，后面都是 $0$，舍弃第五位，结果为 $1000$，还是 $-8$，没毛病。如果是 $-6 - 3$，我们会发现结果的第五位是 $1$，而第四位是 $0$，舍弃第五位之后结果是 $0111$，发现变成了 $7$，也就是发生了负数溢出为整数的情况！总结来看，对于两个负数相加，肯定会发生溢出，至于数值算得对不对，我们比较第 $n + 1$ 位和第 $n$ 位是否相同，若均为 $1$，那实际上数值没有发生溢出，若不同，说明向正数发生溢出了。

时间复杂度：$O(Tn)$。

参考代码：

#include <stdio.h>

int n, a[10010], b[10010];

int main()

{

    // freopen("D.in", "r", stdin);

    // freopen("D.out", "w", stdout);

    int T;

    scanf("%d%d", &T, &n);

    while (T -- )

    {

        b[n + 1] = 0;

        for (int i = n; i; -- i)

            scanf("%1d", &a[i]);

        for (int i = n; i; -- i)

            scanf("%1d", &b[i]);

        if (a[n] != b[n])

            puts("Not 0verFLOW");

        else

        {

            for (int i = 1; i <= n; ++ i)

            {

                b[i] += a[i];

                if (b[i] >= 2)

                {

                    b[i] -= 2;

                    ++ b[i + 1];

                }

            }

            if (a[n] == 0 && b[n] == 1)

                puts("0verFLOW!");

            else if (a[n] == 1 && b[n] != b[n + 1])

                puts("0verFLOW!");

            else

                puts("Not 0verFLOW");

        }

    }

    return 0;

}