#P17850. FLO

FLO

— 花卉杂交

你要培育出恰好有 cc 片花瓣的花。最初只有两种花,花瓣数分别为 aa 和 bb。

唯一的杂交方法是:选择两种已有的花,它们分别有 x,yx,y 片花瓣,培育出花瓣数为

xy−x−y+2xy-x-y+2

的新种类。允许两次选择同一种花,已有种类可以反复使用。

给定若干询问。它们共享同一个目标 cc,但初始的 a,ba,b 不同。对每个询问,判断能否得到目标种类;如果能,输出一个不超过 ℓ\ell 次杂交的方案。不要求操作次数最少。

输入格式

第一行是十进制整数 cc。

第二行一个整数 qq,表示询问数。第三行一个整数 ℓ\ell,表示每个方案允许的最大操作次数。

接下来 qq 行,每行两个整数 ai,bia_i,b_i。

输出格式

按输入顺序分别回答各询问。

若无解,输出一行 -1。

若有解,输出两行:第一行给出操作次数 kk;第二行给出 2k2k 个种类编号,每两个数表示一次杂交使用的两种花。

初始 aia_i 片花瓣的花编号为0,bib_i 片花瓣的花编号为1。第 jj 次操作得到的新种类编号为 j+1j+1;这次操作只能引用编号 0,1,…,j0,1,\ldots,j,允许两个编号相同。最后产生的编号 k+1k+1 的花必须恰有 cc 片花瓣。

保证只要存在方案,就存在不超过 ℓ\ell 次操作的方案。合法方案可能不唯一。

数据范围

4≤c≤1050004\le c\le10^{5000},1≤q≤50001\le q\le5000,100≤ℓ≤20000100\le\ell\le20000,3≤ai,bi≤min⁡(c−1,108)3\le a_i,b_i\le\min(c-1,10^8)。

注意 c=105000c=10^{5000} 有5001个十进制数字。

以下五个子任务各20分:

子任务 附加限制
1 c≤1000,q≤100,ℓ=20000c\le1000,q\le100,\ell=20000
2 c≤1018,ℓ=100c\le10^{18},\ell=100
3 q≤10,ℓ=20000q\le10,\ell=20000
4 ℓ=20000\ell=20000
5 ℓ=100\ell=100

样例 1

输入:

97
3
100
9 13
13 22
5 7

输出:

1
0 1
-1
2
0 1 2 0