Fraction quruluş (Həll təhlili)

Qeyd: Lukas teoremi tək binomiyal əmsallar üçün sadə bir şərt təqdim edir.

Lukas teoremine görə, \binom{n}{k} \equiv 1 \pmod 2 yalnız $k$ və n-k-nın ikili sistemdə toplanması zamanı daşınmalar olmadıqda baş verir. Bu, k \text{ \& } (n-k) = 0 bit AND əməliyyatına bərabərdir, ya da daha sadə desək, k \text{ \& } n = k.

Gəlin kiçik dəyərlər üçün a_i, a_j \in \{1, 2, 3\} şərtini qiymətləndirək:

• \binom{1}{1} = 1 (Tək)

• \binom{2}{2} = 1 (Tək)

• \binom{2}{1} = 2 (Cüt)

• \binom{3}{3} = 1 (Tək)

• \binom{3}{2} = 3 (Tək)

• \binom{3}{1} = 3 (Tək)

Qeyd edin ki, yalnız $3$ dəyərini istifadə etdikdə, istənilən $(3,3)$ cütü $f(a)$-ya kömək edir. Lakin, $1$ və ya $2$ dəyərlərini daxil etdikdə, cütləri "sındıra" bilərik. Xüsusilə, $3$ dəyəri $1,2,$ və $3$ ilə tək binomiyal əmsal yaradır. $1$ dəyəri yalnız digər $1$ və ya $3$ ilə tək əmsal yaradır. $2$ dəyəri yalnız digər $2$ və ya $3$ ilə tək əmsal yaradır. Vacibdir ki, $(1,2)$ cütü \binom{2}{1} = 2-yə səbəb olur ki, bu da cütdür.

Quruluş: Tam olaraq $x$ cütü əldə etmək üçün, $s$ ədəd $3$ dəyəri ilə başlayırıq, burada \binom{s}{2} \ge x. Bu, bizə \binom{s}{2} tək cüt verir. Bu sayı dəqiq $x$-ə endirmək üçün, rem = \binom{s}{2} - x cütünü çıxarmalıyıq. Biz $rem$ ədədini $3$-dən $1$-ə çevirə bilərik və $1$ ədədini $2$-yə çevirə bilərik. Çünki $(1,2)$ cütü cütdür, tək $2$ $rem$-də olan $1$ ədədi ilə tək cüt yaratmayacaq, bu da ümumi sayı dəqiq $rem$ qədər azaldır.

from collections import defaultdict as dd

def C(x): return (x*(x-1))//2

mp=dd(int)
for i in range(1,10**5):
    mp[(i*(i-1))//2]=i

def solve():
    x,y=map(int,input().split())
    if(y<=1):
        for i in range(1,int(2*(x**0.5))+2):
            if(C(i)==x):
                print(i)
                print(*([1]*i))
                return
    if(y==2):
        for c1 in range(1,10**5):
            t = x - C(c1)
            if(t >= 0 and mp[t]!=0):
                c2=mp[t]
                print(c1+c2)
                print(*([1]*c1+[2]*(c2)))
                return
    if(y>0):
        l,r=1,2*10**9
        s=r 
        while(l<=r):
            m=l+(r-l)//2
            if((m*(m-1))//2>=x):
                s=m
                r=m-1
            else:
                l=m+1
        rem=s*(s-1)//2-x 
        c1,c2,c3=0,0,0
        if(rem==0):
            c3=s
        else:
            c1=rem
            c2=1
            c3=s-c1-c2 
        print(int(c1+c2+c3))
        print(*([1]*int(c1)+[2]*int(c2)+[3]*int(c3)))
        return

for _ in range(int(input())):
    solve()