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

n, m, p = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((a, b, p-c))

INF = 10**10
dist = [INF]*n
dist[0] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(10**5):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c
        negative[v2] = 1

if negative[-1]:
    print(-1)
else:
    print(max(0, -dist[-1]))


### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m, p = map(int, input().split())
edges = []
forward_edges = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((a, b, p-c))
    forward_edges[a].append(b)


can_reach = [0]*n
stack = [0]
while stack:
    v = stack.pop()
    if can_reach[v]:
        continue
    can_reach[v] = 1
    for v2 in forward_edges[v]:
        if can_reach[v2]:
            continue
        stack.append(v2)


INF = 10**10
dist = [INF]*n
dist[0] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        if not can_reach[v2]:
            continue
        dist[v2] = -INF
        negative[v2] = 1

if negative[-1]:
    print(-1)
else:
    print(max(0, -dist[-1]))
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(N):
    ans += i
print(ans)

### FIXED CODE ###

N = int(input())
ans = (N-1)*N//2
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  if Fraction(A,B)>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[-1/Fraction(A,B)][1]+=1
ans=1
for k in dic:
 ans*=(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

### FIXED CODE ###

from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    H, W = MAP()
    S = []
    walls = 0
    for _ in range(H):
        line = INPUT()
        walls += line.count('#')
        S.append(line)

    dist = [[INF]*W for _ in range(H)]
    dist[0][0] = 1
    queue = deque([[0, 0]])
    while queue:
        y, x = queue.popleft()
        if y == H - 1 and x == W - 1:
            print(H*W - walls - dist[y][x])
            sys.exit()

        for dy, dx in [(y, x-1), (y-1, x), (y, x+1), (y+1, x)]:
            if 0 <= dy < H and 0 <= dx < W and S[dy][dx] == '.' and dist[dy][dx] > dist[y][x]:
                dist[dy][dx] = dist[y][x] + 1
                queue.append([dy, dx])

    print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    H, W = MAP()
    dungeon = []
    walls = 0

    for _ in range(H):
        line = [0 if i == "." else 1 for i in INPUT()]
        walls += line.count(1)
        dungeon.extend([line])

    queue = deque([(0, 0, 1)])
    while queue:
        y, x, cnt = queue.popleft()
        if y == H-1 and x == W-1:
            print(H*W - walls - cnt)
            exit()
        for row, col in [(y, x-1), (y-1, x), (y, x+1), (y+1, x)]:
            if 0 <= row < H and 0 <= col < W and not dungeon[row][col]:
                dungeon[row][col] = 2
                queue.append((row, col, cnt+1))

    print(-1)


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

n = int(input())
s = list(input())
ansl = []
for i in range(1,n-1):
    l = []
    count = 0
    for j in range(n-i):
        #print(s[j],s[j+i])
        if s[j] == s[j+i]:
            count += 1
        else:
            if count > 0:
                if count > i:
                    l.append(i)
                else:
                    l.append(count)
                count = 0
    l.append(min(count,i))
    ansl.append(max(l))
if len(ansl) > 0:
    print(max(ansl))
else:
    print(0)

### FIXED CODE ###

n = int(input())
s = list(input())
ansl = []
for i in range(1,n):
    ans = 0
    count = 0
    for j in range(n-i):
        #print(s[j],s[j+i])
        if s[j] == s[j+i]:
            count += 1
        else:
            if count > 0:
                if count > ans:
                    ans = min(count,i)
                count = 0
    if count > ans:
        ans = min(count,i)
    ansl.append(ans)
print(max(ansl))
### BUGGY CODE ###

import collections
import math

#****************************************************************
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#****************************************************************

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

c = collections.Counter(A)
dict_ans = {}

for i in c.keys():
    target = c.copy()
    target[i] -= 1
    ans = 0
    for k in [j for j in target.values() if j >= 2]:
        ans += comb(k, 2)
    dict_ans[i] = ans

for i in A:
    print(dict_ans[i])

### FIXED CODE ###

import collections
import math

#****************************************************************
def comb(n):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))
#****************************************************************

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

c = collections.Counter(A)
full_ans = sum(list(map(comb, c.values())))

for a in A:
    print(full_ans - c[a] + 1)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))

    seen = [False] * (N+1)
    arr = [1]
    seen[1] = True
    while True:
        next = A[arr[-1]]
        if seen[next]:
            arr.append(next)
            break
        arr.append(next)
        seen[next] = True

    x = int(math.log2(K)) + 1
    dub = [[0] * (N+1) for _ in range(x)]
    for idx, a in enumerate(arr[:-1]):
        dub[0][a] = arr[idx+1]
    for d in range(1,x):
        for k in arr[:-1]:
            tmp = dub[d - 1][k]
            #if tmp == 0:continue
            dub[d][k] = dub[d-1][tmp]

    ret = 1
    while K:
        d = int(math.log2(K))
        K -= 1 << d
        ret = dub[d][ret]
    print(ret)

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))
    perm = [1]
    seen = [[-1, False] for _ in range(N+1)]
    seen[1] = [1,True]
    l = 1
    while True:
        v = perm[-1]
        idx, boo = seen[A[v]]
        if boo: break
        l += 1
        perm.append(A[v])
        seen[A[v]] = [l,True]

    if K <= idx -1:
        print(perm[K])
        return None
    K -= idx - 1
    perm = perm[idx-1:]
    print(perm[K % len(perm)])

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

def check(a,b):
    if b == 0 :
        return a
    return check(b,a%b)
def check2(x,y):
    for i in range(2,min(x,y)+1):
        if x % i == 0 and y % i == 0 :
            return i
A,B = map(int,input().split())
ans = 1
while True :
    if check(A,B)== 1 :
        break
    p = check2(A,B)
    while True :
        if A % p == 0 and B % p == 0 :
            A = (A//p)
            B = (B//p)
        else :
            break
    ans += 1
print(ans)

### FIXED CODE ###

def gcd(x, y):
    if y == 0 :
        return x
    else:
        return gcd(y,x%y)
def prime(x):
    global  ans
    m = x ** (0.5)
    for i in range(2,int(m+1)):
        if x % i == 0 :
            while True:
                if x % i != 0 :
                    break
                else:
                    x = (x//i)
            ans +=1
    if x != 1 :
        ans += 1
    return ans
A,B = map(int,input().split())
t = gcd(A,B)
ans = 1
print(prime(t))
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]

cnt = []
for i in S:
    cnt.append(S.count(i))
M = max(cnt)

ans = [s for s in S if S.count(s) == M]

print(*sorted(set(ans)), sep = "\n")

### FIXED CODE ###

from collections import Counter

N = int(input())
S = [input() for _ in range(N)]

counter = Counter(S)
max_cnt = max(counter.values())
ans = [name for name, cnt in counter.items() if cnt == max_cnt]
ans.sort()
 
print(*ans, sep='\n')
### BUGGY CODE ###

MOD=10**9+7
K=int(input())
S=list(input())
len_S=len(S)

def invmod(a):
  return pow(a,MOD-2,MOD)
fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,K+len_S+1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
def comb_mod_table(n,r):
  if 0<=r<=n:
    return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]
  else:
    return 0
  
answer=pow(26,K+len_S,MOD)
for i in range(len_S):
  answer-=comb_mod_table(K+len_S,i)*pow(25,K+len_S-i,MOD)
  answer%=MOD
  
print(answer)

### FIXED CODE ###

MOD=10**9+7
K=int(input())
S=list(input())
len_S=len(S)

def invmod(a):
  return pow(a,MOD-2,MOD)
fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,K+len_S+1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
def comb_mod_table(n,r):
  if 0<=r<=n:
    return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]
  else:
    return 0
  
answer=pow(26,K+len_S,MOD)
pow25=pow(25,K+len_S,MOD)
inv25=invmod(25)
for i in range(len_S):
  answer-=comb_mod_table(K+len_S,i)*pow25
  pow25=pow25*inv25%MOD
  answer%=MOD
  
print(answer)
### BUGGY CODE ###

A,B =[int(x) for x in input().split()]

def bunkai(n):
    sosu= {1}
    tmp = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.add(2)
    
    for i in range(3,int(n/2)+1,2):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)

    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[]:
        sosu.add[n]
    
    return sosu

ans = len(bunkai(A)&bunkai(B))
print(ans)

### FIXED CODE ###


A,B =[int(x) for x in input().split()]

def bunkai(n):
    sosu= {1}
    tmp = n
    stop_flag = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.add(2)
    
    for i in range(3,n+1,2):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)
            stop_flag = tmp 
            
        if i > stop_flag:
            break
        else:
            stop_flag = int(n/i)+1
            
    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[1]:
        sosu.add(n)
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

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

from collections import deque


def BFS(s):
    color=["white" for _ in range(n+1)]
    D=[0 for _ in range(n+1)]

    D[s]=0
    color[s]="gray"
    queue=deque([s])

    while len(queue)>0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                D[i]=D[u]+1
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return D


n,x,y=map(int,input().split())
M=[[] for _ in range(n+1)]
for i in range(1,n):
    M[i].append(i+1)
    M[i+1].append(i)
M[x].append(y)
M[y].append(x)

A=[0]*(n)
for i in range(1,n+1):
    for j in BFS(i)[i:]:
        A[j] +=1

for i in A[1:]:
    print(i)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)


def BFS(s):
    color=["white" for _ in range(n)]
    D=[float("inf") for _ in range(n)]

    color[s-1]="gray"
    D[s-1]=0
    queue=deque([s-1])

    while len(queue)!=0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


n,x,y=map(int,input().split())

M=[[] for _ in range(n)]
for i in range(n-1):
    M[i].append(i+1)
    M[i+1].append(i)
M[x-1].append(y-1)
M[y-1].append(x-1)

C=[0]*n
for i in range(n):
    for j in BFS(i+1)[i:]:
        C[j] +=1

for i in C[1:]:
    print(i)
### BUGGY CODE ###

def Triangles(N, Lrand):
    asc = sorted(Lrand)
    desc = sorted(Lrand, reverse=True)
    cnt = 0
    for i in range(N-2):
        if desc[i] >= desc[i+1]*2: break
        for j in range(i+1, N-1):
            if desc[i] >= desc[j] + desc[i+1]: break
            for k in range(N-j-1):
                if desc[i] - desc[j] < asc[k]:
                    cnt += N-j-k-1
                    break
    return cnt

N = int(input())
L = [int(x) for x in input().split()]
print(Triangles(N, L))

### FIXED CODE ###

from bisect import bisect_left

def Triangles(N, L):
    asc = sorted(L)
    cnt = 0
    for i in range(N-2):
        l1 = asc[i]
        for j in range(i+1, N-1):
            l2 = asc[j]
            pos = bisect_left(asc, l1+l2)
            cnt += pos - 1 - j
    return cnt

N = int(input())
L = list(map(int, input().split()))
print(Triangles(N, L))
### BUGGY CODE ###

S = list(input())
MOD = 10 ** 9 + 7

dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
            dp[i + 1][(k * 10 + j) % 13] %= MOD

print(dp[len(S)][5])


### FIXED CODE ###

S = list(input())
MOD = 10 ** 9 + 7

length = len(S)
dp = [[0] * 13 for _ in range(length + 1)]
dp[0][0] = 1

for i in range(length):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            index = (k * 10 + j) % 13
            dp[i + 1][index] = (dp[i + 1][index] + dp[i][k]) % MOD

print(dp[length][5])
### BUGGY CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))

for i in range(n):
    if i>=k:
        c1 = 1
        c2 = 1
        for j in range(i-k+1,i+1):
            c1 *= a[j]
            c2 *= a[j-1]
        if c1>c2:
            print("Yes")
        else:
            print("No")

### FIXED CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    if i>=k:
        if a[i]>a[i-k]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

import math
n,a,b = [int(x) for x in input().rstrip().split()]
l=[]
n1=1
st=1
ans=0
for i in range(1,n+1):
    n1=n1*(n-i+1)
    st=st*i
    ans1 = (n1//st)
    if i==a or i==b:
        l.append(n1//st)
        continue
    else:
        if n<(i/2):
            ans+=l[n-i]
        else:
            ans+=ans1
            l.append(ans1)

print(ans%(10**9+7))

### FIXED CODE ###

mod=10**9+7
n,a,b=[int(x) for x in input().rstrip().split()]

def modpow(a,n):
  if n<1:
    return 1
  ans=modpow(a,n//2)
  ans=(ans*ans)%mod
  if n%2==1:
    ans*=a
  return ans%mod

def conb(n,i):
  inv,ans=1,1
  for j in range(1,i+1):
    ans=ans*(n-j+1)%mod
    inv=inv*j%mod
  return (ans*modpow(inv,mod-2))%mod

ans_n=pow(2,n,mod)-1
ans_a=conb(n,a)
ans_b=conb(n,b)

print((ans_n-ans_a-ans_b)%mod)
### BUGGY CODE ###

def main():
    n = int(stdinput())

    d = MyDict()

    for _ in range(n):
        cmd, value = stdinput().split()
        if cmd == 'insert':
            d.insert(value)
        elif cmd == 'find':
            if d.find(value):
                print('yes')
            else:
                print('no')


class MyDict():
    def __init__(self):
        self.stacks = {
            1: [], 2: [], 3: [], 4: [], 5: [],
            6: [], 7: [], 8: [], 9: [], 10: [],
            11: [], 12: []
        }
    
    def insert(self, value):
        st = self.stacks[len(value)].append(value)
    
    def find(self, value):
        st = self.stacks[len(value)]
        return value in st

def binary_search(S, n, t):
    left = 0
    right = n - 1
    while left <= right:
        mid = (left + right) // 2
        if S[mid] == t:
            return True
        elif S[mid] > t:
            right = mid - 1
        else:
            left = mid + 1
    
    return False

def stdinput():
    from sys import stdin
    return stdin.readline().strip()

if __name__ == '__main__':
    main()
    


### FIXED CODE ###

def main():
    n = int(stdinput())

    st = [None] * (4**12)

    for _ in range(n):
        cmd, value = stdinput().split()
        if cmd == 'insert':
            st[get_hash(value)] = 1
        elif cmd == 'find':
            if st[get_hash(value)] == 1:
                print('yes')
            else:
                print('no')

CODES = {'A' : 1, 'C' : 2, 'G' : 3, 'T' : 4}
def get_hash(s):
    base = 1
    h = 0
    for c in s:
        code = CODES[c]
        h += code * base
        base *= 4
    return h

def stdinput():
    from sys import stdin
    return stdin.readline().strip()

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')
### BUGGY CODE ###

n = list(map(int,input().split()))
a = n[0]
b = n[1]
while 1>0:
  c=a
  if a>b:
    a=a-b
  else:
    a=b-a
  if c<a:
    break
print(c)

### FIXED CODE ###

n = list(map(int,input().split()))
a = n[0]
b = n[1]
c = a%b
d = b - c
if d<c:
    print(d)
else:
    print(c)
### BUGGY CODE ###

class UnionFind:

    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        # 集合の代表を求める
        children = []
        while self.table[x] >= 0:
            children.append(x)
            x = self.table[x]
        for c in children:
            self.table[c] = x
        return x

    def union(self, x, y):
        # 併合
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
        return self.table[s1]

n,k,l= map(int, input().split())
road = UnionFind(n+1)
train = UnionFind(n+1)

for i in range(k):
    p,q = map(int, input().split())
    road.union(p, q)
for i in range(l):
    p,q = map(int, input().split())
    train.union(p,q)
con = [1 for i in range(n)]
for i in range(1,n):
    for j in range(i+1, n+1):
        if road.find(i) == road.find(j) and train.find(i) == train.find(j):
            con[i-1] += 1
            con[j-1] += 1
print(*con, sep=' ')


### FIXED CODE ###

class UnionFind:
 
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        # 集合の代表を求める
        children = []
        while self.table[x] >= 0:
            children.append(x)
            x = self.table[x]
        for c in children:
            self.table[c] = x
        return x
 
    def union(self, x, y):
        # 併合
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
        return self.table[s1]
 
n,k,l= map(int, input().split())
road = UnionFind(n+1)
train = UnionFind(n+1)
for i in range(k):
    p,q = map(int, input().split())
    road.union(p, q)
for i in range(l):
    p,q = map(int, input().split())
    train.union(p,q)
import collections
d = collections.defaultdict(int)
for i in range(1,n+1):
    r = road.find(i)
    t = train.find(i)
    d[(r,t)] += 1
res = [d[(road.find(i), train.find(i))] for i in range(1,n+1)]

print(*res, sep=' ')
### BUGGY CODE ###

A, B, N = map(int, input().split())
ans_dict = {}
for x in range(N + 1):
    ans_dict.setdefault((((A * x) // B) - (A * (x // B))), x)


print(max(ans_dict))

### FIXED CODE ###

A, B, N = map(int, input().split())

if N >= B:
    x = B - 1
    ans = ((A * x) // B) - (A * (x // B))
else:
    x = N
    ans = ((A * x) // B) - (A * (x // B))


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

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*200010
    now = 0
    l[0] = 0
    ans = -100

    for i in range(n):
        a[i] -= 1

    for i in range(n*4):
        k -= 1
        now = a[now] #転送された場所
        l[now] += 1
        if l[now] == 2: #3ループ目の頭
            loop = l.count(1) + 1
            k %= loop
        if k == 0:
            ans = now + 1
            break
        
    print(max(ans, -1))

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*n
    now = 0
    order = 0
    l[0] = 0
    s = {}
    ans = -100

    for i in range(n):
        a[i] -= 1

    while k > 0:
        k -= 1
        now = a[now]
        order += 1
        if l[now] != -1: #既に訪問済の場合
            loop = order - l[now]
            k %= loop
        if k == 0:
            ans = now + 1
            break
        l[now] = order #転送順で何番目の町かを記録

    print(max(ans, -1))

main()