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

dp1=[None]*100001
dp2=[None]*100001
dp1[0]=0
dp2[0]=0
n,W=map(int,input().split())
for i in range(n):
    w,v=map(int,input().split())
    for i in range(v,100001):
        if(dp2[i-v]!=None):
            if(dp2[i]==None):
                dp1[i]=dp2[i-v]+w
            else:
                dp1[i]=min(dp2[i],dp2[i-v]+w)
    dp2=list(dp1)
for i in range(100000,-1,-1):
    if(dp2[i]!=None and dp2[i]<=W):
        print(i)
        break
# 3 8
# 3 3
# 4 5
# 5 6

### FIXED CODE ###

dp1=[None]*100001
dp2=[None]*100001
dp1[0]=0
dp2[0]=0
n,W=map(int,input().split())
for i in range(n):
    w,v=map(int,input().split())
    for i in range(v,100001):
        if(dp2[i-v]!=None):
            if(dp2[i]==None):
                dp1[i]=dp2[i-v]+w
            else:
                dp1[i]=min(dp2[i],dp2[i-v]+w)
    dp2=list(dp1)
for i in range(100000,-1,-1):
    if(dp2[i]!=None and dp2[i]<=W):
        print(i)
        break
# 3 8
# 3 3
# 4 5
# 5 6
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[-1] * W for _ in range(H)]

ans = 0
que = deque([])
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            visited[i][j] = 0
            for di, dj in move:
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W and visited[ni][nj] == -1:
                    que.append((ni, nj, 1))
                    visited[ni][nj] = 1
                    ans = 1

while que:
    i, j, d = que.popleft()
    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and visited[ni][nj] == -1:
            que.append((ni, nj, d+1))
            visited[ni][nj] = d+1
            ans = d+1

print(ans)


### FIXED CODE ###

import numpy as np
import sys
# 距離K以内にxが居ない
# xからの距離を測る

buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
black = np.zeros((R+2,C+2),dtype=np.bool)
black[1:-1,1:] = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#').reshape(R,C+1)

INF = 10 ** 9
dist = np.zeros((R,C),dtype=np.int32)
dist[~black[1:-1,1:-1]] = INF

for n in range(1,R):
  np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(R-2,-1,-1):
  np.minimum(dist[n+1]+1,dist[n],out=dist[n])

for n in range(1,C):
  np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(C-2,-1,-1):
  np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

answer = dist.max()
print(answer)
### BUGGY CODE ###

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

n, y = map(int, input().split())
a = 10000
b = 5000
c = 1000
list = []
for i in range(n+1):
        for j in range((n+1)-i):
                for k in range((n+1)-(i+j)):
                        total = a*i + b*j + c*k
                        if total == y:
                                if (i+j+k) == n:
                                        new_list = [i, j, k]
                                        list.append(new_list)
                                        print("{} {} {}".format(i, j, k))
                                        exit()
                        else:
                                continue
if not list:
        print("-1 -1 -1")

### FIXED CODE ###

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

n, y = map(int, input().split())
a = 10000
b = 5000
c = 1000
list = []
for i in range(n+1):
        for j in range((n+1)-i):
                #for k in range((n+1)-(i+j)):
                        total = a*i + b*j + c*(n-(i+j))
                        if total == y:
                                new_list = [i, j, (n-(i+j))]
                                list.append(new_list)
                                print("{} {} {}".format(i, j, (n-(i+j))))
                                exit()
if not list:
        print("-1 -1 -1")
### BUGGY CODE ###

s = input()

ans = 0

q = s.count('?')

rc = [0]
rq = [0]
la = [0]
lq = [0]

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
    else:
        rc.append(rc[-1])
    if s[len(s)-i-1]=='?':
        rq.append(rq[-1] + 1)
    else:
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
    else:
        la.append(la[-1])
    if s[i]=='?':
        lq.append(lq[-1]+1)
    else:
        lq.append(lq[-1])
rc.reverse()
rq.reverse()

t = 10**9+7

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = 3**(lq[i]-1)%t
        r = 3**(rq[i]-1)%t
        ans += la[i]*3*l*rc[i]*3*r % t
        ans += lq[i]*l*rc[i]*3*r % t
        ans += la[i]*3*l*rq[i]*r % t
        ans += lq[i]*l*rq[i]*r % t

print(int(ans%t))


### FIXED CODE ###

s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

q3.append(1/3)

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(round(ans%t))
### BUGGY CODE ###

#!/usr/bin/env python3
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
n,m,k = map(int,input().split())
uf = UnionFind(n)
#初期化したら友達関係を受け取ってufを形成していく union
friend = [0]*n
# 友達が何人いるかも必要
for i in range(m):
    a,b = map(int,input().split())
    friend[a-1] += 1
    friend[b-1] += 1
    uf.union(a-1,b-1)
# uf が完成したら,c,d を受け取り、parentの値が同じならblock[c],bloc[d]+=1をする
block = [0]*n
for j in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1]+=1
        block[d-1]+=1
"""
print(uf.parents)
print(block)
print(friend)"""
for i in range(n):
    #print(abs(uf.parents[uf.find(i)]),":",i)
    print(abs(uf.parents[uf.find(i)]) - 1 - friend[i] - block[i],end=" ")

### FIXED CODE ###

#!/usr/bin/env python3
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            #self.parents[x] = self.find(self.parents[x])
            #return self.parents[x]
            return self.find(self.parents[x])

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
n,m,k = map(int,input().split())
uf = UnionFind(n)
#初期化したら友達関係を受け取ってufを形成していく union
friend = [0]*n
# 友達が何人いるかも必要
for i in range(m):
    a,b = map(int,input().split())
    friend[a-1] += 1
    friend[b-1] += 1
    uf.union(a-1,b-1)
# uf が完成したら,c,d を受け取り、parentの値が同じならblock[c],bloc[d]+=1をする
block = [0]*n
for j in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1]+=1
        block[d-1]+=1
"""
print(uf.parents)
print(block)
print(friend)"""
for i in range(n):
    #print(abs(uf.parents[uf.find(i)]),":",i)
    print(abs(uf.parents[uf.find(i)]) - 1 - friend[i] - block[i],end=" ")
### BUGGY CODE ###

S = list(input())
T = list(input())

# S=list("BBAAABA")
# T=list("BBBA")

q = int(input())

l = []
for i in range(q):
	l.append(list(map(int,input().split(" "))))


i = 1
while i < len(S):
	i <<= 1
sta = [0 for i in range(i*2)]

i = 1
while i < len(S):
	i <<= 1
stb = [0 for i in range(i*2)]

i = 1
while i < len(T):
	i <<= 1
tta = [0 for i in range(i*2)]

i = 1
while i < len(T):
	i <<= 1
ttb = [0 for i in range(i*2)]

for i in range(len(S)):
	if S[i] == "A":
		sta[i+len(sta)//2] = 1
	else:
		stb[i+len(stb)//2] = 1

for i in range(len(T)):
	if T[i] == "A":
		tta[i+len(tta)//2] = 1
	else:
		ttb[i+len(ttb)//2] = 1

def make(l):
	def do(i):
		if i >= len(l)//2:
			return(l[i])
		else:
			l[i] = do(i*2)+do(i*2+1)
			return(l[i])

	do(1)

def get(li,a,b):   #[a,b]を調べる
		def foo(k,a,b,l,r): #[a,b)を調べる
			if b <= l or r <= a:
				return(0)
			elif a <= l and r <= b:
				return(li[k])
			else:
				return(
					foo(2*k,a,b,l,(r+l)//2)+foo(2*k+1,a,b,(r+l)//2,r)
					)

		return(foo(1,a,b+1,0,len(li)//2))

make(sta)
make(stb)
make(tta)
make(ttb)

for a,b,c,d in l:
	sa = get(sta,a-1,b-1)
	sb = get(stb,a-1,b-1)
	ta = get(tta,c-1,d-1)
	tb = get(ttb,c-1,d-1)


	if (sa+sb*2)%3 == (ta+tb*2)%3:
		print("YES")
	else:
		print("NO")





















### FIXED CODE ###

S = list(input())
T = list(input())

# S=list("BBAAABA")
# T=list("BBBA")

q = int(input())

l = []
for i in range(q):
	l.append(list(map(int,input().split(" "))))


sta = [0 for i in range(len(S))]
stb = [0 for i in range(len(S))]

tta = [0 for i in range(len(T))]
ttb = [0 for i in range(len(T))]

if S[0] == "A":
	sta[0] = 1
else:
	stb[0] = 1

if T[0] == "A":
	tta[0] = 1
else:
	ttb[0] = 1

for i in range(1,len(S)):
	if S[i] == "A":
		sta[i] = sta[i-1]+1
		stb[i] = stb[i-1]
	else:
		sta[i] = sta[i-1]
		stb[i] = stb[i-1]+1

for i in range(1,len(T)):
	if T[i] == "A":
		tta[i] = tta[i-1]+1
		ttb[i] = ttb[i-1]
	else:
		tta[i] = tta[i-1]
		ttb[i] = ttb[i-1]+1


def get(l,a,b):
	if a == 0:
		return(l[b])
	else:
		return(l[b]-l[a-1])

for a,b,c,d in l:
	sa = get(sta,a-1,b-1)
	sb = get(stb,a-1,b-1)
	ta = get(tta,c-1,d-1)
	tb = get(ttb,c-1,d-1)


	if (sa+sb*2)%3 == (ta+tb*2)%3:
		print("YES")
	else:
		print("NO")
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
P = [0]*N
E = [0]*N
EV = [0]*(N-K+1)


for i in range(N):
    P[i] = (p[i]+1)*p[i]/2
    E[i] = P[i]/p[i]
if N==K:
    print(sum(E))
elif K==1:
    print(max(E))
else:
    for i in range(N-K+1):
        count = 0
        for j in range(K):
            count = count+E[i+j]
        EV[i] = count
    print(max(EV))

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
P = [0]*N
E = [0]*N
ev = [0]*(N+1)
EV = [0]*(N-K+1)

for i in range(N):
    P[i] = (p[i]+1)*p[i]/2
    E[i] = P[i]/p[i]
if N==K:
    print(sum(E))
elif K==1:
    print(max(E))
else:
    for i in range(N):
        ev[i+1] = ev[i]+E[i]
    for i in range(N-K+1):
        EV[i]=ev[i+K]-ev[i]
    print(max(EV))
### BUGGY CODE ###

N = int(input())
S = []
for i in range(1, N+1):
        S_i = input()
        S.append(S_i)
cnt = 0
for i in range(0, N):
        flg = 0
        for j in range(i+1, N):
                if( S[i] == S[j]):
                        flg = 1
        if(flg ==0):
                cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = []
for i in range(1, N+1):
        S_i = input()
        S.append(S_i)
A = set(S)
print(len(A))
### BUGGY CODE ###


N, K = [int(x) for x in input().split()] 
h = [int(x) for x in input().split()]

def chmin(a, b):
    return a if a <= b else b

dp = [float('inf')] * N
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i + j >= len(dp):
            break
        else:
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
        
print(dp[-1])

### FIXED CODE ###


N, K = [int(x) for x in input().split()] 
h = [int(x) for x in input().split()]

def chmin(a, b):
    return a if a <= b else b

dp = [float('inf')] * N
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i + j >= len(dp):
            break
        else:
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
        
print(dp[-1])
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
for i in range(N):
  if i > 0:
    dp[i] = min([dp[i - j] + abs(h[i] - h[i - j]) if i - j >= 0 else 10**9 for j in range(1, K + 1)])
print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
for i, hi in enumerate(h):
  if i > 0:
    x = max(0, i - K)
    dp[i] = min([dpj + abs(hi - hj) for hj, dpj in zip(h[x:i], dp[x:i])])
print(dp[N - 1])
### BUGGY CODE ###

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    result = []

    for i in range(N):
        if i % 2:
            result.append(A[i])
        else:
            result.insert(0, A[i])

    if N % 2:
        print(*result)
    else:
        print(*result[::-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

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


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

    result = collections.deque()

    for i in range(N):
        if i % 2 == N % 2:
            result.append(A[i])
        else:
            result.appendleft(A[i])
    print(*result)


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

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

for i in range(N):
    s[i] = sorted(s[i]) # 2次元配列になる

ans = 0
for i in range(N-1): # iは0からN-2まで
    for j in range(i+1, N): # jはi+1からN-1まで
        if s[i] == s[j]:
            ans += 1

print(ans)

### FIXED CODE ###

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

Dict = {} # 空の辞書を用意(集合ともみれるが)
ans = 0

for i in range(N):
    s[i] = ''.join(sorted(s[i])) # 文字列をソートすると配列になる
    if s[i] in Dict:
        ans += Dict[s[i]] # あったら過去にあった個数をansに代入
        Dict[s[i]] += 1 # 値に1追加
    else:
        Dict[s[i]] = 1 # なかったら辞書にキー(文字列)と値1を格納

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

S = input()
Q = int(input())
k = 1
l = ""
r = ""
for _ in range(Q):
    query = input()
    if query.startswith('1'):
        k *= -1
    elif query.startswith('2'):
        t, f, c = query.split()
        if f == '1':
            if k > 0:
                l += c
            else:
                r += c
        elif f == '2':
            if k > 0:
                r += c
            else:
                l += c

if k > 0:
    l = l[::-1]
    print(l + S + r)
else:
    print(r[::-1] + S[::-1] + l)


### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
k = 1
d = deque(S)
for _ in range(Q):
    query = input()
    if query.startswith('1'):
        k *= -1
    elif query.startswith('2'):
        t, f, c = query.split()
        if f == '1':
            if k > 0:
                d.appendleft(c)                
            else:
                d.append(c)
        elif f == '2':
            if k > 0:
                d.append(c)
            else:
                d.appendleft(c)
d = list(d)
if k > 0:
    print(''.join(d))
else:
    print(''.join(d[::-1]))
### BUGGY CODE ###

s = list(str(input()))
q = int(input())
for i in range (q):
    t = list(str(input()))
    if t[0] == '2':
        if t[2] == '1':
            s.reverse()
            s.append(t[4])
            s.reverse()      
        else:
            s.append(t[4])
    else:
        s.reverse()
print(''.join(s))

### FIXED CODE ###

s = list(str(input()))
q = int(input())
f = []
b = []
cnt = 0
for i in range (q):
    t = list(str(input()))
    if t[0] == '2':
        if t[2] == '1':
            f.append(t[4])
        else:
            b.append(t[4])
    else:
        x = f
        y = b
        f = y
        b = x
        cnt += 1
f.reverse()
if cnt%2 != 0:
    s.reverse()
    
print(''.join(f) + ''.join(s) + ''.join(b))
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    mod = (10**9)+7
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n):
        a[i] %= mod
    for i in range(n-1):
        for j in range(i+1, n):
            ans +=  a[i]*a[j]
    print(ans%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    mod = (10**9)+7
    n = int(input())
    a = list(map(int, input().split()))
    suma = sum(a)
    for i in range(n-1):
        suma -= a[i]
        ans += a[i]*suma
    print(ans%mod)

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

from itertools import product
H, W, N = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(N)]
count = {}
for x, y in A:
    for xx, yy in product(range(x-1, x+2), range(y-1, y+2)):
        if 2 > xx or xx > H-1 or 2 > yy or yy > W-1:
            continue
        count[(xx, yy)] = count.get((xx, yy), 0) + 1
ans = [0] * 10
for v in count.values():
    ans[v] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep="\n")


### FIXED CODE ###

from itertools import product
H, W, N = list(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(N)]
count = {}
for x, y in A:
    for xx, yy in product(range(x-1, x+2), range(y-1, y+2)):
        if not(2 <= xx <= H-1 and 2 <= yy <= W-1):
            continue
        count[(xx, yy)] = count.get((xx, yy), 0) + 1
ans = [0] * 10
for k, v in count.items():
    ans[v] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans, sep="\n")
### BUGGY CODE ###

n = int(input())
mul_list = []
for i in range(1, n+1):
    if n % i == 0:
        if i <= n / i:
            mul = [i, n/i]
            mul_list.append(mul)
        else:
            break
length = 10000000000000
result = 0
for line in mul_list:
    dif = len(str(line[1]))-len(str(line[0]))
    if dif < length:
       result = len(str(int(line[1])))
print(result)    

### FIXED CODE ###

n = int(input())
mul_list = []
for i in range(1, n+1):
    if i <= n / i:
        if n % i == 0:
            mul = [i, n/i]
            mul_list.append(mul)
    else:
        break
length = 10000000000000
result = 0
for line in mul_list:
    dif = len(str(line[1]))-len(str(line[0]))
    if dif < length:
       result = len(str(int(line[1])))
print(result)
### BUGGY CODE ###

n = int(input())
phrases = [tuple(map(int, input().split())) for _ in range(n)]
m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + 394)
dp[0] = 0

for s, l, p in phrases:
    for i in range(max_length):
        if dp[i] > -1:
            for j in range(s, l + 1):
                dp[i + j] = max(dp[i + j], dp[i] + p)

results = [dp[melody] for melody in melodies]
print(-1 if -1 in results else '\n'.join(map(str, results)))

### FIXED CODE ###

from collections import defaultdict

max_phrases = defaultdict(int)
n = int(input())
for _ in range(n):
    s, l, p = map(int, input().split())
    for length in range(s, l + 1):
        max_phrases[length] = max(max_phrases[length], p)

m = int(input())
melodies = [int(input()) for _ in range(m)]

max_length = max(melodies)
dp = [-1] * (max_length + max(max_phrases))
dp[0] = 0

for i in range(max_length):
    c = dp[i]
    if c == -1:
        continue
    for length, p in max_phrases.items():
        dp[i + length] = max(dp[i + length], c + p)

results = [dp[melody] for melody in melodies]
print(-1 if -1 in results else '\n'.join(map(str, results)))
### BUGGY CODE ###

N, M = map(int, input().split())

while 2 * N + 1 < M:
    N += 1
    M -= 2

print(min(N, M // 2))

### FIXED CODE ###

N, M = map(int, input().split())

x = max(0, (M - 2 * N) // 4)
N += x
M -= 2 * x

print(min(N, M // 2))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(int(i) for i in input().split())

kitai = list(map(lambda x: (x+1)/2, p))

gokei = 0

for i in range(n-k+1):
    wa = sum(kitai[i:i+k])
    if gokei < wa:
        gokei = wa

print(gokei)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(int(i) for i in input().split())

kitai = [(x+1)/2 for x in p]

rui_kitai = [kitai[0]]

for i in range(1, n):
    ruiseki=rui_kitai[i-1]+kitai[i]
    rui_kitai.append(ruiseki)

gokei = 0

for i in range(n-k+1):
    if i==0:
        wa = rui_kitai[k-1]
    else:
        wa = rui_kitai[i+k-1]-rui_kitai[i-1]
    if gokei < wa:
        gokei = wa

print(gokei)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
if N<K:
  ans=0
else:
  for i in range(K):
    A.remove(max(A))
  ans=sum(A)
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
ans=0
if N<=K:
  pass
else:
  A=list(map(int,input().split()))
  A.sort()
  ans=sum(A[:N-K])
print(ans)
### BUGGY CODE ###

a, b = map(int, input().split())
divisor = []
upper = min(a, b)//2+1
if a%2 or b%2:
    for i in range(3, upper, 2):
        divable = False
        if a % i == 0 and b % i == 0:
            for j in range(len(divisor)):
                if i % divisor[j] == 0:
                    divable = True
                    break
            if not divable:
                divisor.append(i)
else:
    for i in range(2, upper):
        divable = False
        if a % i == 0 and b % i == 0:
            for j in range(len(divisor)):
                if i % divisor[j] == 0:
                    divable = True
                    break
            if not divable:
                divisor.append(i)
print(len(divisor)+1)

### FIXED CODE ###

a, b = map(int, input().split())
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
n = gcd(a, b)
ndiv = n
if n == 1:
    print(1)
else:
    i = 1
    primecount = 0
    divisor = False
    while True:
        i += 1
        while ndiv%i == 0:
            ndiv = ndiv//i
            divisor = True
        if divisor:
            primecount += 1
            divisor = False
            if ndiv == 1:
                break
        if ndiv != 1 and i*i > n:
            primecount += 1
            break
    print(primecount+1)
### BUGGY CODE ###

x,k,d = map(int,input().split())

if(x < 0):
  while(x < 0):
    k -= 1
    x = x + d
    if(k == 0):
      break
  if(abs(x) > abs(x - d)):
    k += 1
    x = x - d
elif(x > 0):
  while(x > 0):
    k -= 1
    x = x - d
    if(k == 0):
      break
  if(abs(x) > abs(x + d)):
    k += 1
    x = x + d

if(x == 0):
  if(k%2 == 0):
    print(0)
  else:
  	print(d)
else:
  if(k%2 == 0):
    print(abs(x))
  else:
    print(min(abs(x+d),abs(x-d)))

### FIXED CODE ###

x,k,d = map(int,input().split())

if(x < 0):
  i = int(abs(x)/d)
  if(k > i):
    k = k - i
    x = x + d*i
  else:
    x = x + d*k
    k = 0
  if(abs(x) > abs(x - d)):
    k += 1
    x = x - d
elif(x > 0):
  i = int(abs(x)/d)
  if(k > i):
    k = k - i
    x = x - d*i
  else:
    x = x - d*k
    k = 0
  if(abs(x) > abs(x + d)):
    k += 1
    x = x + d

if(x == 0):
  if(k%2 == 0):
    print(0)
  else:
  	print(d)
else:  
  if(k%2 == 0):
    print(abs(x))
  else:
    print(min(abs(x+d),abs(x-d)))
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import connected_components
N, M = map(int, input().split())
matrix = np.array([[0] * N for _ in range(N)], dtype=np.bool)
for _ in range(M):
    i, j, _ = map(int, input().split())
    matrix[i - 1][j - 1] = True

print(connected_components(matrix)[0])


### FIXED CODE ###

import numpy as np
from scipy.sparse import csr_matrix, csgraph
N, M = map(int, input().split())
row, column, _ = np.array([tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(M)], dtype=np.int32).T
matrix = csr_matrix(([1] * M, (row, column)), shape=(N, N), dtype=np.int32)
print(csgraph.connected_components(matrix)[0])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#import numpy as np
n,m = map(int, input().split())
i=0
lst = []
while i < m: 
    l = list(map(int, input().split()))
    l.append(i)
    lst.append(l)
    i+=1
sort_lst = sorted(lst)
i=1
res=[]
for i in range(1,n+1):
    j=1
    for k in sort_lst:
        if i == k[0]:
            res.append([k[2],str(k[0])+str(k[1]),str(k[0]).rjust(6,'0') + str(j).rjust(6,'0')])
            j+=1
#ans
for ans in sorted(res):
    print(ans[2])


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
i=0
lst = []
while i < m: 
    lst.append(list(map(int, input().split())) + [i])
    i+=1
lst = sorted(lst)
j=0
i=1
for k in lst:
    if i != k[0]:
        i=k[0]
        j=1
        k[1]=i*1000000+j
    else:
        j+=1
        k[1]=i*1000000+j

#ans
for ans in sorted(lst, key=lambda x:x[2]):
    print('{0:012d}'.format(ans[1]))