#P18428. Alea Iacta Est

Alea Iacta Est

Alea Iacta Est

SSerxhs 有两枚骰子,分别有 nn 个面和 mm 个面,面上的数字分别为 1,2,…,n1,2,\ldots,n 和 1,2,…,m1,2,\ldots,m。他对同时掷这两枚骰子所得数字之和的概率分布很感兴趣。请找到另一对与原来不同的骰子,使它们所得数字之和服从相同的概率分布。

由于面数很多的骰子难以制作,你需要使新骰子的面数之和最小。假设每枚骰子的各个面出现的概率相等。

当且仅当存在一个数字 xx,它在两枚骰子的面上出现的次数不同,称这两枚骰子不同。当且仅当一对骰子中存在一枚骰子,与另一对中的任意一枚都不同,称这两对骰子不同。也就是说,骰子按面上数字的多重集合比较,一对骰子不区分先后顺序。

当且仅当对所有整数 kk 都有 P(X=k)=P(Y=k)P(X=k)=P(Y=k),两个随机变量 X,YX,Y 服从相同的概率分布。

输入格式

第一行包含整数 tt(1≤t≤40001\le t\le4000),表示测试用例数。

每个测试用例仅一行,包含两个整数 n,mn,m(1≤n,m≤1061\le n,m\le10^6),表示原来的两枚骰子的面数。

保证全部测试用例的 max⁡{n,m}\max\{n,m\} 之和不超过 10610^6。

输出格式

每个测试用例输出两行,分别描述两枚新骰子。第 ii 行的第一个整数 fif_i 表示对应骰子的面数,随后输出 fif_i 个整数 a1,a2,…,afia_1,a_2,\ldots,a_{f_i}(1≤aj<n+m1\le a_j<n+m),表示各面上的数字。允许不同面上的数字相同。

输出的骰子对必须不同于原来的骰子对,和的概率分布相同,并且面数和最小。有多种最优方案时可以输出任意一种。

特别地,若不存在解,则两行分别输出一个 0。原题还规定,所有测试用例输出的 fif_i 之和不超过 3⋅1063\cdot10^6。

原样例在不同测试用例之间增加了空行以便阅读;输出中是否包含这些空行均可。

原样例

3
2 8
1 9
2 9
4 1 2 3 4
4 1 2 5 6

3 1 2 3
3 1 4 7

6 1 2 4 5 7 8
3 1 2 3