Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
color = [-1]*n
dist = [-1]*n
dist[0] = 0
visited = [0]*n
for _ in range(n-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1 
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]
  
def dfs(u, d):
  visited[u] = 1
  if sum(visited) == n:
    return 
  for v, w in graph[u]:
    if dist[v] == -1:
      dist[v] = (w + d) % 2
      dfs(v, d+w)
      
dfs(0, 0)
for i in dist:
  print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
    adlist[v-1] += [[u-1, w%2]]
  return adlist 

def dfs(v, c):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] != 0:
      continue
    if color[next_v] == 0 and w % 2 != 0:
      dfs(next_v, -c)
    elif color[next_v] == 0 and w % 2 == 0:
      dfs(next_v, c)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  dfs(0, 1)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


if __name__ == "__main__":
  main()
### BUGGY CODE ###

INPUT = list(map(int, input().split()))

import time
B=INPUT[1]
Number=(INPUT[0]*INPUT[1]+1)
time.sleep(2)

print(Number)

### FIXED CODE ###

INPUT = list(map(int, input().split()))
print(INPUT[0]*INPUT[1])
### BUGGY CODE ###

n=int(input())
ans=[]
for i in range(1,n+1):
  a=0
  for x in range(1,100):
    for y in range(1,x+1):
      for z in range(1,y+1):
        if x**2+y**2+z**2+x*y+y*z+z*x==i:
          if x==y and y==z:
            a+=1
          elif x==y or y==z:
            a+=3
          else:
            a+=6
  ans.append(a)
for i in ans:
  print(i)

### FIXED CODE ###

n=int(input())
ans=[0 for i in range(n)]
for x in range(1,100):
  for y in range(1,x+1):
    for z in range(1,y+1):
      i=x**2+y**2+z**2+x*y+y*z+z*x
      if i<=n:
        if x==y and y==z:
          ans[i-1]+=1
        elif x==y or y==z:
          ans[i-1]+=3
        else:
          ans[i-1]+=6
for i in ans:
  print(i)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(200000000)


# my functions here!

#入力

def pin(type=int):
    return map(type,input().rstrip().split())
from collections import Counter    
def resolve():
    N,=pin()
    A=list(pin())
    S=[sum(A[:i])for i in range(N+1)]
    
    s=list(Counter(S).values())
    ans=0
    for j in s:
            ans+=(j*(j-1))//2
    print(ans)
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """6
1 3 -4 2 2 -2"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """7
1 -1 1 -1 1 -1 1"""
        output = """12"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5
1 -2 3 -4 5"""
        output = """0"""
        self.assertIO(input, output)
if __name__=="__main__":resolve()

### FIXED CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(200000000)


# my functions here!

#入力

def pin(type=int):
    return map(type,input().rstrip().split())
from collections import Counter
from itertools import accumulate as acm
def resolve():
    N,=pin()
    S=list(acm(pin()))
    S.insert(0,0)
    s=list(Counter(S).values())
    ans=0
    for j in s:
            ans+=(j*(j-1))//2
    print(ans)
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
if __name__=="__main__":resolve()
### BUGGY CODE ###

m = 998244353
n,k = map(int,input().split())
l,r = [],[]
for _ in range(k):
    l_, r_ = map(int,input().split())
    l.append(l_)
    r.append(r_)
    
dp = [0]*(n+1)
dp[1] = 1
dpsum = [0]*(n+1)
dpsum[1] = 1

for i in range(2,n+1):
    for j in range(k): 
        li = i - r[j] 
        ri = i - l[j] 
        if ri < 0:
            continue
        li = max(li,1)
        dp[i] += dpsum[ri] - dpsum[li-1]
    dpsum[i] = dpsum[i-1]+dp[i]
    
print(dp[n]%m)

### FIXED CODE ###

m = 998244353
def main():
    n,k = map(int,input().split())
    l,r = [],[]
    for _ in range(k):
        l_, r_ = map(int,input().split())
        l.append(l_)
        r.append(r_)

    dp = [0]*(n+1)
    dp[1] = 1
    dpsum = [0]*(n+1)
    dpsum[1] = 1

    for i in range(2,n+1):
        for j in range(k):
            li = i - r[j]
            ri = i - l[j]
            if ri < 0:
                continue
            li = max(li,1)
            dp[i] += dpsum[ri] - dpsum[li-1]
        dpsum[i] = (dpsum[i-1]+dp[i])%m

    print(dp[n]%m)
main()
### BUGGY CODE ###

import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

N,M=map(int,input().split())
edge=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

odd=0
f=0
s=0
v=[]
for i in range(N):
    if len(edge[i])%2==1:
        odd+=1
    elif len(edge[i])==4:
        f+=1
        v.append(i)
    elif len(edge[i])>=6:
        s+=1

if odd>0:
    print("No")
else:
    if s>0:
        print("Yes")
    elif f>2:
        print("Yes")
    elif f!=2:
        print("No")
    else:
        start=v[0]
        ban=v[1]
        check=False
        def dfs(V,pv):
            global check
            if V==start and pv==-1:
                for i in edge[start]:
                    if i!=ban:
                        dfs(i,start)
            elif V==start:
                check=True
            else:
                for i in edge[V]:
                    if i!=ban and i!=pv:
                        dfs(i,V)
        dfs(start,-1)
        if check:
            print("Yes")
        else:
            print("No")


### FIXED CODE ###

import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

N,M=map(int,input().split())
edge=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

odd=0
f=0
s=0
v=[]
for i in range(N):
    if len(edge[i])%2==1:
        odd+=1
    elif len(edge[i])==4:
        f+=1
        v.append(i)
    elif len(edge[i])>=6:
        s+=1

if odd>0:
    print("No")
else:
    if s>0:
        print("Yes")
    elif f>2:
        print("Yes")
    elif f!=2:
        print("No")
    else:
        start=v[0]
        ban=v[1]
        check=False
        def dfs(V,pv):
            global check
            if V==start and pv==-1:
                for i in edge[start]:
                    if i!=ban:
                        dfs(i,start)
            elif V==start:
                check=True
            else:
                for i in edge[V]:
                    if i!=ban and i!=pv:
                        dfs(i,V)
        dfs(start,-1)
        if check:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

A, B, K = map(int, input().split())
def func():
  pass
for i in range(K):
  if A >= 1:
    A -= 1
  elif A < 1 and B >= 1:
    B -= 1
  else:
    func()
print(A, B)

### FIXED CODE ###

a, b, k = map(int, input().split())
d = max(0, k-a)
ans_a = max(0, a-k)
ans_b = max(0, b-d)
print(ans_a, ans_b)
### BUGGY CODE ###

N = int(input())
S = list(input())

minNum = N
for i in range(N):
    cost = 0
    for j in range(N):
        if cost > minNum:
            break
        if i == j:
            continue
        if j < i:
            if S[j] == 'W':
                cost += 1
        else :
            if S[j] == 'E':
                cost += 1
    if minNum > cost:
        minNum = cost

print(cost-1)

### FIXED CODE ###

N = int(input())
S = list(input())

reS = S[::-1]

wSum = [0 for i in range(N)]
eSum = [0 for i in range(N)]

for i in range(N):
    if i == 0:
        if S[i] == 'W':
            wSum[i] = 1
        if reS[i] == 'E':
            eSum[i] = 1
    else:
        if S[i] == 'W':
            wSum[i] = wSum[i-1] + 1
        else:
            wSum[i] = wSum[i-1]
        if reS[i] == 'E':
            eSum[i] = eSum[i-1] + 1
        else:
            eSum[i] = eSum[i-1]

eSum = eSum[::-1]

cost = eSum[1]

for i in range(1,N):
    if i == N - 1:
        if cost > wSum[N-2]:
            cost = wSum[N-2]
    else:
        if cost > wSum[i-1] + eSum[i+1]:
            cost = wSum[i-1] + eSum[i+1]
print(cost)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque
import math
import pprint
from functools import reduce
# stdin = open("sample.txt")

def keta(kazu):
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(stdin.readline().rstrip())
ans = 0

for c in range(2,K+1):
    for b in range(2,K+1):
        for a in range(2,K+1):
            ans += gcd(a,b,c)
            
print(ans+(K**3-(K-1)**3))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque
import math
import pprint
from functools import reduce
# stdin = open("sample.txt")

def keta(kazu):
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(stdin.readline().rstrip())
ans = 0
for_c = []

for b in range(1,K+1):
    for a in range(1,K+1):
        if math.gcd(a,b) == 1:
            ans += K
        else:
            for_c.append(math.gcd(a,b))

for c in range(1,K+1):
    for ab in range(len(for_c)):
        ans += math.gcd(for_c[ab],c)

print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
P = input().split()
P = [int(p) for p in P]

E = [p*(p+1)/2/p for p in P]

ans = 0.0
for i in range(K,N+1):
  if sum(E[i-K:i])> ans:
    ans = sum(E[i-K:i])
print(float(ans))

### FIXED CODE ###

N, K = map(int, input().split())
P = input().split()
P = [int(p) for p in P]

import numpy as np

E = (np.array(P)+1)/2
E = np.cumsum(E)  

ans = E[K-1]
for i in range(0,N-K):
  ans = max(ans, E[i+K]-E[i])
print(float(ans))
### BUGGY CODE ###

import copy
import itertools

maxnum=0

def parm_check(n,maxnum):
    if(n >= 2):
        #print(tmp)
        #print(list(itertools.combinations(a,n)))
        comb = list(itertools.combinations(a,n))
        for j in range(len(comb)):
            if(sum(comb[j]) % 10 != 0 and maxnum < sum(comb[j])):
                maxnum = sum(comb[j])
    else:
        tmp= copy.deepcopy(a)
        for j in range(N):
            #print(tmp[j])
            if(tmp[j] % 10 != 0 and maxnum < tmp[j]):
                maxnum=tmp[j]
    
    return maxnum

if(__name__=="__main__"):
    N = int(input())
    a =[int(input()) for i in range(N)]
    #print(sum(a))
    
    if(sum(a) % 10 != 0):
        print(sum(a))
    else:
        for i in range(1,N):
            maxnum = parm_check(i,maxnum)

        print(maxnum)


### FIXED CODE ###

maxnum=0

if(__name__=="__main__"):
    N = int(input())
    a =[int(input()) for i in range(N)]
    #print(sum(a))
    
    if(sum(a) % 10 != 0):
        print(sum(a))
    else:
        a_sort = sorted(a)
        for i in range(0,N):
            if(a_sort[i] % 10 != 0):
                del a_sort[i]
                maxnum = sum(a_sort)
                break
            

        print(maxnum)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

AB.sort(key=lambda x:x[1])
bridge=[True]*(n-1)
for a,b in AB:
  if False not in bridge[a-1:b-1]:
    bridge[b-2]=False
print(bridge.count(False))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

AB.sort(key=lambda x:(x[1],x[0]))
end=AB[0][1]
ans=1
for a,b in AB[1:]:
  if end<=a:
    end=b
    ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(float, input().split()))

dp = [[0]*(i+2) for i in range(n)]
dp[0][0] = 1-p[0]
dp[0][1] = p[0]

for i in range(1, n):
    for j in range(i+2):
        if j < i+1:
            dp[i][j] += dp[i-1][j]*(1-p[i])
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * p[i]

print(sum(dp[n-1][(n//2)+1:]))

### FIXED CODE ###

n = int(raw_input())
p = list(map(float, raw_input().split()))

dp = [[0]*(i+2) for i in range(n)]
dp[0][0] = 1-p[0]
dp[0][1] = p[0]

for i in range(1, n):
    for j in range(i+2):
        if j < i+1:
            dp[i][j] += dp[i-1][j]*(1-p[i])
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * p[i]

print(sum(dp[n-1][(n//2)+1:]))
### BUGGY CODE ###

from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# from operator import xor
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    S=[int(input()) for i in range(N)]
    ls=[]
    for i in range(1, N + 1):
        for j in combinations(S,i):
            ls.append(j)
    ans=0
    for i in ls:
        if sum(i)%10!=0:
            ans=max(ans,sum(i))
    print(ans)


resolve()

### FIXED CODE ###

def resolve():
    N=int(input())
    S=sorted([int(input()) for i in range(N)])
    total=sum(S)
    if total%10!=0:
        print(total)
    else:
        for i in range(N):
            if S[i]%10!=0:
                print(total-S[i])
                break
            elif i==N-1:print(0)


resolve()
### BUGGY CODE ###

n=input()
a=map(int,raw_input().split())
r=0
for i in range(1<<n):
 b=[a[j]*((i>>j&1)*2-1)%24 for j in range(n)]+[0]
 s=24
 for j in range(n):
  for k in range(j+1,n+1):s=min(s,(b[j]-b[k])%24,(b[k]-b[j])%24)
 r=max(r,s)
print r

### FIXED CODE ###

n=input()
a=sorted(map(int,raw_input().split()))
r=0
b=[0]+[a[j]*(-1)**j%24 for j in range(n)]
s=24
for j in range(n):
 for k in range(j+1,n+1):s=min(s,(b[j]-b[k])%24,(b[k]-b[j])%24)
r=max(r,s)
print r
### BUGGY CODE ###

s = list(input())
t = list(input())

def restr(string):
    result = []
    for i in range(len(string)):
        tmp = [i]
        for j in range(i+1, len(string)):
            if string[i] == string[j]:
                tmp.append(j)
        if len(tmp) > 1:
            result.append(tmp)
    return result

print('Yes' if restr(s) == restr(t) else 'No')


### FIXED CODE ###

from collections import defaultdict

def a(s):
    dic = defaultdict(list)
    for i, ch in enumerate(s):
        dic[ch].append(i)
    return sorted(list(dic.values()))

s = input()
t = input()
print('Yes' if a(s) == a(t) else 'No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n,m=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    a.reverse()
    l,r=2*a[-1],2*a[0]
    x=(l+r)//2
    while l+1<r:
        cnt=0
        for A in a:
            for B in a:
                if A+B>=x:
                    cnt+=1
                else:
                    break
        if cnt>=m:
            l=x
        else:
            r=x
        x=(l+r)//2
    s,cnt=0,0
    for A in a:
        for B in a:
            if A+B>=l:
                cnt+=1
                s+=A+B
            else:
                break
    print(s+(m-cnt)*l)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect, bisect_left
from itertools import accumulate

def main():
    def check(x):
        count = 0
        for a in aaa:
            if x <= a:
                count += n
            else:
                count += n - bisect_left(aaa, x - a)
        return count >= m
    
    
    n, m = map(int, input().split())
    aaa = list(map(int, input().split()))
    aaa.sort()
    acc = [0] + list(accumulate(aaa))
    sum_a = acc[-1]
    
    l, r = 0, 200001
    while l + 1 < r:
        mid = (l + r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    
    # 合計がlより大きい組み合わせの和と組数を求める→Mに足りない分だけ合計がlの組を採用
    ans = 0
    count = 0
    for a in aaa:
        if l <= a:
            ans += sum_a + a * n
            count += n
        else:
            omit = bisect(aaa, l - a)
            if omit < n:
                ans += sum_a - acc[omit] + a * (n - omit)
                count += n - omit
    ans += l * (m - count)
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input())

    rows = []
    for i in range(H):
        count = 0
        temp = []
        for j in range(W):
            if grid[i][j] == "#":
                temp += [count]*count
                temp += [0]
                count = 0
            else:
                count += 1
        temp += [count]*count
        rows.append(temp)
    cols = []
    for j in range(W):
        count = 0
        temp = []
        for i in range(H):
            if grid[i][j] == "#":
                temp += [count]*count
                temp += [0]
                count = 0
            else:
                count += 1
        temp += [count]*count
        cols.append(temp)

    max_v = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == ".":
                v = rows[i][j] + cols[j][i] - 1 # -1 for overlap
                max_v = max(max_v, v )
    return max_v


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import collections
def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input())

    rows = []
    rows_val = dict()
    id = 0
    for i in range(H):
        count = 0
        temp = []
        id += 1
        for j in range(W):
            if grid[i][j] == "#":
                if count > 0:
                    rows_val[id] = count
                count = 0
                id += 1
                temp.append(None)
            else:
                temp.append(id)
                count += 1
        if count > 0:
            rows_val[id] = count
        rows.append(temp)
    # print(rows)

    cols = []
    cols_val = dict()
    id = 0
    for j in range(W):
        count = 0
        temp = []
        id += 1
        for i in range(H):
            if grid[i][j] == "#":
                if count > 0:
                    cols_val[id] = count
                count = 0
                id += 1
                temp.append(None)
            else:
                count += 1
                temp.append(id)
        if count > 0:
            cols_val[id] = count
        cols.append(temp)

    max_v = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == ".":
                v = rows_val[rows[i][j]]
                v += cols_val[cols[j][i]] - 1 # -1 for overlap
                max_v = max(max_v, v)
    return max_v


if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
 
 
def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue
        
        g, im = inv_gcd(m0, m1)
 
        u1 = m1 // g
        if (r1 - r0) % g:
            return (0, 0)
        
        x = (r1 - r0) // g % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)
 
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
 
 
def main():
    n = int(input())
    divisors = make_divisors(2 * n)
 
    ans = n-1 if n%2 else 2*n-1
    for x in divisors:
        y = n * 2 // x
        if y == 1:
            continue
        r = [0, y-1]
        m = [x, y]
        rem, mod = crt(r, m)
        if rem == mod == 0:
            continue
        ans = min(ans, rem)
 
    
    print(ans if n-1 else 1)
 
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue
        
        g, im = inv_gcd(m0, m1)
 
        u1 = m1 // g
        if (r1 - r0) % g:
            return (0, 0)
        
        x = (r1 - r0) // g % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)


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


# print(divisors(z))

z=int(input())


ans = z-1 if z%2 else 2*z-1
for i in divisors(2*z):
  y=2*z//i
  if y == 1:
    continue
  a=[0,-1]
  b=[i,y]
  rem, mod = crt(a, b)
  #print(rem)
  #print(mod)
  if rem == mod == 0:
      continue
  ans = min(ans, rem)

print(ans if z-1 else 1)