Harryxun/stf_run huggingface dataset:
sa = input()
sb = input()
sc = input()
start  = sa.pop(0)

for i in range(399):
  if len(sa) == 0 :
    print("A")
    exit()
  if len(sb) == 0:
    print("B")
    exit()
  if len(sc) == 0:
    print("C")
    exit()
  if start == "a":
    start = sa.pop(0)
  if start == "b":
    start = sb.pop(0)
  if start == "c":
    start = sc.pop(0)

### FIXED CODE ###

a = list(input())
b = list(input())
c = list(input())
next = a.pop(0)
while True:
  if next == "a":
    if a == []:
      print("A")
      break
    else:
      next = a.pop(0)
  elif next == "b":
    if b == []:
      print("B")
      break
    else:
      next = b.pop(0)
  else:
    if c == []:
      print("C")
      break
    else:
      next =c.pop(0)
x = int(input())

ans = []

for i in range(2,x+1):
  for j in range(2,x+1):
    if i**j > x:
      break
    ans.append(i**j)
      
print(max(ans))

### FIXED CODE ###

x = int(input())

ans = []
if x == 1:
  print(1)
  exit()

for i in range(2,x+1):
  for j in range(2,x+1):
    if i**j > x:
      break
    ans.append(i**j)

if len(ans)==0:
  print(0)
else:
  print(max(ans))
[A, B, C, D] = list(map(int, input().split()))
X = A / D
Y = B / C
if X >= Y:
    prinT('Yes')
else:
    print('No')

### FIXED CODE ###

[A, B, C, D] = list(map(int, input().split()))
while A > 0:
    C -= B
    if C <= 0:
        print('Yes')
        break
    A -= D
    if A <= 0:
        print('No')
        break
#!/usr/bin/env python3
#abc126 e

N,M = list(map(int,input().split()))
XYZ = [list(map(int,input().split())) for _ in range(M)]

G = [[] for _ in range(N)]

for i in XYZ:
    G[i[0]-1].append(i[1])
    G[i[1]-1].append(i[0])

check = [False for _ in range(N)]#各頂点を訪問したかどうか
def DFS(G,s):
    check[s-1] = True
    for i in G[s-1]:
        if not check[i-1]:
            DFS(G,i)
    return
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#abc126 e

import sys
sys.setrecursionlimit(1000000)
N,M = list(map(int,input().split()))
XYZ = [list(map(int,input().split())) for _ in range(M)]

G = [[] for _ in range(N)]

for i in XYZ:
    G[i[0]-1].append(i[1])
    G[i[1]-1].append(i[0])

check = [False for _ in range(N)]#各頂点を訪問したかどうか

def DFS(G,s):
    check[s-1] = True
    for i in G[s-1]:
        if not check[i-1]:
            DFS(G,i)
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)
n,m,k=map(int,input().split())
MOD=998244353

def prepare(n, MOD):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs

a,b=prepare(n-1,MOD)
if n==1:
    print(m)
else:
    ans,s=0,(m*pow(m-1,n-k-2,MOD))%MOD
    for x in range(k,-1,-1):
        s*=(m-1)
        s%=MOD
        ans+=(s*a*b[x]*b[n-x-1])%MOD
        ans%=MOD
    print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
MOD=998244353

def prepare(n, MOD):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs

a,b=prepare(n-1,MOD)
ans,s=0,(m*pow(m-1,n-k-1,MOD))%MOD
for x in range(k,-1,-1):
    ans+=(s*a*b[x]*b[n-x-1])%MOD
    ans%=MOD
    s*=(m-1)
    s%=MOD
print(ans)
n,m = map(int,input().split())
para = [int(input()) for i in range(m)]
mod = 10**9+7

import sys
sys.setrecursionlimit(100000)

dp = [1,0]
def dps(cnt,cantvisit):
    if cnt == n + 1 :
        return 

    else :
        if cnt == 1 :
            if cnt in cantvisit :
                dp[1] = 0
                cnt += 1
            else : 
                dp[1] = 1
                cnt += 1
        else :
            if cnt in cantvisit : 
                a  = 0 
                dp[0] = dp[1]
                dp[1] = a
                cnt += 1
            else :
                
                a  = (dp[0] + dp[1]) % mod
                dp[0] = dp[1]
                dp[1] = a 
                cnt += 1
        return dps(cnt,cantvisit)
dps(1,para)
print("{}".format(dp[1]))

### FIXED CODE ###

n,m = map(int,input().split())
para = [int(input()) for i in range(m)]
mod = 10**9+7
dp = [-1]*(n+1)
for i in para:
    dp[i] = 0
for i in range(n+1):
    if  dp[i] != 0 :
        if i == 1 or i==0:
            dp[i] = 1
        else:
            dp[i] = (dp[i-1] + dp[i-2])%mod



print("{}".format(dp[-1]))
n = int(input())
x = str(input())
X = 0
one = 0
for i in range(n):
    X+=int(x[i])*2**(n-i-1)
    if x[i]=="1":
        one+=1

u = X % one

l = [0, 1]
for i in range(2,n):
    if i%2==0:
        l.append(1)
    else:
        l.append(l[i%bin(i).count("1")]+1)

for i in range(n):
    if x[i]=="0":
        print(l[(X+2**(n-i-1))%(one+1)]+1)
    else:
        print(l[(X-2**(n-i-1))%(one-1)]+1)

### FIXED CODE ###

n = int(input())
x = str(input())

one = x.count("1")
X = int(x, 2)

if one==1:
    for i in range(n):
        if x[i]=="1":
            print(0)
        elif i==n-1:
            print(2)
        else:
            print(1)
    
    
elif one>1:
    
    Xp = X % (one+1)
    Xm = X % (one-1)

    def f(x):
        if x==0:
            return 0
        return 1+f(x%bin(x).count("1"))

    for i in range(n):
        
        if x[i]=="0":
            c = pow(2, n-i-1, one+1)
            print(f((Xp+c)%(one+1))+1)
        else:
            c = pow(2, n-i-1, one-1)
            print(f((Xm-c)%(one-1))+1)
else:
    for i in range(n):
        print(1)
p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
C = {}
D = {}
cnt = 1
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
        D[a] = 0
    C[a] += 1
    D[a] += 1
    if a>0:
        cnt = (cnt*C[a-1])%p
        C[a-1] -= 1
if D[0]==3:
    cnt = (cnt*6)%p
else:
    cnt = (cnt*3)%p
print(cnt)

### FIXED CODE ###

p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
cnt = 1
cnt0 =0
C = {i:0 for i in range(N)}
B = []
for i in range(N):
    a = A[i]
    if a==0:
        cnt = (cnt*(3-cnt0))%p
        cnt0 += 1
    else:
        cnt = (cnt*C[a-1])%p
        C[a-1] -= 1
    C[a] += 1
print(cnt)
s = input()

if s[2] == s[3] and s[4]== s[5]:
	print(‘Yes’)
else:
	print(‘No’)


### FIXED CODE ###

s = input()

if s[2] == s[3] and s[4]== s[5]:
  print('Yes')
else:
  print('No')
import bisect

import numpy as np
from scipy.ndimage.interpolation import shift


def preliminary(k, aaa):
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    fwd = []
    for a in aaa:
        dp |= shift(dp, a)
        fwd.append(dp.copy())

    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    bwd = []
    for a in reversed(aaa):
        dp |= shift(dp, a)
        bwd.append(np.where(dp)[0])
    bwd.reverse()

    fwd.append(np.zeros(k, np.uint8))
    bwd.append([0])

    return fwd, bwd


def solve(k, aaa):
    aaa.sort()
    uk = bisect.bisect_left(aaa, k)
    aaa = aaa[:uk]

    fwd, bwd = preliminary(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        dp = fwd[m - 1]
        for i in bwd[m + 1][1:]:
            dp |= shift(dp, i)
        if dp[-aaa[m]:].any():
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))


### FIXED CODE ###

import bisect


def solve(k, aaa):
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    ans = len(aaa)
    for i, a in reversed(list(enumerate(aaa))):
        if curr_max + a >= k:
            ans = i
        f = True
        for j in range(min(curr_max, k - a - 1), -1, -1):
            if dp[j]:
                dp[j + a] = True
                if f:
                    curr_max = max(curr_max, j + a)
                    f = False
    return ans


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

print(solve(k, aaa))
import numpy as np

ef iterate(mapdata, passed, curr, count):
    if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
        return count

    if mapdata[curr[0]][curr[1]] == '#':
        return 100000 #passed[curr]
    
    if passed[curr] > 0:
        return 100000 #passed[curr]
    passed[curr] = 1
    
    ret = 100000
    if curr[0] < passed.shape[0] - 1:
        tmp = iterate(mapdata, passed, (curr[0] + 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] < passed.shape[1] - 1:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] + 1), count + 1)
        ret = min(ret, tmp)
    if curr[0] > 0:
        tmp = iterate(mapdata, passed, (curr[0] - 1, curr[1]), count + 1)
        ret = min(ret, tmp)
    if curr[1] > 0:
        tmp = iterate(mapdata, passed, (curr[0], curr[1] - 1), count + 1)
        ret = min(ret, tmp)

    return ret


h, w = map(int, input().split())
mapdata = [input() for y in range(h)]
dotsum = sum(mapdata[y].count('.') for y in range(h))

passed = np.zeros((h, w), np.int32)
#passed[:, :] = 100000
count = iterate(mapdata, passed, (0, 0), 0)
#print(count)
if count < 50 * 50:
    print(dotsum - count - 1)
else:
    print(-1)

### FIXED CODE ###

import numpy as np

def iterate2(mapdata, passed, start):
    queue = [(start, 0)]

    while len(queue) > 0:
        curr, count = queue[0]
        del queue[0]
        if curr == (passed.shape[0] - 1, passed.shape[1] - 1):
            return count
        if mapdata[curr[0]][curr[1]] == '#':
            continue
        if passed[curr] > 0:
            continue
        passed[curr] = 1

        if curr[0] < passed.shape[0] - 1:
            queue.append(((curr[0] + 1, curr[1]), count + 1))
        if curr[1] < passed.shape[1] - 1:
            queue.append(((curr[0], curr[1] + 1), count + 1))
        if curr[0] > 0:
            queue.append(((curr[0] - 1, curr[1]), count + 1))
        if curr[1] > 0:
            queue.append(((curr[0], curr[1] - 1), count + 1))
    
    return -1

h, w = map(int, input().split())
mapdata = [input() for y in range(h)]
dotsum = sum(mapdata[y].count('.') for y in range(h))

passed = np.zeros((h, w), np.int8)
count = iterate2(mapdata, passed, (0, 0))
#print(dotsum)
#print(count)
if count > 0:
    print(dotsum - count - 1)
else:
    print(-1)
import sys
n=10**5+1
s=[True]*n
s[0]=False
s[1]=False
for x in xrange(2, int(n**0.5)+1):
    if s[x]:
        for i in xrange(x+x,n,x):
            s[i]=False
for x in sys.stdin.readlines():
    a=int(x)
    cnt=0
    for i in xrange(a):
        if s[i]:
            cnt=cnt+1
    print cnt

### FIXED CODE ###

import sys
n=10**6
p=[1]*n
p[0],p[1]=0,0
for i in xrange(2,int(n**0.5)+1):
    if p[i]==1:
        for j in xrange(i**2,n,i):
            p[j]=0
for i in xrange(2,n):
    p[i]+=p[i-1]
for line in sys.stdin.readlines():
    print p[int(line)]
a, b = input().split()
print(a if a <= b elif a > b a - 1)

### FIXED CODE ###

a, b = map(int, input().split())
print(a if a <= b else a - 1)
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8,i8,i8[:])', cache=True)
def main(N, K, A):
    B = np.maximum(A, 0)
    Acum = np.zeros(len(A) + 1, np.int64)
    Bcum = np.zeros(len(A) + 1, np.int64)
    Acum[1:] = np.cumsum(A)
    Bcum[1:] = np.cumsum(B)
    ret = -(10**18)
    for l in range(N - K + 1):
        r = l + K
        sum1 = Bcum[l]
        sum2 = Bcum[-1] - Bcum[r]
        sum3 = Acum[r] - Acum[l]
        x = sum1 + sum2 + max(sum3, 0)
        ret = max(ret, x)
    return ret

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(N, K, A))


### FIXED CODE ###

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

import numpy as np

# どこかの長さKは最後に単色で残る
# そこを残すと決めると他は自由に設定できる

N,K = map(int,input().split())
A = np.array(input().split(), dtype=np.int64)

Acum = A.cumsum()
range_sum = Acum[K-1:] - Acum[:N-(K-1)] + A[:N-(K-1)]

# 各地点を左端として、長さKの区間の合計を求める
Acum = A.cumsum()
range_sum = Acum[K-1:] - Acum[:N-(K-1)] + A[:N-(K-1)]
best = np.maximum(A,0)
best_cum = best.cumsum()
best_range_sum = best_cum[K-1:] - best_cum[:N-(K-1)] + best[:N-(K-1)]

min_loss = (best_range_sum - np.maximum(range_sum,0)).min()

answer = best.sum() - min_loss
print(answer)
int(input())
s = 180 * (n - 2)

print(s)


### FIXED CODE ###

n = int(input())
s = 180 * (n - 2)
print(s)
a,s,d=map(int,input().split())
l=[]
for i in range(1,min(a,s)+1):
  if a%i==0 and s%i==0:
    l.append(i)
print(l[-2])

### FIXED CODE ###

a,s,d=map(int,input().split())
l=[]
for i in range(1,min(a,s)+1):
  if a%i==0 and s%i==0:
    l.append(i)
print(l[-d])
N = int(input())
H = list(map(int, input().split()))
ans = 0
max = H[0]
for i in range(N-1):
  if H[i] >= max:
    ans += 1
    max = H[i]
print(ans+1)


### FIXED CODE ###

a,b = map(int, input().split())
if a>b:
  ans = 2*a-1
elif a==b:
  ans = 2*a
else:
  ans = 2*b-1
  
print(ans)
import sys

N, M = map(int, input().split())
X = [int(_) for _ in input().split()]

# 座標数よりコマ数が多ければ初期位置で条件を満たす
if N >= M:
    print(0)
    sys.exit()

# ソートする
X.sort()

# 隣り合う数の差を計算する
diff = list()
for m in range(M-1):
    diff.append(X[m+1] - X[m])

total = 0
for n in range(N-1):
    max_index = diff.index(max(diff))
    left = 0
    right = 0
    for l in range(len(diff)):
        if l < max_index:
            left += diff[l]
        elif l > max_index:
            right += diff[l]
    if left == right:
        left_list = diff[:max_index]
        left_max = left_list.index(max(left_list))
        right_list = diff[max_index+1:]
        right_max = right_list.index(max(right_list))
        if left_max > right_max:
            diff = diff[:max_index]
            total += right
        else:
            diff = diff[max_index+1:]
            total += left
    elif left > right:
        diff = diff[:max_index]
        total += right
    else:
        diff = diff[max_index+1:]
        total += left

total += sum(diff)
print(total)

### FIXED CODE ###

import sys

N, M = map(int, input().split())
X = [int(_) for _ in input().split()]

# 座標数よりコマ数が多ければ初期位置で条件を満たす
if N >= M:
    print(0)
    sys.exit()

# ソートする
X.sort()

# 隣り合う数の差を計算する
diff = list()
for m in range(M-1):
    diff.append(X[m+1] - X[m])

diff.sort(reverse=True)
print(sum(diff[N-1:]))
ｖH, W = map(int, input().split())
a = []
for i in range(H):
    s = input()
    if s != '.'*W:
        a.append(s)
ls = []
for i in range(W):
    b = ''
    for j in range(len(a)):
        b += a[j][i]
    if b == '.'*len(a):
        ls.append(i)
ans = []
for i in range(W):
    s = ''
    for j in range(len(a)):
        if i in ls:
            continue
        else:
            s += a[j][i]
    ans.append(s)
print(*ans, sep='\n')

### FIXED CODE ###

H, W = map(int, input().split())
a = []
for i in range(H):
    s = input()
    if s != '.'*W:
        a.append(s)
ls = []
for i in range(W):
    b = ''
    for j in range(len(a)):
        b += a[j][i]
    if b == '.'*len(a):
        ls.append(i)
ans = []
for i in range(len(a)):
    s = ''
    for j in range(W):
        if j in ls:
            continue
        else:
            s += a[i][j]
    ans.append(s)
print(*ans, sep='\n')
s=input()
K=int(input())

ans=[]
ans.append(s)


for i in range(len(s)-1):
 for j in range(i+1):
  cut_s=s[j:j+len(s)-i-1]
  ans.append(cut_s)
  ans=sorted(set(ans))
  if len(ans)>K:
   ans.pop()
  print(ans)
    


answer=ans[K-1]
print(answer)

### FIXED CODE ###

a,b,c,d=map(int,input().split())

if abs(c-a)<=d or (abs(a-b)<=d and abs(b-c)<=d):
 print('Yes')
else:
 print('No')
N, M = map(int, input().split())

group = []

MOD = 1000000007

pre_a = int(input())
group.append(pre_a)

ok = True
for i in range(M-1):
    a = int(input())
    tmp = a - pre_a - 1
    pre_a = a
    if tmp == 0:
        ok = False
    else:
        group.append(tmp)
    if not ok:
        break
group.append(N - pre_a)

if not ok:
    print(0)
elif max(group) == 1:
    print(1)
else:
    fiv = [0 for i in range(max(group))]
    fiv[0] = 1
    fiv[1] = 1
    for i in range(2, len(fiv)):
        fiv[i] = (fiv[i-1] + fiv[i-2]) % MOD
    ans = 1
    for g in group:
        ans *= fiv[g-1]
    print(ans%MOD)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M =map(int, input().split())
    a = [int(input()) for i in range(M)]

    sep = []
    pre = -1
    ok = True
    for t in a:
        tmp = t - pre - 1
        if tmp == 0:
            ok = False
            break
        sep.append(tmp)
        pre = t
    sep.append(N-pre)
    # print(sep)

    if not ok:
        print(0)
        return
    max_sep = max(sep)

    MOD = 1000000007
    fib = [1] * (max_sep)
    for i in range(2, max_sep):
        fib[i] = fib[i-2] + fib[i-1]
        fib[i] %= MOD
    
    ans = 1
    for s in sep:
        ans *= fib[s-1]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
numList = [0]*10**5
sum=0
for i in A:
    numList[i] += 1
    sum+=i

B = [list(map(int,input().split())) for _ in range(Q)]

for i in range(Q):
    dev = B[i][1]-B[i][0]
    sum += numList[B[i][0]]*dev
    numList[B[i][1]] +=numList[B[i][0]]
    numList[B[i][0]] = 0
    print(sum)
    

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [list(map(int,input().split())) for _ in range(Q)]
numList = [0]*(10**5+1)
res=sum(A)
for i in A:
    numList[i] += 1

for i in range(Q):
    dev = B[i][1]-B[i][0]
    res += numList[B[i][0]]*dev
    numList[B[i][1]] +=numList[B[i][0]]
    numList[B[i][0]] = 0
    print(res)
s = input("number of senbei:")
p = input("number of people:")
N = int(s)
K = int(p)

if N % K == 0:
    print(0)
else:
    print(1)

### FIXED CODE ###

N,K = (int(i) for i in input().split())

if N % K == 0:
    print(0)
else:
    print(1)
def main ():
N = int(input())
A = list(map(int,input(). split ()))
if 0 in A:
	print(0)
	return
prod = 1
for a in A:
	prod *= a
if prod > 1000000000000000000:
	print(-1)
	return
print(prod)
main ()

### FIXED CODE ###

def main ():
	N = int(input())
	A = list(map(int,input(). split ()))
    
	if 0 in A:
		print(0)
		return
      
	prod = 1
	for a in A:
		prod *= a
		if prod > 1000000000000000000:
			print(-1)
			return
          
	print(prod)
main ()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.par = [i for i in range(1,n+1)]

    def find(self, x):
        if self.par[x-1] == x:
            return x
        else:
            self.par[x-1] = self.find(self.par[x-1])
            return self.par[x-1]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        else:
            self.par[y-1]=x

    def same(self, x, y):
        return self.find(x)==self.find(y)

N,M,K=map(int,input().split())
U=UnionFind(N)
F=[set() for _ in range(N)]
B=[set() for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  U.union(a,b)
  F[a-1].add(b)
  F[b-1].add(a)
for _ in range(K):
  a,b=map(int,input().split())
  B[a-1].add(b)
  B[b-1].add(a)
G={}
for i in range(1,N+1):
  x = U.find(i)
  if x in G:
    G[x].add(i)
  else:
    G[x]={i}
ans=[0]*N
for g in G.values():
  for i in g:
    ans[i-1]=len(g-F[i-1]-B[i-1])-1
print(*ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1]*n
        self.rank = [0]*n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.rank[x-1] > self.rank[y-1]:
            self.par[x-1] += self.par[y-1]
            self.par[y-1] = x
        else:
            self.par[y-1] += self.par[x-1]
            self.par[x-1] = y
            if self.rank[x-1] == self.rank[y-1]:
                self.rank[y-1] += 1

    def same(self, x, y):
        return self.find(x)==self.find(y)

    def count(self, x):
        return -self.par[self.find(x)-1]

from collections import deque

N,M,K=map(int,input().split())
U=UnionFind(N)
q=deque([])
for _ in range(M):
  a,b=map(int,input().split())
  U.union(a,b)
  deque.append(q,(a,b))
G=[set([]) for _ in range(N)]
for _ in range(M):
  a,b=deque.pop(q)
  if U.same(a,b):
    G[a-1].add(b)
    G[b-1].add(a)
for _ in range(K):
  a,b=map(int,input().split())
  if U.same(a,b):
    G[a-1].add(b)
    G[b-1].add(a)
ans=[0]*N
for i in range(1,N+1):
  ans[i-1]=U.count(i)-len(G[i-1])-1
print(*ans)
N=int(input())
ABC=[]
for i in range(N):
  l=list(map(int,input().split()))
  ABC=ABC+[l]
dp=[[0,0,0]*N]#dp[i][j]はi+1日目にアクティビティjを選んだ時の活動終了時の幸福量
for i in range(3):
  dp[0][i]=ABC[0][i]
for i in range(1,N):
  dp[i][1]=max(dp[i-1][2]+ABC[i][1],dp[i-1][0]+ABC[i][1])
  dp[i][0]=max(dp[i-1][1]+ABC[i][0],dp[i-1][2]+ABC[i][0])
  dp[i][2]=max(dp[i-1][1]+ABC[i][2],dp[i-1][0]+ABC[i][2])
ans=max(dp[N-1])
print(ans)

### FIXED CODE ###

N=int(input())
A=[]
B=[]
C=[]
for i in range(N):
  l1,l2,l3=map(int,input().split())
  A+=[l1]
  B+=[l2]
  C+=[l3]
dp=[[0,0,0] for i in range(N)]#dp[i][j]はi+1日目にアクティビティjを選んだ時の活動終了時の幸福量
dp[0][0]=A[0]
dp[0][1]=B[0]
dp[0][2]=C[0]
for i in range(1,N):
  dp[i][1]=max(dp[i-1][2]+B[i],dp[i-1][0]+B[i])
  dp[i][0]=max(dp[i-1][1]+A[i],dp[i-1][2]+A[i])
  dp[i][2]=max(dp[i-1][1]+C[i],dp[i-1][0]+C[i])
ans=max(dp[N-1])
print(ans)
import bisect
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(m)]
AB = sorted(ab)
for x,y in cd:
    a = bisect.bisect_left(AB, [x,y])
    print(ab.index(AB[a])+1)

### FIXED CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(M)]

for i in range(N):
  d = []
  for j in range(M):
    d.append(abs(ab[i][0] - cd[j][0]) + abs(ab[i][1] - cd[j][1]))
  print(d.index(min(d)) + 1)
import math

a = str(input())
b = str(input())

c = a + b
d = int(c)

print(d)

e = math.sqrt(d)
# e = int(e)

print(e)

if e.is_integer() == True:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

import math

a,b = map(str, input().split())

c = a + b
d = int(c)

e = math.sqrt(d)

if e.is_integer() == True:
  print("Yes")
else:
  print("No")
nums = map(int,input().split())

print(nums[2],nums[0],nums[1])

### FIXED CODE ###

nums = input().split()
print(nums[2],nums[0],nums[1],sep = ' ')
import itertools

n, m = map(int, input().split())
l = itertools.accumulate([1] * 999)
print(l[m-n-1] - m)

### FIXED CODE ###

import itertools

n, m = map(int, input().split())
l = list(itertools.accumulate(range(1, 1000)))
print(l[m-n-1]-m)
def enqueue(x):
    global tail
    Q[tail] = ???
    tail = (tail + 1) % (n + 1)

def dequeue():
    global head
    x,t = Q[head]
    head = (head + 1) % (n + 1)
    return [x,t]
n,q = map(int, input().split())
Q = [0 for i in range(n+1)]
head = 0
tail = 0
for i in range(n):
    P = input().split()
    enqueue([P[0], int(P[1])])

elaps = 0
while head != tail:
    u,t = dequeue()
    c = min(q, t)
    t -= c
    elaps += c
    if t > 0:
        enqueue([u,t])
    else:
        print(u + " " + str(elaps))

### FIXED CODE ###

n,q = map(int, input().split())
MAX = n + 2
Q = [0 for i in range(MAX)]
head = 0
tail = 0

def enqueue(u, t):
    global tail
    Q[tail] = [u, t]
    tail = (tail + 1) % MAX

def dequeue():
    global head
    x,t = Q[head]
    head = (head + 1) %MAX
    return [x,t]
for i in range(n):
    P = list(input().split())
    enqueue(P[0], int(P[1]))

elaps = 0
while head != tail:
    u,t = dequeue()
    c = min(q, t)
    t -= c
    elaps += c
    if t > 0:
        enqueue(u,t)
    else:
        print(u + " " + str(elaps))