离线版OEIS

题号：NC221005
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

想必你一定做过很多找规律的题目吧

用1*2的多米诺骨牌铺2*n的方格......

用1*2的多米诺骨牌铺4*n的方格.......

n条直线可以把平面分割成几个区域呢？n条折线呢？

这类题目有很多...智乃酱在AC掉很多找规律的线性地推题目后，灵机一动，为什么不写个程序帮我找规律呢？

给你使用暴力程序得出在n=1,2,3,4,.... ${maxn}$ 时的答案。

如果你认为存在递推关系，请输出递推表达式，否则请输出"No_solution"。

我们规定，如果输入的数字存在线性递推关系，则仅会包含。

1、该项的前k项 $(k \leq 5)$ 分别乘以一个整数系数求和的递推关系。

2、最高次数最多为3次的常数多项式，且多项式的系数也为整数。

换句话说，你要求得的递推式是下式的一个子式。

$a[i]=k_1 \times a[i-1] +k_2 \times a[i-2] +k_3 \times a[i-3] +k_4 \times a[i-4] +k_5 \times a[i-5] +k_6\times i^3+k_7\times i^2+k_8\times i^1+k_9$

如果这 ${maxn}$ 个数据虽然存在系数为实数的递推关系，但是不存在系数为整数的递推关系时，也认为是无解的，此时也应当输出“No_solution”。

输入的测试数据还保证，如果存在符合题目要求的递推式，则至少存在一个递推式的各项系数在32位int型能表示的范围内，并且在计算前 ${maxn}$ 的值时，计算过程和最终结果不会超过64位整形的最大范围。

输入描述:

第一行一个正整数，表示有T组样例

对于每组样例，第一行一个正整数。

输入数据保证maxn远大于最简递推式的阶数（如果存在的话）。

接下来一行maxn个整数，表示暴力程序跑出的答案。

输出描述:

如果输入数据中不存在由前k项的常数倍与常数多项式组成的递推式，请输出"No_solution"
输入数据保证如果递推式中存在常数多项式，则最高次数为3次。

注意你输出的各种系数都必须是整数，并且保证该递推式在计算递推的中间过程不会有数据超过64位整形能够表示的最大范围。

如果存在一个各项系数为整数的递推式，请按照如下规则输出：

如需定义前k项的初始值。请先输出一行定义初始值，但是最多只能指定前5项的初始值。
请输出  a[i]=val  i表示第几项(i<=k)，val表示初始值。当k不等于1时，每一项之间使用一个","隔开。


比如定义斐波那契数列1 1 2 3 5 8 11 23 34 .....的前两项
就可输出"a[1]=1,a[2]=1"或者"a[2]=1,a[1]=1"

当定义完初始值或者无需定义初始值时

请输出a[i]=(递推表达式)
比如在定义完斐波那契数列的前两项后，请输出一行a[i]=a[i-1]+a[i-2]

对于常数多项式，三次幂要写成k*i*i*i的形式，两次幂要写成k*i*i的形式，一次幂次写成k*i，常数直接写k。

对于表达式的格式没有特定要求。特判程序可以识别连加表达式。

比如a[i]=a[i-1]+a[i-2]
如果写成a[i]=+1*a[i-1]+1a[i-2]+0a[i-3]+0*a[i-4]+0*i*i*i+0*i+0（系数直接写在项的前面，或者写成系数*项都是可以的，并且当系数的绝对值为1时可以省略不写，没有的项既可以不写也可以写成0*的形式），也能得到AC的结果。

但是每一项之间必须使用符号隔开，且不允许两符号直接相连。也就是输出的表达式必须合法。

同时，如果某个数列有多种表述方式的话，你可以输出任意一种，但是请注意最多只能指定前5项的初始值。

比如数列1 2 3 4 5 6 7 8 9 10 11 12 13 14...

既可以输出一行：
a[i]=i

也可以输出两行：
a[1]=1
a[i]=a[i-1]+1

示例1

输入

复制

12
20
1300000264 2400000529 4900000736 9400000819 16500000712 26800000349 40899999664 59399998591 82899997064 111999995017 147299992384 189399989099 238899985096 296399980309 362499974672 437799968119 522899960584 618399952001 724899942304 842999931427
20
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
20
0 -3 248 -1001 4742 -21475 98124 -447437 2041170 -9310743 42471608 -193736321 883738622 -4031220235 18388624164 -83880680117 382626152490 -1745369401983 7961594705168 -36317234721641
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20
20
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
20
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
20
1 -2 3 -4 5 -560 -1504 -2339 -2874 -1654 1982 5758 6146 -2489 -24255 -50815 -59158 -17723 94346 241315
20
1 -2 3 -4 5 -553 -1507 -2336 -3978 -5791 -6267 -7826 -9795 -8947 -11468 -16675 -15702 -21764 -33809 -28091
20
1 -2 3 -4 5 -550 -1510 -2333 -3978 -5794 -7902 -14000 -21336 -29509 -45317 -59863 -79716 -124151 -166100 -226259
20
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12 13 -14 15 -16 17 -18 19 -20
20
1 96 5 4 6 21 3 1 5 6 4 8 9 5 4 6 3 2 1 5

12
20
1300000264 2400000529 4900000736 9400000819 16500000712 26800000349 40899999664 59399998591 82899997064 111999995017 147299992384 189399989099 238899985096 296399980309 362499974672 437799968119 522899960584 618399952001 724899942304 842999931427
20
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
20
0 -3 248 -1001 4742 -21475 98124 -447437 2041170 -9310743 42471608 -193736321 883738622 -4031220235 18388624164 -83880680117 382626152490 -1745369401983 7961594705168 -36317234721641
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20
20
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
20
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
20
1 -2 3 -4 5 -560 -1504 -2339 -2874 -1654 1982 5758 6146 -2489 -24255 -50815 -59158 -17723 94346 241315
20
1 -2 3 -4 5 -553 -1507 -2336 -3978 -5791 -6267 -7826 -9795 -8947 -11468 -16675 -15702 -21764 -33809 -28091
20
1 -2 3 -4 5 -550 -1510 -2333 -3978 -5794 -7902 -14000 -21336 -29509 -45317 -59863 -79716 -124151 -166100 -226259
20
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12 13 -14 15 -16 17 -18 19 -20
20
1 96 5 4 6 21 3 1 5 6 4 8 9 5 4 6 3 2 1 5

输出

复制

a[i]=99999989*i*i*i+100000037*i*i+100000231*i+1000000007

a[1]=1,a[2]=1
a[i]=a[i-1]+a[i-2]

a[1]=0,a[2]=-3
a[i]=-5*a[i-1]-2*a[i-2]+233

a[i]=i

a[i]=-i

a[i]=8

a[1]=0
a[i]=-a[i-1]+1

a[1]=1,a[2]=-2,a[3]=3,a[4]=-4,a[5]=5
a[i]=a[i-1]-a[i-2]-3*a[i-4]-3*i*i*i+2*i*i+1

a[1]=1,a[2]=-2,a[3]=3,a[4]=-4,a[5]=5
a[i]=a[i-1]-a[i-2]+2*a[i-3]-3*a[i-4]+a[i-5]-3*i*i*i+2*i*i+1

a[1]=1,a[2]=-2,a[3]=3,a[4]=-4,a[5]=5
a[i]=a[i-1]-a[i-2]+2*a[i-3]-3*a[i-4]+4*a[i-5]-3*i*i*i+2*i*i+1

a[1]=1,a[2]=-2
a[i]=-2*a[i-1]-a[i-2]

No_solution

说明

多组样例之间的空行是为了让大家看的更清楚，实际上你的程序不被要求样例与样例之间的额外空行。

如果你的运算过程使用了实数计算，请使用long double类型代替double，避免精度不足导致的WA。