def quotient_range(n): ret=[] i=1 while i<=n: q=n//i j=n//q+1 ret.append((i,j)) i=j return ret def floor_sum(n,m,a,b): ans=0 while True: if a>=m: ans+=(n-1)*n*(a//m)//2 a%=m if b>=m: ans+=n*(b//m) b%=m y_max=(a*n+b)//m x_max=(y_max*m-b) if y_max==0: return ans ans+=(n-(x_max+a-1)//a)*y_max n,m,a,b=y_max,a,m,(a-x_max%a)%a def mertens_table(n): if n==0: return [[0],[0]] b=10**4 small=[1]*(n//b+1) large=[1]*(b+1) small[0]=0 large[0]=0 prime=[1]*(n//b+1) for p in range(2,n//b+1): if not prime[p]: continue for j in range(p,n//b+1,p): if j>p: prime[j]=0 if j%(p*p)==0: small[j]=0 else: small[j]*=-1 for i in range(1,n//b): small[i+1]+=small[i] for i in range(b,0,-1): l=2 while l<=n//i: q=n//(i*l) r=n//(i*q)+1 if i*l<=b: large[i]-=large[i*l]*(r-l) else: large[i]-=small[n//(i*l)]*(r-l) l=r return small,large def range_g(L,R,P,Q): return floor_sum(R,Q,P,0)-floor_sum(L,Q,P,0) def count(n,P,Q): res=0 for L,R in QR: x=n//L if x1: mid=(ok+ng)>>1 if count(n,mid,n*n)>=k: ok=mid else: ng=mid ng2,ok2=0,n*n while ok2-ng2>1: mid=(ok2+ng2)>>1 cnt1=floor_sum(mid,n*n,ok-1,ok-1) cnt2=floor_sum(mid,n*n,ok,ok) if cnt1!=cnt2: ok2=mid else: ng2=mid den=ok2 num=ok*den//(n*n) if rev: den,num=num,den print(str(num)+'/'+str(den))