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

nums = list(map(int, input().split()))
n = nums[0]
m = nums[1]

codes = []
prefectures = []


class Prefecture:
    def __init__(self, id, list):
        self.id = id
        self.list = list


for i in range(m):
    codes.append(list(map(int, input().split())))

for code in codes:
    exist = False
    for prefecture in prefectures:
        if code[0] == prefecture.id:
            prefecture.list.append(code[1])
            exist = True
            break
    if not exist:
        prefectures.append(Prefecture(code[0], [code[1]]))

for prefecture in prefectures:
    prefecture.list = sorted(prefecture.list)

for code in codes:
    for prefecture in prefectures:
        if code[0] == prefecture.id:
            for i in range(len(prefecture.list)):
                if code[1] == prefecture.list[i]:
                    print(str(code[0]).zfill(6) + str(i+1).zfill(6))
            break

### FIXED CODE ###

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

prefectures = []

i = 0
while i < m:
    p, y = map(int, input().split())
    prefectures.append((i, p, y))
    i += 1
prefectures.sort(key=lambda x: x[2])

answers = []
ranks = [1 for i in range(n + 1)]
for i, p, y in prefectures:
    answers.append((i, str(p).zfill(6) + str(ranks[p]).zfill(6)))
    ranks[p] += 1

answers.sort()

for i, answer in answers:
    print(answer)
### BUGGY CODE ###

#%%
s = list(input())
ans = 0
i = 0

while True:
    if i < 0 :
        i += 1
    elif len(s)-2 <= i:
        break
    else:
        if s[i] == 'A':
            if s[i+1] == 'B' and s[i+2] == 'C':
                ans += 1
                s[i], s[i+1], s[i+2] = 'B', 'C', 'A'
                i -= 1
            else:
                i += 1
        else:
            i += 1

print(ans)


### FIXED CODE ###

#%%
s = list(input())
i = 0
ss = ''

while True:
    if i <= len(s) - 2:
        if s[i] == 'B' and s[i+1] == 'C':
            ss += 'D'
            i += 2
        else:
            ss += s[i]
            i += 1          
    else:
        ss += s[i]
        i += 1
    if i >= len(s):
        break
#print(ss)

a = 0
ans = 0
for i in range(len(ss)):
    if ss[i] == 'A':
        a += 1
    elif ss[i] == 'D':
        ans += a
    else:
        a = 0
print(ans)

#%%
### BUGGY CODE ###

import itertools
def inpl(): return [int(i) for i in input().split()]
def f(y):
    return abs(x-A[y])
N, Q = inpl()
A = inpl()
SA = list(itertools.accumulate(A))
if N%2 :
    B = [v for i, v in enumerate(A) if not i%2]
    B = [0] + list(itertools.accumulate(B))
else:
    B = [v for i, v in enumerate(A) if i%2]
    B = [0] + list(itertools.accumulate(B))
    
for _ in range(Q):
    x = int(input())
    lo = 1
    hi = -(-N//2) + 1
    while hi - lo >1:
        mid = (lo+hi)//2
        if mid == 1:
            continue
        if max(f(N-mid-1), f(N-2*mid+1)) <= f(N-mid):
            lo = mid
        else:
            hi = mid    
    print(SA[N-1] - SA[N-lo-1] + B[-((2*lo-N)//2)])
   

### FIXED CODE ###

import itertools
import sys
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
def f(y):
    return abs(x-A[y])
N, Q = inpl()
A = inpl()
SA = list(itertools.accumulate(A))
if N%2 :
    B = [v for i, v in enumerate(A) if not i%2]
    B = [0] + list(itertools.accumulate(B))
else:
    B = [v for i, v in enumerate(A) if i%2]
    B = [0] + list(itertools.accumulate(B))
    
for _ in range(Q):
    x = int(input())
    lo = 1
    hi = -(-N//2) + 1
    while hi - lo >1:
        mid = (lo+hi)//2
        if mid == 1:
            continue
        if max(f(N-mid-1), f(N-2*mid+1)) <= f(N-mid):
            lo = mid
        else:
            hi = mid    
    print(SA[N-1] - SA[N-lo-1] + B[-((2*lo-N)//2)])
### BUGGY CODE ###

from collections import*
n,u,v=map(int,input().split())
e=[[]for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(v,0)])
while q:
  now,c=q.popleft()
  d[now]=c
  for to in e[now]:
    if d[to]!=INF:continue
    q.append((to,c+1))
q=[(u,0)]
ans=0
vis=[1]*(n+1)
while q:
  now,c=q.pop()
  vis[now]=1
  f=1
  for to in e[now]:
    if vis[to]:
      f=0
      if d[to]>c+1:q+=[(to,c+1)]
      if d[to]==c+1:ans=max(c+1,ans)
      else:ans=max(c,ans)
  if f:ans=max(d[to],ans)
print(ans)

### FIXED CODE ###

from collections import*
n,u,v=map(int,input().split())
e=[[]for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(v,0)])
while q:
  now,c=q.popleft()
  d[now]=c
  for to in e[now]:
    if d[to]!=INF:continue
    q.append((to,c+1))
q=[(u,0)]
ans=0
vis=[1]*(n+1)
while q:
  now,c=q.pop()
  vis[now]=0
  f=1
  for to in e[now]:
    if vis[to]:
      f=0
      if d[to]>c+1:q+=[(to,c+1)]
      if d[to]==c+1:ans=max(c+1,ans)
      else:ans=max(c,ans)
  if len(e[now])==1:ans=max(d[to],ans)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
exc = 0

for i in range(N):
    for j in range(N):
        d = j - i
        if d <= 0 or d + j > N - 1 or S[i] == S[j]:
            continue
        k = d + j
        if S[k] != S[i] and S[k] != S[j]:
            exc += 1

ans = S.count("R") * S.count("G") * S.count("B") - exc
print(ans)

### FIXED CODE ###

N = int(input())
S = [s for s in input()]
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j + (j - i)
        if N - 1 < k:
            continue
        if S[k] != S[i] and S[k] != S[j] and S[i] != S[j]:
            ans -= 1

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

from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
b = gcd(a[0], a[1])
c = [a[0], a[1]]
for i in range(2, n):
    g1 = gcd(b, a[i])
    d = []
    for j in c:
        g2 = gcd(j, a[i])
        if g2 > 1:
            d.append(g2)
    c = d
    if b > 1:
        c.append(b)
    b = g1

if c:
    print(max(c))
else:
    print(1)

### FIXED CODE ###

from fractions import gcd
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
oc = []
b = 0
for i, v in c.items():
    if v == 1:
        oc.append(i)
    else:
        if b == 0:
            b = i
        else:
            b = gcd(b, i)

loc = len(oc)
if loc <= 1:
    print(b)
    exit()

c = [oc[0], oc[1]]
e = gcd(oc[0], oc[1])
if loc == 2:
    c.append(e)
for i in range(2, loc):
    g1 = gcd(e, oc[i])
    d = []
    for cc in c:
        g2 = gcd(cc, oc[i])
        if g2 > 1:
            d.append(g2)
    c = d
    if e > 1:
        c.append(e)
    if i == loc-1:
        c.append(g1)
    e = g1

if b >= 2:
    print(max([gcd(cc, b) for cc in c]))
elif b == 0:
    print(max(c))
else:
    print(1)
### BUGGY CODE ###

from functools import reduce
import operator
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if not ANS[idx]:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if not ANS[i] : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if not ANS[i] : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.998
INIT = None
ANS = [INIT]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

from bisect import bisect_left as bl
N, M = map(int, input().split())
work = [list(map(int, input().split())) for _ in range(N)]
work.sort(key = lambda x: x[1], reverse=True)
#print(work)
inf = 10 ** 5 + 1
money = 0
able = [i for i in range(M + 1)] + [inf]
added = 0
for i in range(N):
  if added == M:
    break
  ind = bl(able, work[i][0])
  if able[ind] != inf:
    able = able[: ind] + able[ind + 1: ]
    money += work[i][1]
    added += 1
print(money)



### FIXED CODE ###

import heapq
N, M = map(int, input().split())
work = [[0] for _ in range(M + 1)]
for _ in range(N):
  d, p = map(int, input().split())
  if d > M: continue
  work[d].append(-p)
#print(work)
money = 0
q = work[1]
heapq.heapify(q)
for i in range(1, M + 1):
  #print(q)
  if len(q) != 0:
    money += heapq.heappop(q)
  if i == M: continue
  for p in work[i + 1]:
    heapq.heappush(q, p)
print(-money)
### BUGGY CODE ###

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

out = 0

for i in range(max(a)+1):
    cnt = 0
    for j in a:
        if j == i or j-1 == i or j+1 == i:
            cnt += 1
    out = max(out, cnt)

print(out)

### FIXED CODE ###

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

def func(a):
  count = [0] * (max(a)+1)

  for i in a:
      count[i] += 1

  max_n = 0
  for j in range(1, len(count)-1):
      max_n = max(max_n, count[j] + count[j-1] + count[j+1])
  max_n = max(max_n, count[-1] + count[-2])

  return max_n

print(n if len(set(a)) == 1 else func(a))
### BUGGY CODE ###

import collections
import math
n, m = [int(item) for item in input().split()]

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return collections.Counter(table)

cnt = prime_decomposition(m)

ans = 1
for item in cnt:
  ans *= int(math.factorial(n + cnt[item] - 1) // int(math.factorial(cnt[item]) * math.factorial(n-1)))
  ans = int(ans) % (1000000000 + 7)
print(ans)

### FIXED CODE ###

import collections
import math
n, m = [int(item) for item in input().split()]

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1
    return prime_count

cnt = trial_division_sqrt(m)

ans = 1
for item in cnt:
  h = 1
  k_fact = 1
  for i in range(cnt[item]):
    h *= n + cnt[item] - 1 - i
    k_fact *= (i+1)
  ans *= h
  ans = ans // k_fact
  ans = ans % (1000000000 + 7)
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce


def calc_comb(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n = int(input())
    a = [int(an) for an in input().split()]
    a.sort()
    ans = 0
    max_comb = 0
    sub_set = set()
    for i in range(n - 1):
        sub = a[-1] - a[i]
        if not sub in sub_set:
            sub_set.add(sub)
            comb = calc_comb(a[-1], a[i])
            if comb > max_comb:
                max_comb = comb
                ans = a[i]
    print(f'{a[-1]} {ans}')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    _ = int(input())
    a = [int(an) for an in input().split()]
    a.sort()
    half_val = -(-a[-1] // 2)
    dist_list = [abs(half_val - an) for an in a[:-1]]
    min_index = dist_list.index(min(dist_list))
    print(f'{a[-1]} {a[min_index]}')


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

d=[0]*13
d[0]=1
mul=1
mulmod=1
t=list(input())
t.reverse()
zero=[0]*13
for c in t:
    e=zero[:]

    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            #e[(i*mul+j)%13]+=d[j]
            k=(i*mul+j)%13
            e[k]+=d[j]
            e[k]%=1000000007
    d,e=e,d
    mul*=10
    #mulmod=mul%13
print(d[5])



### FIXED CODE ###

# coding: utf-8
# Your code here!
 
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
s = input()
l = len(s)
MOD = 10**9+7
 
dp = [0]*13
dp[0] = 1
for i in s:
    new = [0]*13
    if i == "?":
        for i in range(10):
            for j in range(13):
                new[(10*j+i)%13] += dp[j]
    else:
        i = int(i)
        for j in range(13):
            new[(i+10*j)%13] += dp[j]
    
    for i in range(13):
        new[i] %= MOD
    dp,new = new,dp
#    print(dp)
 
print(dp[5]%MOD)
### BUGGY CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target = target | primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

MOD = 1000000007
n = int(input())
aas = list(map(int, input().split()))
KET = 62
arr_0 = [0]*KET
arr_1 = [0]*KET
for i in aas:
    bits = format(i,'062b')
    for j in reversed(range(KET)):
        if bits[j] == '0':
            arr_0[KET-j-1] += 1
        else:
            arr_1[KET-j-1] += 1
res = 0
for i in range(KET):
    res += (arr_0[i]%MOD * arr_1[i]%MOD)%MOD * pow(2,i,MOD)
    res %= MOD
print(res)

### FIXED CODE ###

MOD = 1000000007
n = int(input())
aas = list(map(int, input().split()))
KET = 60
arr_0 = [0]*KET
arr_1 = [0]*KET
for i in aas:
    bits = format(i,'060b')
    for j in reversed(range(KET)):
        if bits[j] == '0':
            arr_0[KET-j-1] += 1
        else:
            arr_1[KET-j-1] += 1
res = 0
for i in range(KET):
    res += (arr_0[i]%MOD * arr_1[i]%MOD)%MOD * pow(2,i,MOD)
    res %= MOD
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main() :
    H,W,D = map(int,input().split())
    Point = {}
    for y in range(H) :
        line = list(map(int,input().split()))
        for x,p in enumerate(line) :
            Point[p] = (y,x)

    Q = int(input())

    def dist(ny,nx,py,px) :
        return abs(ny-py) + abs(nx-px)

    for i in range(Q) :
        l,r = map(int,input().split())
        ny,nx = Point[l]
        res = 0
        while l != r :
            l += D
            py,px = ny,nx
            ny,nx = Point[l]
            res += dist(ny,nx,py,px)
        print(res)
main()


### FIXED CODE ###

H,W,D = map(int,input().split())
Point = {}
for y in range(H) :
    line = list(map(int,input().split()))
    for x,p in enumerate(line) :
        Point[p] = (y,x)

Q = int(input())

def dist(ny,nx,py,px) :
    return abs(ny-py) + abs(nx-px)

Cost = [0]*(H*W+1)
for i in range(D+1, H*W+1) :
    yi,xi = Point[i-D]
    yj,xj = Point[i]
    Cost[i] = Cost[i-D] + dist(yi,xi,yj,xj)


for i in range(Q) :
    l,r = map(int,input().split())
    print(Cost[r] - Cost[l])
### BUGGY CODE ###

n, k = [int(i) for i in input().split(' ')]
input_list = [int(i) for i in input().split(' ')]
 
maximum = 0
for i in range(n-k+1):
  maximum = max(maximum, sum(input_list[i:i+k]))

print( (maximum + k) / 2 )

### FIXED CODE ###

n, k = [int(i) for i in input().split(' ')]
input_list = [int(i) for i in input().split(' ')]
 
maximum = sum(input_list[:k])
s = sum(input_list[:k])
for i in range(1, n-k+1):
  s = s - input_list[i-1] + input_list[i+k-1]
  maximum = max(maximum, s)

print( (maximum + k) / 2 )
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import (
  Counter, 
  defaultdict )

def main():
  s = input().strip()
  x = remain = 0
  remains = defaultdict(int)
  for i, d in enumerate(map(int, list(s[::-1]))):
    x = d * (10**i) + x
    remain = x % 2019
    remains[remain] += 1

  cnt = 0
  for k, v in remains.items():
    cnt += (v * (v - 1)) // 2
    if k == 0:
      cnt += v
  print(cnt)
  
if __name__=='__main__':
  main()


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  s = input().strip()
  x = remain = 0
  remains = [0] * 2019
  k = 1
  for d in map(int, list(s[::-1])):
    x = d * k + remain
    remain = x % 2019
    k = (10 * k) % 2019
    remains[remain] += 1

  print(sum([(remain * (remain - 1)) // 2 for remain in remains]) + remains[0])
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

N=int(input())

S=input()

#print(S)

list1=[]

for i in range(N):
    E=S[:i].count("W")
    W=S[i+1:].count("E")
    list1.append(E+W)
    
print(min(list1))

### FIXED CODE ###


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

#print(S)
#print(S[1:])
list1=[]

ST=S[1:].count("E")
list1.append(ST)
#print(list1)

for i in range(1,N):
    if S[i]=="E":
        ST=ST-1
    if S[i-1]=="W":
        ST=ST+1
    list1.append(ST)
#print(list1)
print(min(list1))
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
N += 1
match = [[] for i in range(N)]
for i in range(1, N):
    match[uf[i]].append(i)
for i in range(1, N):
    matchlen = len(match[i])
    for j in range(matchlen):
        if p[match[i][j]] in match[i]:
            ans += 1
print(str(ans))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
#N += 1
#match = [[] for i in range(N)]
#for i in range(1, N):
#    match[uf[i]].append(i)
#for i in range(1, N):
#    matchlen = len(match[i])
#    for j in range(matchlen):
#        if p[match[i][j]] in match[i]:
#            ans += 1

for i in range(1, N+1):
    if same(i, p[i]):
        ans += 1
print(str(ans))
### BUGGY CODE ###

S = input()
N = len(S)

MOD = 10**9 + 7
dp = [[0 for _ in range(13)] for _ in range(N)]  # dp[i][j]: S[i]までみて13で割ってjあまるものの個数

# 初期値
if S[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1


# dpテーブル更新式
for i in range(1, N):
    si = S[i]
    if si == "?":
        for si_cand in range(10):
            for j in range(13):
                dp[i][(j*10+si_cand)%13] += dp[i-1][j] % MOD
    else:
        for j in range(13):
            dp[i][(j*10+int(si))%13] += dp[i-1][j] % MOD

print(dp[N-1][5] % MOD)


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13

print(dp[len(S)][5])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(300000)
input = sys.stdin.readline

N, Q = map(int, input().split())
children = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    children[a].append(b)

alls = [[] for _ in range(N + 1)]


def chase(node):
    ret = [node]
    for c in children[node]:
        ret.extend(chase(c))
    alls[node] = ret
    return ret


chase(1)

Co = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    for j in alls[p]:
        Co[j] += x
Co.pop(0)

print(" ".join(map(str, Co)))

### FIXED CODE ###

import sys

sys.setrecursionlimit(300000)
input = sys.stdin.readline

N, Q = map(int, input().split())
children = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    children[a].append(b)

Ps = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    Ps[p] += x

Co = [0] * (N + 1)
import collections

q = collections.deque([(1, 0)])
while (len(q) > 0):
    now, pa = q.popleft()
    Co[now] = Ps[now] + Co[pa]
    for c in children[now]:
        q.append((c, now))

Co.pop(0)
print(" ".join(map(str, Co)))
### BUGGY CODE ###

N, K = map(int, input().split(" "))
H = [int(i) for i in input().split(" ")]

cost = [0 for _ in range(N)]
for i in range(1,N):
    c_lst = [abs(H[i]-H[i-j-1])+cost[i-(j+1)] for j in range(min(K, i))]
    cost[i] = min(c_lst)
print(cost[-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split(" "))
H = np.array([int(i) for i in input().split(" ")])

cost = np.array([0] + [10**9 for _ in range(N-1)])
for i in range(1,N):
    cost[i] = np.min(cost[max(0,i-K):i] + np.abs(H[max(0,i-K):i] - H[i]))

print(cost[-1])
### BUGGY CODE ###

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

if x==y:
  print(-1)
elif y==1:
  print(-1)
else:
  for i in range(1,10**10):
    if x*i>10**18:
      break
    elif x*i%y !=0:
      print(x*i)
      break


### FIXED CODE ###

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

if x%y==0:
  print(-1)
else:
  print(x)