import sys read=sys.stdin.buffer.read readline=sys.stdin.buffer.readline readlines=sys.stdin.buffer.readlines loop=0 def LLL(b, eta_n=501, eta_d=1000, delta_n=99, delta_d=100): k = 2 kmax = 1 n = len(b) m = len(b[0]) d = [0] * (n+1) d[0] = 1 d[1] = sum(b[0][_]*b[0][_] for _ in range(m)) # H = [[1 if j==i else 0 for j in range(n)] for i in range(n)] lmd = [[0]*n for _ in range(n)] def RED(k, l): if -eta_n*d[l]<=eta_d*lmd[k-1][l-1] and eta_d*lmd[k-1][l-1]<=eta_n*d[l]: return q = (2*lmd[k-1][l-1]+d[l])//(2*d[l]) # for i in range(n): # H[k-1][i] -= H[l-1][i]*q for i in range(m): b[k-1][i] -= b[l-1][i]*q lmd[k-1][l-1] -= q*d[l] for i in range(l-1): lmd[k-1][i] -= q*lmd[l-1][i] def SWAP(k): # # swap(H[k], H[k-1]) # for i in range(n): # tmp = H[k-1][i] # H[k-1][i] = H[k-2][i] # H[k-2][i] = tmp # swap(b[k], b[k-1]) for i in range(m): tmp = b[k-1][i] b[k-1][i] = b[k-2][i] b[k-2][i] = tmp if k > 2: for j in range(1, k-1): tmp = lmd[k-1][j-1] lmd[k-1][j-1] = lmd[k-2][j-1] lmd[k-2][j-1] = tmp v = lmd[k-1][k-2] B = (d[k-2]*d[k]+v*v)//d[k-1] for i in range(k+1, kmax+1): t = lmd[i-1][k-1] lmd[i-1][k-1] = (d[k]*lmd[i-1][k-2]-v*t)//d[k-1] lmd[i-1][k-2] = (B*t+v*lmd[i-1][k-1])//d[k] d[k-1] = B def test_LLL_condition(k): global loop loop += 1 RED(k, k-1) if delta_d*d[k]*d[k-2] 2: k -= 1 k = test_LLL_condition(k) else: for l in range(k-2, 0, -1): RED(k, l) k += 1 return k while k <= n: if k <= kmax: k = test_LLL_condition(k) else: kmax = k for j in range(1, k+1): u = sum(b[k-1][_]*b[j-1][_] for _ in range(m)) for i in range(1, j): assert (d[i]*u-lmd[k-1][i-1]*lmd[j-1][i-1])%d[i-1]==0 u = (d[i]*u-lmd[k-1][i-1]*lmd[j-1][i-1])//d[i-1] if j==k: d[k] = u assert d[k] != 0 else: lmd[k-1][j-1] = u #print(loop) return b p=1000000000000000003 b=123456789987654321 n=11 mat=[[0]*n for _ in range(n)] for i in range(n-1): mat[i][i]=-b mat[i][i+1] = 1 mat[n-1][0]=p # res=LLL(mat, 1, 2, 3, 4)[0] res = LLL(mat)[0] #print(res) s=[] t=[] for i in range(n): if res[i]>=0: s.append(chr(ord('a')+res[i])) t.append('a') else: t.append(chr(ord('a')-res[i])) s.append('a') s=''.join(s) t=''.join(t) hs=0 ht=0 for i in range(n): hs+=ord(s[i])*(b**i) ht+=ord(t[i])*(b**i) hs%=p ht%=p assert hs==ht print(s[::-1]) print(t[::-1])