题目背景

A+B Problem 是每个 OIer 入门必做的经典题。自古以来，已有众多先辈研发出过各种解法。这次，请你以不同的解法重温这道题吧。

题目描述

我们一共有 $10$ 种不同的解法。分别是：

1. 直接输出 $A+B$。
2. 交换 $A$ 和 $B$，再换回来，输出 $A+B$。
3. 循环 $A+B$ 次，记录 $sum$ 变量，每次 $+1$，最后输出 $sum$。
4. 二分 $A+B$。规定 $l$ 初值为 $-10^9$，$r$ 初值为 $10^9$，条件为 $l+1<r$，$mid \leftarrow (l+r)/2$。若 $mid=A+B$，直接输出，结束二分；若 $mid<A+B$，则令 $l \leftarrow mid$；若 $mid>A+B$，则令 $r \leftarrow mid$。
5. 针对第 $3$ 点进行优化。二进制拆分 $A$ 和 $B$（若当前数大于等于 $2^n$（$n$ 从 $0$ 开始），则当前数拆分出一个 $2^n$，$n=n+1$；反之直接将剩下的数拆分出来），再将结果全部相加。
6. gcd（最大公因数）。求 $A$ 与 $B$ 的 gcd，同时除以 gcd，再乘回来。
7. 快速读入。会输入 $n$ 个与 $A,B$ 无关的整数，以及 $A$ 和 $B$，全部读入后再输出 $A+B$。
8. 线段树。将 $A$ 与 $B$ 二进制拆分为一个序列（拆分方法同上），从小到大排序，建立线段树（建立时每次将该节点维护的和分为两半，若长度为奇数则左边比右边长 $1$。编号由 $1$ 开始，按从上到下，从左到右编号。注意：$0$ 值的节点应被删除。），再查询区间 $[1,n]$ 的和（$n$ 是拆分出来的数的个数）
9. 最短路。将 $A$ 与 $B$ 二进制拆分为一个序列，从小到大排序，建无向图，图有 $n$ 条边，将节点编号为 $1$ 至 $n+1$（$n$ 是拆分出来的数的个数），节点 $i$（$i<n+1$）与节点 $i+1$ 有连边，边权为排序后的序列的第 $i$ 项。使用 floyd 算法求点 $1$ 至 $n+1$ 的最短路，输出。
10. AC 自动机。构造一个由 $A$ 和 $B$ 的字符串形式拼接而成的字符串，trie 的编号由 $0$（根节点） 开始，按创建时间编号（依次加入 $A$ 与 $B$ 的字符串形式，从前往后加字符进 trie 树，以此从 $1$ 至 $n$ 编号，$n$ 是 trie 的节点数）。Fail 的意义与通常的一样。在构造出的字符串中搜寻 $A$ 与 $B$ 的字符串形式，搜到后将搜到的 $A$ 与 $B$ 相加，输出。

输入格式

先输入一个数 $T$，表示使用的解法的编号。接下来：

1. 若 $T\ne7$，一行，两个空格隔开的整数，$A$ 和 $B$。
2. 若 $T=7$，三行，第一行是一个整数 $n$，第二行是 $n$ 个空格隔开的整数，第三行是两个空格隔开的整数，$A$ 和 $B$。

输出格式

对于 $10$ 种不同的解法，你需要分别输出一些中间过程。分别有：

1. 输出一行一个整数，$A+B$。
2. 三行，每行一个整数，分别是交换后的 $A$ 和 $B$，换回来后的 $A$ 和 $B$，$A+B$。
3. 输出 $A+B$ 行，每行一个整数，分别是每次循环的 $sum$。
4. 输出若干行，每行三个空格隔开的整数，分别是每次进行完一次二分的 $l$，$r$，$mid$，也包括 $mid=A+B$ 时的 $l$，$r$，$mid$。完整操作流程：

初始化 l,r。
循环执行直到 l+1>=r：
    计算 mid。
    若 mid=A+B：
        输出 l,r,mid。
        结束操作。
    若 mid<A+B：
        将 l 的值赋为 mid。
    否则：
        将 r 的值赋为 mid。
    输出 l,r,mid。

5. 两行，第一行若干个空格隔开的整数，为拆分 $A$ 和 $B$ 且排序后的几个数；第二行是 $A+B$。
6. 两行，一行一个整数，第一行为 $A$ 和 $B$ 的 gcd，第二行是 $A+B$。
7. 输出一行，$A+B$。
8. 输出两行，第一行 $n$ 个空格隔开的整数（$n$ 是线段树节点数），分别为每个节点维护的和；第二行是 $A+B$。
9. 输出 $n+1$ 行（将 $A$ 与 $B$ 二进制拆分，$n$ 是拆分出来的数的个数），每行 $n+1$ 个整数，第 $i$ 行的第 $j$ 个数为节点 $i$ 至节点 $j$ 的最短路。
10. 输出 $4$ 行，第一行为一个字符串，为构造的字符串；第二行为若干个空格隔开的数字字符，分别为 trie 树中每个节点（不包括根节点 $0$）对应的字符；第三行分别为 trie 树中每个节点对应的 fail 指针指向的节点编号（包括根节点 $0$），第四行为 $A+B$。

样例

1
20 30

50

提示说明

对于每个解法，数据分别保证：

1. $0\le A,B\le 10^9$。
2. $0\le A,B\le 10^9$。
3. $0\le A,B\le 10^6$。
4. $0\le A,B\le 10^8$。
5. $0\le A,B\le 10^9$。
6. $0\le A,B\le 10^9$。
7. $0\le n\le 10^7$，每个整数 $0\le a_i\le 10^9$，$0\le A,B\le 10^9$。
8. $0\le A,B\le 10^9$。
9. $0\le A,B\le 10^9$。
10. $0\le A,B\le 10^9$。

对于测试点 $1-10$，每个点分别对应解法 $1-10$。其时间、空间、赋分分别为：

1. $50$ ms，$10$ MB，$1$ pts
2. $50$ ms，$10$ MB，$3$ pts
3. $500$ ms，$10$ MB，$4$ pts
4. $50$ ms，$10$ MB，$6$ pts
5. $50$ ms，$10$ MB，$6$ pts
6. $50$ ms，$10$ MB，$6$ pts
7. $800$ ms，$10$ MB，$4$ pts
8. $50$ ms，$10$ MB，$20$ pts
9. $50$ ms，$10$ MB，$20$ pts
10. $50$ ms，$10$ MB，$30$ pts