Harryxun/stf_run huggingface dataset:
K = int(input())

if K % 2 == 0:
    print(-1)
    exit()


def factorization(n):
    arr = []
    temp = n
    for i in range(3, n, 2):
        if i * i > n:
            break
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


arr = factorization(K)
# print(f'{arr=}')

ans = 1
for a in arr:
    b = a[0]
    time = a[1]
    # print(f'{K=}')
    v = ''
    M = set([])
    for i in range(1, 999982):
        v += '7'
        mod = int(v) % b
        if mod == 0:
            # print(f'{K=}, {i=}')
            ans *= i**time
            break
        if mod in M:
            print(f'{K=}, i=-1')
            print(-1)
            exit()
        M.add(mod)

print(ans)


### FIXED CODE ###

K = int(input())

if K == 1 or K == 7:
    print(1)
    exit()

v = 7
M = set([])
for i in range(1, K + 1):
    v = (v * 10 + 7) % K
    if v == 0:
        print(i + 1)
        exit()
    if v not in M:
        M.add(v)
    else:
        print(-1)
        exit()
n = int(input())
a = list(range(1, n))
print(sum(a))


### FIXED CODE ###

n = int(input())
ans = n * (n-1) // 2
print(ans)
import sys


def _s(): return sys.stdin.readline().strip()


def _i(): return int(sys.stdin.readline().strip())


def flip(c):
    return "1" if c == "0" else "0"


def main():
    n = _i()
    s = _s()

    lst = [0] * (n+1)
    lst[0] = 0
    for i in range(1, n+1):
        t = i % bin(i)[2:].count("1")
        lst[i] = 1 + lst[t]

    for i in range(n):
        m = s[:i] + flip(s[i]) + s[i+1:]
        t = int(m, 2) % m.count("1")
        print(lst[t] + 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def _s(): return sys.stdin.readline().strip()


def _i(): return int(sys.stdin.readline().strip())


def main():
    n = _i()
    s = _s()
    m = s.count("1")
    arr = list(range(max(1, m-1), m+2))
    d1 = {}
    for ai in arr:
        d1[ai] = [1 % ai]
        for i in range(n-1):
            d1[ai].append((2*d1[ai][-1]) % ai)

    d2 = {ai: 0 for ai in arr}
    for ai in arr:
        for i, c in enumerate(reversed(s)):
            if c == "1":
                d2[ai] = (d2[ai] + d1[ai][i]) % ai

    lst = [0] * (n+1)
    for i in range(1, n+1):
        t = i % bin(i)[2:].count("1")
        lst[i] = 1 + lst[t]

    i = n
    for c in s:
        i -= 1
        if c == "1":
            m1 = m - 1
            if m1 == 0:
                print(0)
                continue
            else:
                t = (d2[m1] - d1[m1][i]) % m1
        else:
            m1 = m + 1
            t = (d2[m1] + d1[m1][i]) % m1
        print(lst[t] + 1)


if __name__ == "__main__":
    main()
import numpy as np
import math
import collections
import bisect
import itertools
from collections import Counter

suf_xor_dict = {}
pre_xor_dict = {}


def suf_xor(N, p):
    # print(p)
    global xor_dict
    if N - len(p) + 1 in suf_xor_dict:
        return suf_xor_dict[N - len(p) + 1]

    if len(p) == 0:
        return 0
    if len(p) == 1:
        suf_xor_dict[N] = p[0]
        return p[0]
    if len(p) == 2:
        suf_xor_dict[N] = p[1]
        suf_xor_dict[N - 1] = p[0] ^ p[1]
        return(p[0] ^ p[1])
    else:
        ret = p[0] ^ suf_xor(N, p[1:])
        suf_xor_dict[N - len(p) + 1] = ret
        return ret


def pre_xor(N, p):
    global pre_xor_dict
    if len(p) in pre_xor_dict:
        return pre_xor_dict[len(p)]

    if len(p) == 0:
        return 0
    if len(p) == 1:
        pre_xor_dict[1] = p[0]
        return p[0]
    if len(p) == 2:
        pre_xor_dict[1] = p[0]
        pre_xor_dict[2] = p[0] ^ p[1]
        return(p[0] ^ p[1])
    else:
        ret = p[-1] ^ pre_xor(N, p[:-1])
        pre_xor_dict[len(p)] = ret
        return ret


def main():
    N = int(input())
    a = list(map(int, input().split()))
    ans = []
    last = pre_xor(N, a[:N - 1]) ^ suf_xor(N, a[N:])
    for i in range(N - 1):
        ans.append(pre_xor(N, a[:i]) ^ suf_xor(N, a[i + 1:]))

    ans.append(last)
    for item in ans:
        print(item, end=' ')
    print('')


if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
import math
import collections
import bisect
import itertools
from collections import Counter

suf_xor_dict = {}
pre_xor_dict = {}


def suf_xor(N, p):
    # print(p)
    global xor_dict
    if N - len(p) + 1 in suf_xor_dict:
        return suf_xor_dict[N - len(p) + 1]

    if len(p) == 0:
        return 0
    if len(p) == 1:
        suf_xor_dict[N] = p[0]
        return p[0]
    if len(p) == 2:
        suf_xor_dict[N] = p[1]
        suf_xor_dict[N - 1] = p[0] ^ p[1]
        return(p[0] ^ p[1])
    else:
        ret = p[0] ^ suf_xor(N, p[1:])
        suf_xor_dict[N - len(p) + 1] = ret
        return ret


def pre_xor(N, p):
    global pre_xor_dict
    if len(p) in pre_xor_dict:
        return pre_xor_dict[len(p)]

    if len(p) == 0:
        return 0
    if len(p) == 1:
        pre_xor_dict[1] = p[0]
        return p[0]
    if len(p) == 2:
        pre_xor_dict[1] = p[0]
        pre_xor_dict[2] = p[0] ^ p[1]
        return(p[0] ^ p[1])
    else:
        ret = p[-1] ^ pre_xor(N, p[:-1])
        pre_xor_dict[len(p)] = ret
        return ret


def main():
    N = int(input())
    a = list(map(int, input().split()))
    ans = []
    pre_xor_list = [0]
    suf_xor_list = [0]
    for i in range(N):
        pre_xor_list.append(pre_xor_list[i] ^ a[i])
        suf_xor_list.append(suf_xor_list[i] ^ a[N - i - 1])

    pre_xor_list = pre_xor_list[1:]
    suf_xor_list = suf_xor_list[1:]

    for i in range(N):
        ans.append((0 if i - 1 < 0 else pre_xor_list[i - 1]) ^ (0 if i >= N - 1 else suf_xor_list[N - i - 2]))

    for item in ans:
        print(item, end=' ')
    print('')


if __name__ == "__main__":
    main()
n, m, k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

ab_list = a_list + b_list
ab_list.sort()

dp = [False] * 200000*2

dp[0] = ab_list[0]
j = ab_list[0]

count=1

for i in range(1,len(ab_list)):
    # print(ab_list[i]+j)
    a_min = a_list.pop(0)
    b_min = b_list.pop(0)
    dp[i] = min(a_min, b_min) + j
    j += ab_list[i]
    
    if dp[i]<=k:
        count+=1
    
    if j+ab_list[i+1]>k:
        break

    

print(count)




### FIXED CODE ###

n, m, k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

a = []
a.append(0)
for i in range(n):
    a.append(a[i]+a_list[i])
    
b = []
b.append(0)
for i in range(m):
    b.append(b[i]+b_list[i])
    

ans = 0
for i in range(n+1):
    if a[i]>k:
        break
    while a[i] + b[m] > k:
        m -= 1
    ans = max(ans, i+m)
    
print(ans)
# -*- coding: utf-8 -*-

import sys
from itertools import combinations
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
xy=[]
for i in range(N):
    x,y=MAP()
    xy.append((x, y))

C=Counter()
for comb in combinations(xy, 2):
    a,b=comb
    C[(a[0]-b[0], a[1]-b[1])]+=1

mx=max(C.values())
print(N-mx)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from itertools import combinations
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()

if N==1:
    print(1)
    exit()

xy=[]
for i in range(N):
    x,y=MAP()
    xy.append((x, y))

C=Counter()
for comb in combinations(xy, 2):
    a,b=comb
    if a[0]-b[0]==0:
        key=INF
    else:
        key=(a[1]-b[1])/(a[0]-b[0])
    C[(key, abs(a[0]-b[0]), abs(a[1]-b[1]))]+=1

mx=max(C.values())
print(N-mx)
N = int(input())
p = list((int, input().split()))
cnt = 0
 
for i in range(N):
  if p[i] != i+1:
    cnt += 1
 
if cnt==0 or cnt==2 :
  print('YES')
else:
  print('NO')

### FIXED CODE ###

N = int(input())
p = list(map(int, input().split()))
cnt = 0
 
for i in range(N):
  if p[i] != i+1:
    cnt += 1
 
if cnt==0 or cnt==2 :
  print('YES')
else:
  print('NO')
from collections import deque
h,w = map(int,input().split())
#0が進めるところ、1は無理
lis = [[1 if l == '#' else 0 for l in list(input())] for _ in range(h)]
#ゴールは9
lis[h-1][w-1] = 9
#print(lis)
#[[0, 0, 1], [1, 0, 0], [0, 0, 9]]

#この問題ではbfsを始める前に、もともと移動可能だったところの数を記録しておく
road = 0
for row in lis:
    for column in row:
        if column != 1:
            road +=1

count = 0
#(開始x,開始y,移動回数)
pos = [[0,0,0]]
que = deque(pos)
while len(pos)>0:
    x,y,depth = pos.popleft()

    if lis[x][y] == 9:
        count = depth
        break

    #探索済みのところは、1にする
    lis[x][y] = 1

    #遷移先は0or9なので、1以外なら行ける
    if x-1>=0 and lis[x-1][y] != 1:
        pos.append([x-1,y,depth+1])
    if x+1<h and lis[x+1][y] != 1:
        pos.append([x+1,y,depth+1])
    if y-1>=0 and lis[x][y-1] != 1:
        pos.append([x,y-1,depth+1])
    if y+1<w and lis[x][y+1] != 1:
        pos.append([x,y+1,depth+1])

#そもそも行けない
if count == 0:
    print(-1)
#(移動可能マス数) - (移動する道順上のマスの数 ＝ 最短の移動回数＋１）
else:
    print(road-(count+1))

### FIXED CODE ###

h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('#'*w))
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1
 
 
print(-1)
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


ups = []
downs = []
eqs = []
for i in range(3):
    if A[i] < B[i]:
        ups.append((A[i], B[i]))
    elif A[i] == B[i]:
        eqs.append((A[i], B[i]))
    else:
        downs.append((A[i], B[i]))
ans = N

if len(eqs) == 3:
    print(N)
    exit()

if len(ups) == 0:
    tmp = A
    A = B
    B = tmp
    tmp = ups
    ups = downs
    downs = tmp

if len(ups) == 3:
    gold_diff = B[0]-A[0]
    silver_diff = B[1]-A[1]
    cupper_diff = B[2]-A[2]
    for gold in range(N//A[0]+1):
        left = N - gold*A[0]
        for silver in range(left//A[1]+1):
            cupper = (left - silver*A[1])//A[2]
            tmp_ans = (N
                       + gold*gold_diff
                       + silver*silver_diff
                       + cupper*cupper_diff)
            ans = max(ans, tmp_ans)
    print(ans)
elif len(ups) == 2:
    gold_diff = ups[0][1]-ups[0][0]
    silver_diff = ups[1][1]-ups[1][0]
    for gold in range(N//ups[0][0]+1):
        left = N - gold*ups[0][0]
        silver = left // ups[1][0]
        tmp_ans = (N
                   + gold*gold_diff
                   + silver*silver_diff)
        ans = max(ans, tmp_ans)
    if len(downs) == 1:
        diff = downs[0][0]-downs[0][1]
        ans += (ans // downs[0][1]) * diff
    print(ans)
elif len(ups) == 1:
    bbans = N + (N//ups[0][0])*(ups[0][1]-ups[0][0])
    if len(downs) == 2:
        tmp_ans = bbans
        gold_diff = downs[0][0]-downs[0][1]
        silver_diff = downs[1][0]-downs[1][1]
        for gold in range(bbans//downs[0][1]+1):
            left = bbans - gold*downs[0][1]
            silver = left // downs[1][1]
            tmp_ans = (bbans
                       + gold*gold_diff
                       + silver*silver_diff)
            ans = max(ans, tmp_ans)
    elif len(downs) == 1:
        ans =bbans + (bbans//downs[0][1])*(downs[0][0]-downs[0][1])
    eise:
        ans = bbans
    print(ans)


### FIXED CODE ###

N, K = map(int, input().split(" "))
if K == 1:
    print(0)
    exit()
print(str(N - K))
from collections import deque

N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
O = min(N, K)
for i in range(O+1):
    for j in range(O-i+1):
        if i + j > O:
            break
        DV = deque(V)
        S = 0
        nums = []
        for _ in range(i):
            nums.append(DV.popleft())
        for _ in range(j):
            nums.append(DV.pop())
        nums.sort()
        for n in range(min(K-i-j, len(nums))):
            if nums[n] >= 0:
                break
            del nums[n]
        ans = max(ans, sum(nums))
print(ans)

### FIXED CODE ###

from collections import deque

N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
O = min(N, K)
for i in range(O+1):
    for j in range(O-i+1):
        if i + j > O:
            break
        DV = deque(V)
        S = 0
        nums = []
        for _ in range(i):
            nums.append(DV.popleft())
        for _ in range(j):
            nums.append(DV.pop())
        nums.sort()
        S = sum(nums)
        for n in range(min(K-i-j, len(nums))):
            if nums[n] >= 0:
                break
            S -= nums[n]
        ans = max(ans, S)
print(ans)
n, m = map(int, input().split())
print(max(i for i in range(2, 100000) if m % i == 0 and m / i >= n))

### FIXED CODE ###

n, m = map(int, input().split())
values = []

def pfac(n):
    values = [1, n]
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            values.append(i)
            values.append(n // i)
    return values


for i in pfac(m):
    if m % i == 0 and m / i >= n:
        values.append(i)
print(max(values))
M, K = map(int, input().split())

if M == 0:
    print(0, 0)
    quit()

if M == 1:
    if K == 0:
        print(0, 0, 1, 1)
    else:
        print(-1)
    quit()

if K >= (1 << M):
    print(-1)
    quit()


A = [i for i in range(1 << M) if i != K]
print(*A, K, *A[::-1], K)


### FIXED CODE ###

import itertools
M, K = map(int, input().split())

if K >= (1 << M):
    print(-1)
    quit()

if M == 0:
    print(0, 0)
    quit()

if M == 1:
    if K == 0:
        print(0, 0, 1, 1)
    else:
        print(-1)
    quit()


A = [i for i in range(1 << M) if i != K]
print(*(A + [K] + A[::-1] + [K]))
a = sorted(map(int), list(input().split()))
print(10*a[0]+a[1]+a[2])


### FIXED CODE ###

a = sorted(list(map(int, input().split())))
print(10*a[2]+a[1]+a[0])
import sys
from operator import itemgetter
input = sys.stdin.readline

_n, *lrlist = map(int, open(0).read().split())
Lp, Rq = max(lrlist[::2]), min(lrlist[1::2])

st = sorted([(max(r - Lp + 1, 0), max(Rq - l + 1, 0)) for l, r in lrlist])
ans = max([r - l + 1 for l, r in lrlist]) + max(Rq - Lp + 1, 0)

for index, (a, b) in enumerate(st):
    if index:
        continue


for i in range(1, _n):
    s, t = st[:i], st[i:]
    min_b, min_a = sorted(s, key=itemgetter(1))[0][1], t[0][0]

    ans = max(min_a + min_b, ans)

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

_n = int(input())
lrlist = [list(map(int, input().split())) for _ in range(_n)]
Lp, Rq = max(l for l, r in lrlist), min(r for l, r in lrlist)

st = sorted([(max(r - Lp + 1, 0), max(Rq - l + 1, 0)) for l, r in lrlist], key=lambda x: (x[0], -x[1]))
ans = max([r - l + 1 for l, r in lrlist]) + max(Rq - Lp + 1, 0)

min_b = 10 ** 9
for i in range(_n - 1):
    min_b = min(st[i][1], min_b)
    ans = max(ans, min_b + st[i + 1][0])

print(ans)
S = input()
c = 0
ans = 0
for i in range(3):
  if S[i] == 'R':
    c++
  else:
    ans = max(c,ans)
print(ans)

### FIXED CODE ###

S = input()
c = 0
ans = 0
for i in range(3):
  if S[i] == 'R':
    c+=1
  else:
    ans = max(c,ans)
    c = 0
ans = max(c,ans)
print(ans)
if S == "ABC":
  print("ARC")
else:
  print("ABC")


### FIXED CODE ###

S = input()
if S == "ABC":
  print("ARC")
else:
  print("ABC")
N, X = [int(i) for i in input().split()]
x_ls = [int(i) for i in input().split()]
x_ls = [abs(x - X) for x in x_ls]
while True:
    if all([x % min(x_ls) == 0 for x in x_ls]):
        break
    else:
        x_ls = [x % min(x_ls) for x in x_ls]
print(min(x_ls))

### FIXED CODE ###

N, X = [int(i) for i in input().split()]
x_ls = [int(i) for i in input().split()]
x_ls = [abs(x - X) for x in x_ls]
while True:
    min_x = min(x_ls)
    x_ls = [x % min_x for x in x_ls]
    if not any(x_ls):
        break
    x_ls = [x for x in x_ls if x != 0]
print(min_x)
li = input()
li2 =[]
for n in li:
    if n == "0":
        li2.append("0")
    elif n == "1":
        li2.append("1")
    elif n == "B":
        li2.pop()
print("".join(li2))

### FIXED CODE ###

li = input()
li2 =[]
for n in li:
    if n == "0":
        li2.append("0")
    elif n == "1":
        li2.append("1")
    elif n == "B":
        if not len(li2) == 0:
            li2.pop()
print("".join(li2))
import numpy as np


def chmin(a1, a2):
    if a1 <= a2:
        return a1
    elif a1 > a2:
        return a2


n, m = map(int, input().split())
a = np.zeros(m)
for i in range(m):
    a[i] = int(input())

dp = np.full(n + 1, np.inf)
dp[0] = 1
if a[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""


### FIXED CODE ###

n, m = map(int, input().split())
A = set()
for i in range(m):
    a = int(input())
    A.add(a)
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in A:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""
import numpy as np

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

b = [0] * M
c = [0] * M
for i in range(M):
    b[i], c[i] = map(int, input().split())

lst = np.array([c, b]).T.tolist()
lst.sort(reverse=True)
c = np.array(lst).T.tolist()[0]
b = np.array(lst).T.tolist()[1]

k = 0
judge = 0
for i in range(M):
    for j in range(b[i]):
        if A[k] < c[i]:
            A[k] = c[i]
            k += 1
        else:
            judge = 1
            break
    if judge == 1:
        break

print(sum(A))

### FIXED CODE ###

import numpy as np

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

b = [0] * M
c = [0] * M
for i in range(M):
    b[i], c[i] = map(int, input().split())

lst = np.array([c, b]).T.tolist()
lst.sort(reverse=True)
c = np.array(lst).T.tolist()[0]
b = np.array(lst).T.tolist()[1]

k = 0
judge = 0
for i in range(M):
    if k+b[i]-1 < N:
        if A[k+b[i]-1] < c[i]:
            A[k:k+b[i]] = [c[i]] * b[i]
            k += b[i]
        else:
            for j in range(b[i]):
                if k < N:
                    if A[k] < c[i]:
                        A[k] = c[i]
                        k += 1
                    else:
                        judge = 1
                        break
            if judge == 1:
                break
    elif k < N:
        for j in range(b[i]):
            if k < N:
                if A[k] < c[i]:
                    A[k] = c[i]
                    k += 1
                else:
                    judge = 1
                    break
        if judge == 1:
            break
    else:
        break

print(sum(A))
S = input()
T = input()
U = T-T[-1]
if S == U:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S = input()
T = input()
U = T[:-1]
if S == U:
  print("Yes")
else:
  print("No")
def parse(S):
    poly = []
    t = []
    for x in S.split('+'):
        if '-' in x:
            t = t + ['-' + a if i != 0 else a for i, a in enumerate(x.split('-'))]
        else:
            t.append(x)

    for x in t:
        if '^' in x:
            t = x.split('x^')
            if len(t[0]) == 0:
                a = 1
            else:
                a = int(t[0])
            b = int(t[1])
        else:
            if 'x' in x:
                if x == 'x':
                    a = 1
                else:
                    a = int(x[:-1])
                b = 1
            else:
                a = int(x)
                b = 0

        poly.append((a, b))

    return poly

def calc_yaku(n):
    ret = []
    for i in range(n + 1):
        if i != 0 and n % i == 0:
            ret.append(i)

    return reversed(sorted(ret + [-x for x in ret]))

def calc(poly, x):
    ret = 0
    for p in poly:
        ret += p[0] * x ** p[1]

    return ret


def solve(S):
    poly = parse(S)
    n = abs(poly[-1][0])
    yaku = calc_yaku(n)

    ans = []
    for x in yaku:
        if calc(poly, x) == 0:
            ans.append(-x)

    for x in ans:
        if x > 0:
            print('(x+{})'.format(x), end='')
        else:
            print('(x{})'.format(x), end='')

    print('')

S=input()
solve(S)

### FIXED CODE ###

def parse(S):
    poly = []
    t = []
    for x in S.split('+'):
        if '-' in x:
            t = t + ['-' + a if i != 0 else a for i, a in enumerate(x.split('-'))]
        else:
            t.append(x)

    for x in t:
        if '^' in x:
            t = x.split('x^')
            if len(t[0]) == 0:
                a = 1
            else:
                a = int(t[0])
            b = int(t[1])
        else:
            if 'x' in x:
                if x == 'x':
                    a = 1
                elif x == '-x':
                    a = -1
                else:
                    a = int(x[:-1])
                b = 1
            else:
                a = int(x)
                b = 0

        poly.append((a, b))

    return poly

def calc_yaku(n):
    ret = []
    for i in range(n + 1):
        if i != 0 and n % i == 0:
            ret.append(i)

    return reversed(sorted(ret + [-x for x in ret]))

def calc(poly, x):
    ret = 0
    for p in poly:
        ret += p[0] * x ** p[1]

    return ret


def solve(S):
    poly = parse(S)
    n = abs(poly[-1][0])
    yaku = calc_yaku(n)

    ans = []
    for x in yaku:
        if calc(poly, x) == 0:
            ans.append(-x)

    for x in ans:
        if x > 0:
            print('(x+{})'.format(x), end='')
        else:
            print('(x{})'.format(x), end='')

    print('')

S=input()
solve(S)