Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())
al = list(map(int, input().split()))
boxs = []
cnts = [0]*(n+1)
for i in range(n,0,-1):
    if cnts[i]%2 != al[i-1]:
        boxs.append(i)
        for j in range(1, int(i**0.5)+1):
            if i%j == 0:
                cnts[j] += 1
                if j*j != i: cnts[i//j] += 1
    print(i, boxs, cnts)


print(len(boxs))
for b in boxs: print(b)

Fixed submission:
def divs(n):
    res = []
    i = 1
    while i**2 <= n:
        if n%i == 0: 
            res.append(i)
            if i**2 != n:
                res.append(n//i)
        i+=1 
    return res


def main():
    n = int(input())
    al_0 = list(map(int, input().split()))
    if sum(al_0) == 0:
        print(0)
        return

    al = [0] + al_0
    divs_cnts = [0]*(n+1)
    ans = []
    for i in range(n,0,-1):
        if divs_cnts[i]%2 != al[i]%2:
            ans.append(i)
            div_l = divs(i)
            for d in div_l:
                divs_cnts[d] += 1

    print(len(ans))
    print(*ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def divs(n):
    res = []
    i = 1
    while i**2 <= n:
        if n%i == 0: 
            res.append(i)
            if i**2 != n:
                res.append(n//i)
        i+=1 
    return res


def main():
    n = int(input())
    al_0 = list(map(int, input().split()))
    if sum(al_0) == 0:
        print(0)
        return

    al = [0] + al_0
    divs_cnts = [0]*(n+1)
    ans = []
    for i in range(n,0,-1):
        if divs_cnts[i]%2 != al[i]%2:
            ans.append(i)
            div_l = divs(i)
            for d in div_l:
                divs_cnts[d] += 1

    print(len(ans))
    print(*ans)


if __name__ == "__main__":
    main()

Fixed submission:
def divs(n):
    res = []
    i = 1
    while i**2 <= n:
        if n%i == 0: 
            res.append(i)
            if i**2 != n:
                res.append(n//i)
        i+=1 
    return res


def main():
    n = int(input())
    al_0 = list(map(int, input().split()))
    if sum(al_0) == 0:
        print(0)
        return

    al = [0] + al_0
    divs_cnts = [0]*(n+1)
    ans = []
    for i in range(n,0,-1):
        if divs_cnts[i]%2 != al[i]%2:
            ans.append(i)
            div_l = divs(i)
            for d in div_l:
                divs_cnts[d] += 1

    print(len(ans))
    print(*ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

n = int(input())
col_maxs = []
for _ in range(n):
    a = int(input()) * (-1)
    if not col_maxs:
        col_maxs.append(a)
        continue

    curr_max = col_maxs[-1]
    if a >= curr_max:
        col_maxs.append(a)
    else:
        # aより大きい最小要素のindex/value
        ind = bisect_right(col_maxs, a)
        col_maxs[ind] = a

print(len(col_maxs))

Fixed submission:
import bisect
import sys
input = sys.stdin.readline

n = int(input())
colors_maxs = []

colors_maxs.append(int(input()) *(-1) )
for _ in range(n-1):
    a = int(input()) * (-1)
    if colors_maxs[-1] <= a:
        colors_maxs.append(a)
    else:
        ind = bisect.bisect_right(colors_maxs, a) # -> 4
        colors_maxs[ind] = a

print(len(colors_maxs))
Buggy python submission (verdict: Runtime Error):
def dfs(curr_v, pare_v, curr_sum, visited, g):
    if curr_sum%2 == 0:
        visited[curr_v] = 0
    else:
        visited[curr_v] = 1
    for neib_vw in g[curr_v]:
        if neib_vw[0] == pare_v: continue
        dfs(neib_vw[0], curr_v, curr_sum+neib_vw[1], visited, g)
    

N = int(input())
g = [ [] for _ in range(N+1)]
visited = [-1] * (N+1)

for _ in range(N-1):
    u, v, w = map(int, input().split()) 
    w%=2
    g[u].append((v,w))
    g[v].append((u,w))

dfs(1, -1, 0, visited, g)
for p in visited[1:]:
    print(p)
    



Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(curr_v, pare_v, curr_sum, visited, g):
    if curr_sum%2 == 0:
        visited[curr_v] = 0
    else:
        visited[curr_v] = 1
    for neib_vw in g[curr_v]:
        if neib_vw[0] == pare_v: continue
        dfs(neib_vw[0], curr_v, curr_sum+neib_vw[1], visited, g)
    

N = int(input())
g = [ [] for _ in range(N+1)]
visited = [-1] * (N+1)

for _ in range(N-1):
    u, v, w = map(int, input().split()) 
    w%=2
    g[u].append((v,w))
    g[v].append((u,w))

dfs(1, -1, 0, visited, g)
for p in visited[1:]:
    print(p)
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/dp/tasks/dp_f?lang=ja


def lcs(s1,s2):
    n1,n2 = len(s1),len(s2)
    dp = [ [0]*(n2+1) for _ in range(n1+1) ]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
    return dp[-1][-1]



for _ in range(int(input())):
    s1 = input()
    s2 = input()
    ans = lcs(s1,s2)
    print(ans,flush=True)

Fixed submission:
# https://atcoder.jp/contests/dp/tasks/dp_f?lang=ja

# get LCS length
def lcs_len(s1,s2):
    n1,n2 = len(s1),len(s2)
    dp = [ [0]*(n2+1) for _ in range(n1+1) ]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
    return dp[-1][-1]

# get LCS string
def lcs_str(s1,s2):
    n1,n2 = len(s1),len(s2)
    dp = [ [0]*(n2+1) for _ in range(n1+1) ]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
    ansr = []
    i,j = n1,n2
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]: i -= 1
        elif dp[i][j] == dp[i][j-1]: j -= 1
        else: 
            ansr.append(s1[i-1])
            i -= 1
            j -= 1
    ans = ansr[::-1]
    return ''.join(ans)


s1 = input()
s2 = input()
ans = lcs_str(s1,s2)
print(ans,flush=True)
Buggy python submission (verdict: Runtime Error):
import bisect

n,m = map(int, input().split())

n_facs_s = []
n_facs_l = []
for i in range(1, int(-(-n**0.5//1))+1):
    if m%i == 0:
        n_facs_s.append(i)
        n_facs_l.append(m//i)

n_faces = n_facs_s + n_facs_l
ind = bisect.bisect_right(n_faces, n)
print(m//n_faces[ind])


Fixed submission:
import bisect

n,m = map(int, input().split())

n_facs_s = []
n_facs_l = []
for i in range(1, int(-(-m**0.5//1))+1):
    if m%i == 0:
        n_facs_s.append(i)
        n_facs_l.append(m//i)


n_faces = n_facs_s + n_facs_l[::-1]
ind = bisect.bisect_right(n_faces, n)
if n_faces[ind-1] == n:
    ind-=1
print(m//n_faces[ind])

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int, input().split())

for i in range(n,m+1):
    if m%i == 0: 
        print(m//i)
        exit()

Fixed submission:
import bisect

n,m = map(int, input().split())

n_facs_s = []
n_facs_l = []
for i in range(1, int(-(-m**0.5//1))+1):
    if m%i == 0:
        n_facs_s.append(i)
        n_facs_l.append(m//i)


n_faces = n_facs_s + n_facs_l[::-1]
ind = bisect.bisect_right(n_faces, n)
if n_faces[ind-1] == n:
    ind-=1
print(m//n_faces[ind])
Buggy python submission (verdict: Runtime Error):
n,m = map(int, input().split())
A = list(map(int, input().split()))

rem_cnts = {}
curr_sum_rem = 0
for a in A:
    curr_sum_rem += a
    curr_sum_rem%=m
    rem_cnts.setdefault(curr_sum_rem,0)
    rem_cnts[curr_sum_rem] += 1

ans = 0
for cnt in rem_cnts.values():
    ans += cnt*(cnt-1)//2
ans += rem_cnts[0]

print(ans)

Fixed submission:
n,m = map(int, input().split())
A = list(map(int, input().split()))

rem_cnts = {0:0}
curr_sum_rem = 0
for a in A:
    curr_sum_rem += a
    curr_sum_rem%=m
    rem_cnts.setdefault(curr_sum_rem,0)
    rem_cnts[curr_sum_rem] += 1

ans = 0
for cnt in rem_cnts.values():
    ans += cnt*(cnt-1)//2
ans += rem_cnts[0]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m,d = map(int, input().split())

if d != 0:
    top = 2*(n-d)*pow(n,m-2)*(m-1)
else:
    top = n*pow(n,m-2)*(m-1)
bottom = pow(n,m)

print(top/bottom)

Fixed submission:
n,m,d = map(int, input().split())

if d != 0:
    top = 2*(n-d)*(m-1)
else:
    top = n*(m-1)
bottom = pow(n,2)

print(top/bottom)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

n,c = map(int, input().split())
cln = list(range(0,c))
cpl = list(permutations(cln,3))

dl = []
for _ in range(c):
    row = list(map(int, input().split()))
    dl.append(row)

cl = []
for _ in range(n):
    row = list(map(int, input().split()))
    cl.append(row)

ans = 10**10
for cp in cpl:
    cost = 0
    for i in range(n):
        for j in range(n):
            val3 = (i+j+2)%3
            target_c = cp[val3]
            orig_c = cl[i][j]-1
            cost += dl[orig_c][target_c]
    ans = min(ans,cost)

print(ans)

Fixed submission:
from itertools import permutations

n,c = map(int, input().split())
cln = list(range(0,c))
cpl = list(permutations(cln,3))

dl = []
for _ in range(c):
    row = list(map(int, input().split()))
    dl.append(row)

cl = []
for _ in range(n):
    row = list(map(int, input().split()))
    cl.append(row)


costs = [ [0]*c for _ in range(3) ]
for i in range(n):
    for j in range(n):
        for target_c in range(c):
            val3 = (i+j+2)%3
            orig_c = cl[i][j]-1
            cost = dl[orig_c][target_c]
            costs[val3][target_c] += cost


ans = 10**10
for cp in cpl:
    cost = costs[0][cp[0]] + costs[1][cp[1]] + costs[2][cp[2]]
    ans = min(ans,cost)

print(ans)
Buggy python submission (verdict: Runtime Error):
h,w = map(int, input().split())
sl = []
for _ in range(h):
    row = list(input())
    sl.append(row)


dp = [ [10000]*h for _ in range(w) ]
dp[0][0] = 0

for wi in range(w):
    for hi in range(h):
        if wi+1 < w:
            if sl[wi][hi] == '.' and sl[wi+1][hi] == '#':
                dp[wi+1][hi] = min( dp[wi+1][hi], dp[wi][hi]+1 )
            else:
                dp[wi+1][hi] = min( dp[wi+1][hi], dp[wi][hi] )

        if hi+1 < h:
            if sl[wi][hi] == '.' and sl[wi][hi+1] == '#':
                dp[wi][hi+1] = min( dp[wi][hi+1], dp[wi][hi]+1 )
            else:
                dp[wi][hi+1] = min( dp[wi][hi+1], dp[wi][hi] )


ans = dp[w-1][h-1]
if sl[0][0] == '#': ans += 1
print(ans)


Fixed submission:
from bisect import bisect_left, bisect_right

n = int(input())
al = list(map(int, input().split()))
al.sort()
ai = al[-1]
if ai%2 == 0:
    aj_best = ai//2
    ind = bisect_right(al, aj_best) - 1
    ind = ind if 0 <= ind < n else None
    val1 = al[ind] if ind is not None else 0

    ind = bisect_left(al, aj_best)
    ind = ind if 0 <= ind < n else None
    val2 = al[ind] if ind is not None else ai

    if abs(aj_best-val1) <= abs(aj_best-val2):
        aj = val1
    else:
        aj = val2


else:
    aj_best = ai//2
    ind = bisect_right(al, aj_best) - 1
    ind = ind if 0 <= ind < n else None
    val1 = al[ind] if ind is not None else 0

    ind = bisect_left(al, aj_best)
    ind = ind if 0 <= ind < n else None
    val2 = al[ind] if ind is not None else ai

    if abs(aj_best-val1) <= abs(aj_best+1-val2):
        aj = val1
    else:
        aj = val2

print(ai,aj)
Buggy python submission (verdict: Runtime Error):
n = int(input())
md = {'M':0, 'A':0 , 'R':0, 'C':0, 'H':0}
for _ in range(n):
    s = input()
    if s[0] in md:
        md[s[0]] += 1

vs = []
for v in md.values():
    vs.append(v)

ans = 0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            ans += vs[i]*vs[j]*vs[k]

print(ans)

Fixed submission:
n = int(input())
md = {'M':0, 'A':0 , 'R':0, 'C':0, 'H':0}
for _ in range(n):
    s = input()
    if s[0] in md:
        md[s[0]] += 1

vs = []
for v in md.values():
    vs.append(v)

ans = 0
for i in range(5):
    for j in range(i+1,5):
        for k in range(j+1,5):
            ans += vs[i]*vs[j]*vs[k]

print(ans)
Buggy python submission (verdict: Runtime Error):
h,w,d = map(int, input().split())
al = []
num_to_xy = [(-1,-1)]*(h*w+1)
for hi in range(h):
    row = list(map(int, input().split()))
    for wi,v in enumerate(row):
        num_to_xy[v] = (hi+1, wi+1)

dist_l = [ [] ]*(d+1)
for start in range(1,d+1):
    dists = [0]
    c_dist = 0
    for i in range(start, h*w-d, d):
        x1,y1 = num_to_xy[i]
        x2,y2 = num_to_xy[i+d]
        dist = abs(x2-x1) + abs(y2-y1)
        c_dist += dist
        dists.append(c_dist)
    dist_l[start] = dists


ansl = []
q = int(input())
for _ in range(q):
    l,r = map(int, input().split())
    start = l%d
    if start == 0: start = d
    posl, posr = (l-start)//d, (r-start)//d
    ans = dist_l[start][posr] - dist_l[start][posl]
    ansl.append(ans)

for a in ansl: print(a)

Fixed submission:
h,w,d = map(int, input().split())
al = []
num_to_xy = [(-1,-1)]*(h*w+1)
for hi in range(h):
    row = list(map(int, input().split()))
    for wi,v in enumerate(row):
        num_to_xy[v] = (hi+1, wi+1)

dist_l = [ [] ]*(d+1)
for start in range(1,d+1):
    dists = [0]
    c_dist = 0
    for i in range(start, h*w-d+1, d):
        x1,y1 = num_to_xy[i]
        x2,y2 = num_to_xy[i+d]
        dist = abs(x2-x1) + abs(y2-y1)
        c_dist += dist
        dists.append(c_dist)
    dist_l[start] = dists


ansl = []
q = int(input())
for _ in range(q):
    l,r = map(int, input().split())
    start = l%d
    if start == 0: start = d
    posl, posr = (l-start)//d, (r-start)//d
    ans = dist_l[start][posr] - dist_l[start][posl]
    ansl.append(ans)

for a in ansl: print(a)
Buggy python submission (verdict: Runtime Error):
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

sums = [0,0,0]
curr_sum = 0
ps = primes(10**3)
pset = set(ps)
for i in range(3,10**2+1):
    for p in ps:
        if i%p == 0 and i not in pset:
            break
        if ((i+1)//2)%p == 0 and ((i+1)//2) not in pset:
            break
    else:
        curr_sum += 1
        # print(i)
    sums.append(curr_sum)
    

q = int(input())
ansl = []
for _ in range(q):
    l,r = map(int, input().split())
    ans = sums[r] - sums[l-1]
    ansl.append(ans)

for a in ansl: print(a)

# print(sums[:54])


Fixed submission:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


q = int(input())
lrl = []
for _ in range(q):
    lrl.append(list(map(int, input().split())) )

primes = set(get_sieve_of_eratosthenes(10**5))
like2017s = []
cnt_dict = {}
cnt_dict[-1] = 0
for i in range(10**5//2):
    num = i*2+1
    num2 = (num+1)//2
    if num in primes and num2 in primes:
        cnt_dict[num] = cnt_dict[num-2]+1
    else:
        cnt_dict[num] = cnt_dict[num-2]

for lr in lrl:
    l,r = lr
    print(cnt_dict[r]-cnt_dict[l-2])
Buggy python submission (verdict: Runtime Error):
import bisect

n = int(input())
al = list(map(int,input().split())).sort()
bl = list(map(int,input().split())).sort()
cl = list(map(int,input().split())).sort()

ans = 0
for b in bl:
    a_num = bisect.bisect_left(al,b)
    c_num = n - bisect.bisect_right(cl,b)
    ans += a_num*c_num

print(ans)

Fixed submission:
import bisect
n = int(input())
al = list(map(int,input().split()))
bl = list(map(int,input().split()))
cl = list(map(int,input().split()))

al.sort()
bl.sort()
cl.sort()

cnt = 0
for b in bl:
    a_num = bisect.bisect_left(al,b)
    c_num = n - bisect.bisect_right(cl,b)
    cnt += a_num*c_num
    # cnt += c_num

print(cnt)
Buggy python submission (verdict: Runtime Error):
n,m = map(int, input().split())
abl = []
cdl = []
for _ in range(n):
    a,b = map(int, input().split())
    abl.append((a,b))

for _ in range(n):
    c,d = map(int, input().split())
    cdl.append((c,d))


for a,b in abl:
    cmin = 10**10
    mini = -1
    for i,(c,d) in enumerate(cdl):
        v = abs(a-c)+abs(b-d)
        if v < cmin:
            cmin = v
            minc,mind = c,d
            mini = i+1
    print(mini) 

Fixed submission:
n,m = map(int, input().split())
abl = []
cdl = []
for _ in range(n):
    a,b = map(int, input().split())
    abl.append((a,b))

for _ in range(m):
    c,d = map(int, input().split())
    cdl.append((c,d))


for a,b in abl:
    cmin = 10**10
    mini = -1
    for i,(c,d) in enumerate(cdl):
        v = abs(a-c)+abs(b-d)
        if v < cmin:
            cmin = v
            minc,mind = c,d
            mini = i+1
    print(mini)
Buggy python submission (verdict: Runtime Error):
# 0-indexed
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  # init leaf
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  # bottom-up
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    # [l,r)
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)


'''
def add(a,b): return a+b
st = SegTree(vl,add,0)
st = SegTree(vl,(lambda a,b: a+b),0)
st = SegTree(vl,min,10**10)

print(st.query(2,4))
st.update(4,-4)
print(st.query(2,5))
st.update(0,-10)
print(st.query(0,5))
'''
n,x = map(int, input().split())
al = list(map(int, input().split()))

st = SegTree(al, min, 10**18)
ans = 10**18
for i in range(0,n): # move cnt
    curr_i_ans = i*x
    for j in range(n): # ind
        l = j-i
        if l >= 0:
            amin = st.query(l,j+1)
        else:
            amin1 = st.query(0,j+1)
            amin2 = st.query(l+n,n+1)
            amin = min(amin1,amin2)
        curr_i_ans += amin
    ans = min(ans, curr_i_ans) 
print(ans)

Fixed submission:
n,x = map(int, input().split())
al = list(map(int, input().split()))

costs = al[:]
curr_sums = sum(costs)

# curr_mins = al[:]
curr_mins = al[:]

ans = 10**18
for i in range(0,n): # move cnt
    curr_i_ans = 0
    for j in range(n): # ind
        ind = j-i
        if ind < 0: ind+=n
        # xcost = i*x
        next_a = al[ind]
        if curr_mins[j] > next_a:
            curr_mins[j] = next_a
        cost = curr_mins[j]
        curr_i_ans += cost
    ans = min(ans, curr_i_ans+i*x)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def mod_inv(a, MOD):
    """ 前提: aとMODが互いに素であること """
    b = MOD
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        u -= t * v
        a, b = b, a
        u, v = v, u
    u %= MOD
    return u


def prime_factorize(n):
    i = 2
    res = {}
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        res[i] = 0
        while n % i == 0:
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res


def solve(n):
    pf = prime_factorize(n)
    l = len(pf)
    pfk = []
    for i, p in enumerate(pf):
        pfk.append(p ** pf[p])

    ans = 10 ** 18

    for bit in range(1 << l):
        a = 1
        for d in range(l):
            if bit & (1 << d):
                a *= pfk[d]
        b = n // a

        if a == 1:
            k = n - 1
        elif b == 1:
            k = n
        else:
            m = mod_inv(b, a)
            k = b * m - 1
        # print(a, b, m, k)

        if k > 0 and k * (k + 1) // 2 % n == 0:
            ans = min(ans, k)
        else:
            ans = min(ans, k + n)

    return ans


n = int(input())
ans = solve(n)
print(ans)

# import random
#
# for n in range(1, 10000):
#     a = solve(n)
#     i = -1
#     for i in range(1, 2 * n + 1):
#         if i * (i + 1) // 2 % n == 0:
#             break
#     # print(n, a, i)
#     assert a == i


Fixed submission:
def mod_inv(a, MOD):
    """ 前提: aとMODが互いに素であること """
    b = MOD
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        u -= t * v
        a, b = b, a
        u, v = v, u
    u %= MOD
    return u


def prime_factorize(n):
    i = 2
    res = {}
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        res[i] = 0
        while n % i == 0:
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res


def solve(n):
    pf = prime_factorize(n)
    l = len(pf)
    pfk = []
    for i, p in enumerate(pf):
        pfk.append(p ** pf[p])

    ans = 10 ** 18

    for bit in range(1 << l):
        a = 1
        for d in range(l):
            if bit & (1 << d):
                a *= pfk[d]
        b = n // a

        if a == 1:
            k = n - 1
        elif b == 1:
            k = n
        else:
            m = mod_inv(b, a)
            k = b * m - 1
        # print(a, b, m, k)

        if k > 0 and k * (k + 1) // 2 % n == 0:
            ans = min(ans, k)
        else:
            ans = min(ans, k + n)

    return ans


n = int(input())
ans = solve(n)
print(ans)

# import random
#
# for n in range(1, 10000):
#     a = solve(n)
#     i = -1
#     for i in range(1, 2 * n + 1):
#         if i * (i + 1) // 2 % n == 0:
#             break
#     # print(n, a, i)
#     assert a == i
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import time

n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)
bbb = np.fromiter(map(int, input().split()), np.int64)
st = time.time()

while time.time() - st < 1.9:
    np.random.shuffle(bbb)
    if (aaa != bbb).all():
        print('Yes')
        print(*bbb)
        exit()

print('No')


Fixed submission:
from itertools import groupby

n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))

idx_a = {}
cnt_a = {}
i = 0
for a, itr in groupby(aaa):
    cnt = len(list(itr))
    i += cnt
    idx_a[a] = i
    cnt_a[a] = cnt

idx_b = {}
cnt_b = {}
i = 0
for b, itr in groupby(bbb):
    cnt = len(list(itr))
    idx_b[b] = i
    cnt_b[b] = cnt
    i += cnt

slide = 0
for a in idx_a:
    if a not in idx_b:
        continue
    if cnt_a[a] + cnt_b[a] > n:
        print('No')
        exit()
    slide = max(slide, idx_a[a] - idx_b[a])

print('Yes')
if slide > 0:
    bbb = bbb[-slide:] + bbb[:-slide]
print(*bbb)