Harryxun/stf_run huggingface dataset:
from heapq import heappush, heappop

INF = float("inf")

N, K, *TD = map(int, open(0).read().split())

S = [[] for _ in range(N)]
for t, d in zip(*[iter(TD)] * 2):
    S[t - 1].append(d)

E = []
for s in S:
    if s:
        E.append(sorted(s, reverse=True))
    else:
        E.append([-INF])
E.sort(reverse=True)

cur = 0
Q = []
for i in range(K):
    cur += E[i][0]
    for j in range(1, len(E[i])):
        heappush(Q, -E[i][j])

for i in range(K, N):
    for j in range(len(E[i])):
        heappush(Q, -E[i][j])

res = cur + K * K
for x in range(K, 0, -1):
    v, w = E[x][0], -Q[0]
    if v < w:
        heappop(Q)
        cur += w
        heappush(Q, -v)
        cur -= v

    res = max(res, cur + x * x)

print(res)



### FIXED CODE ###

from heapq import heappush, heappop, heapreplace

INF = 10 ** 9 + 5

N, K, *TD = map(int, open(0).read().split())

E = [[] for _ in range(N)]
for t, d in zip(*[iter(TD)] * 2):
    E[t - 1].append(d)

for e in E:
    if e:
        e.sort(reverse=True)
    else:
        e.append(-INF)
E.sort(key=lambda x: -x[0])

cur = 0
Q = []
for ei in E[:K]:
    cur += ei[0]
    for eij in ei[1:]:
        heappush(Q, -eij)

for ei in E[K:]:
    for eij in ei:
        heappush(Q, -eij)

res = cur + K * K
for x in reversed(range(1, K)):
    v, w = E[x][0], -Q[0]
    if v < w:
        heappop(Q)
        cur += w
        heappush(Q, -v)
        cur -= v

    res = max(res, cur + x * x)

print(res)
N = int(input(N))
A = int(input(A))
print(N * N - A)

### FIXED CODE ###

N = int(input())
A = int(input())
print(N * N - A)
n = int(input())

max_i = int(n / 2) + 1
max_mod = n % max_i

sum = ((n - 1) * n) / 2

if max_mod > max_i:
  sum = (sum - max_i-1) + max_mod

print(int(sum))



### FIXED CODE ###

s = input()
t = input()

cnt = 0

for i in range(3):
  if s[i] == t[i]:
    cnt += 1

print(cnt)
inp = map(int, input().split())
inp = list(inp)
hard = 0
for number in range(0, 2) :
  if inp[number] == inp[number + 1] :
    hard = 1
    
if hard == 0 :
  print ("Good")
else :
  print ("Bad)

### FIXED CODE ###

inp = list(input())
hard = 0
for number in range(0, 3) :
  if inp[number] == inp[number + 1] :
    hard = 1
    
if hard == 0 :
  print("Good")
else :
  print("Bad")
l=map(int,input())
print((l/3)**3)

### FIXED CODE ###

l=int(input())
print((l/3)**3)
n = input()
max = 0
min = 0
sum = 0
a=[int(x) for x in input().split()]
for i in range(1,n+1):
    if a[i] >= max: max = a[i]
    if a[i] <= min: min = a[i]
    sum += a[i]

print(min,max,sum)



### FIXED CODE ###

n = int(input())
a = sorted([int(x) for x in input().split()])
print(a[0],a[-1],sum(a))
A, B, C, K = list(map(int, input()))

if (A <= K):
    print(K)
elif (A + B <= K):
    print(A)
else:
    print(A+(-1)*(K-A-B))

### FIXED CODE ###

A, B, C, K = list(map(int, input().split()))

if (A >= K):
    print(K * 1)
elif (A + B >= K):
    print(A)
else:
    print(A+(-1)*(K-A-B))
a, s = open(0).read().split()
if a >= 3200:
  print('red')
else:
  print(a)


### FIXED CODE ###

a, s = open(0).read().split()
if int(a) >= 3200:
  print(s)
else:
  print('red')
inp = int(input())
aaa =0
bbb =0
nega = 0

if 0 <= inp and inp <= 10**9:
  if 500 <= inp:
    big = int(inp / 500)
    
    sma = inp-(big *500)
    if 5 <= sma:
      nega = int(sma / 5)
      
  aaa = 1000*big
  bbb = 5*nega
  print(aaa + bbb)
      

### FIXED CODE ###

inp = input()
inp = int(float(inp))
aaa = 0
bbb = 0
yyy = 0

if 0 < inp and inp <= 10**9:
  if 500 <= inp:
    big = inp // 500
    aaa = big * 1000
    amari = inp % 500
    if 5 <= amari:
      smo = amari //5
      bbb = smo *5
    print(aaa+bbb)
  elif 5 <= inp:
    hhh = inp // 5
    yyy = hhh * 5
    print(yyy)
else:
  print(0)
import math
A=list(map(int,input().split()))
print(math.ceil(A[1]/A[0]))


### FIXED CODE ###

S=list(input())
T=list(input())
if S[0]==T[0] and S[1]==T[1] and S[2]==T[2]:
  print(3)
elif S[0]==T[0] and S[1]!=T[1] and S[2]!=T[2]:
  print(1)
elif S[0]!=T[0] and S[1]==T[1] and S[2]!=T[2]:
  print(1)
elif S[0]!=T[0] and S[1]!=T[1] and S[2]==T[2]:
  print(1)
elif S[0]!=T[0] and S[1]!=T[1] and S[2]!=T[2]:
  print(0)
else:
  print(2)
if int(input())==1:
	print("Hello World")
else:
  	a = int(input())
    B = int(input())
    print(a+b)

### FIXED CODE ###

if int(input())==1:
    print("Hello World")
else:
    a = int(input())
    b = int(input())
    print(a+b)
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
sousa = sorted([[int(i) for i in input().split()] for i in range(M)],
               reverse=True, key=lambda x:x[1])
print(sousa)
for cnt, v in sousa:
    for i in range(cnt):
        if min(A) < v:
            A[A.index(min(A))] = v
        else:
            return(sum(A))
return(sum(A))

### FIXED CODE ###

def check():
    N, M = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    sousa = sorted([[int(i) for i in input().split()] for i in range(M)],
                   reverse=True, key=lambda x:x[1])
    index = 0
    for cnt, value in sousa:
        for i in range(cnt):
            if index == N:
                break
            if A[index] < value:
                A[index] = value
            else:
                return(sum(A))
            index += 1
    return(sum(A))
print(check())
# -*- coding: utf-8 -*-

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

ans = ((B-A/2)+A)
if isinstance(int, ans):
    print(ans)
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

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

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

ans = (((B-A)/2)+A)
if ans.is_integer():
    print(int(ans))
else:
    print("IMPOSSIBLE")
ans=''
for i in range

### FIXED CODE ###

ans=''
for i in range(3):
  s=input()
  ans+=s[i]
  
print(ans)
s = input()
if s="ABC":
    print("ARC")
else:
    print("ABC")

### FIXED CODE ###

s = input()
if s=="ABC":
    print("ARC")
else:
    print("ABC")
a, b = map(int, input().split())
if a == b :
    print('H')
else :
    print('T')

### FIXED CODE ###

a, b = input().split()
if a == b :
    print('H')
else :
    print('D')
if __name__ == "__main__":
  str_N_K = input()
  
  list_N_K = str_N_K.split(' ')
  N = int(list_N_K[0])
  K = int(list_N_K[1])
  
  list_person = [0] * N
  
  for i in range(K):
    d = int(input())
    str_persons = input()
    if (" " in str_persons):
      list_str_persons = list_str_persons.split(" ")
    else:
      list_str_persons = list_str_persons
      
    for str_person in list_str_persons:
      int_person = int(str_person)
      list_person[int_person] += 1
  
  output = 0
  for person in list_person:
    if person == 0:
      output += 1
      
  print(output)
    
  
  


### FIXED CODE ###

if __name__ == "__main__":
  str_N_K = input()
  
  list_N_K = str_N_K.split(' ')
  N = int(list_N_K[0])
  K = int(list_N_K[1])
  
  list_person = [0] * N
  
  for _ in range(K):
    d = int(input())
    str_persons = input()
    if (" " in str_persons):
      list_str_persons = str_persons.split(" ")
    else:
      list_str_persons = [str_persons]
      
    for str_person in list_str_persons:
      int_person = int(str_person)
      list_person[int_person-1] += 1
  
  output = 0
  for person in list_person:
    if person == 0:
      output += 1
      
  print(output)
import math
def prodR(s,a,c,N):
    R=[s]
    for i in range(1,N+1):
        R.append((a*R[i-1]+c)%256)
    return R[1:]

def entropy(R,I,N):
    O=[(I[i]+R[i])%256 for i in range(N)]
    L=[0]*256
    for i in O:
        L[i]+=1
    H=-sum(float(L[i])/N*math.log(float(L[i])/N,2) for i in range(256) if L[i]!\
=0)
    return H

while True:
    N=input()
    if N==0:break
    I=map(int,raw_input().split())
    maxInt=1e10
    for s in range(16):
        for a in range(16):
            for c in range(16):
                R=prodR(s,a,c,N)
                H=entropy(R,I,N)
                if maxInt>H:
                    maxInt=H
                    ans=s,a,c
    print "%d %d %d"%(ans[0],ans[1],ans[2])

### FIXED CODE ###

import math
def prodR(s,a,c,N):
    R=[s]
    for i in range(1,N+1):
        R.append((a*R[i-1]+c)%256)
    return R[1:]

def entropy(R,I,N):
    O=[(I[i]+R[i])%256 for i in range(N)]
    L=[0]*256
    for i in O:
        L[i]+=1
    H=-sum(float(L[i])/N*math.log(float(L[i])/N,2) for i in range(256) if L[i]!=0)
    return H

while True:
    N=input()
    if N==0:break
    I=map(int,raw_input().split())
    maxInt=1e10
    for s in range(16):
        for a in range(16):
            for c in range(16):
                R=prodR(s,a,c,N)
                H=entropy(R,I,N)
                if maxInt>H:
                    maxInt=H
                    ans=s,a,c
    print "%d %d %d"%(ans[0],ans[1],ans[2])
import bisect
import sys

def main():
  input = sys.stdin.readline
  A, B, Q = map(int, input().split())
  INF = 10**18
  S = [-INF] + [int(input()) for _ in range(A)] + [INF]
  T = [-INF] + [int(inout()) for _ in range(B)] + [INF]
  
  for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for s in [S[b-1], S[b]]:
      for t in [T[d-1], T[d]]:
        d1, d2 = abs(s-x) + abs(t-s), abs(t-x) + abs(s-t)
        res = min(res, d1, d2)
  print(res)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import bisect
import sys

def main():
  input = sys.stdin.readline
  A, B, Q = map(int, input().split())
  INF = 10**18
  S = [-INF] + [int(input()) for _ in range(A)] + [INF]
  T = [-INF] + [int(input()) for _ in range(B)] + [INF]
  
  for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(S, x), bisect.bisect_right(T, x)
    res = INF
    for s in [S[b-1], S[b]]:
      for t in [T[d-1], T[d]]:
        d1, d2 = abs(s-x) + abs(t-s), abs(t-x) + abs(s-t)
        res = min(res, d1, d2)
    print(res)


if __name__ == '__main__':
  main()
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = deque()
que.append((0, 0))
dist[0][0] = 0

while len(que) > 0:
  y, x = que.popleft()
  if y == H - 1 and x == W - 1:
    break
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.append((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

### FIXED CODE ###

from collections import deque

R,C = list(map(int,input().split()))
Sx,Sy = 0,0
Gx,Gy = R-1,C-1
Mize = [input() for _ in range(R)]
dd = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def bfs():
    d = [[float('inf')] * C for i in range(R)]
    q = deque([])
    d[Sx][Sy] = 0
    q.append((Sx,Sy))
    while(len(q) != 0):
        x,y = q.popleft()
        if x == Gx and y == Gy:
            break
        for dx,dy in dd:
            
            if -1<x+dx<R and -1<y+dy<C and Mize[x+dx][y+dy]=='.' and d[x+dx][y+dy] == float('inf'):
                q.append([x+dx,y+dy])
                d[x+dx][y+dy] = d[x][y] + 1
    return d[Gx][Gy]

white = sum([m.count('#') for m in Mize])
need = bfs()
if need == float('inf'):
    print(-1)
else:
    print(R*C-white-need-1)
N, K = map(int, input().split())
A = input().split()
count = 0
if N = K:
    print(1)
else:
    count += 1
    rem = N-K
    add = 1 if (N-K)%(K-1) else 0
    count += (N-K)//(K-1) + add
    print(count)

### FIXED CODE ###

N, K = map(int, input().split())
A = input().split()
count = 0
if N == K:
    print(1)
else:
    count += 1
    rem = N-K
    add = 1 if (N-K)%(K-1) else 0
    count += (N-K)//(K-1) + add
    print(count)
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for i in range(M)]
s = [sc[i][0] for i in range(M)]
c = [sc[j][1] for j in range(M)]
box = [0] * M
ans = str()
for m in range(M):
    box[s[m] - 1] = c[m]

for k in box:
    ans += str(k)

if box[0] != 0:
    print(int(ans))
else:
    print(-1)

### FIXED CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

import sys

N, M = MI()
ans = ""
num = [[] for _ in range(N)]

for _ in range(M):
    s, c = MI()
    num[s - 1].append(str(c))

    if (N != 1 and (s, c) == (1, 0)) or len(set(num[s - 1])) != 1:
        print(-1)
        sys.exit()

if num[0] == []:
    ans += str(int(N != 1))
else:
    ans += num[0][0]

for n in num[1:]:
    if n == []:
        ans += "0"
        continue
        
    ans += n[0]

print(ans)
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in xrange(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,rawinput().strip().split())
ices = []
while True:
    ice = int(rawinput().strip())
    ices.append(ice)
    if len(ices) == N:
        break

orderN(N,L,ices)

### FIXED CODE ###

def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    append = peaks.append
    for i in xrange(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            append(upPeak)
            append(downPeak)
    print(max(peaks))

N,L = map(int,raw_input().strip().split())
ices = [int(raw_input().strip()) for _ in xrange(N)]

orderN(N,L,ices)
i=1;count=1
while 1:
    i=input()
    if i==0:break

    print("Case {0}: {1}".format(count,i))
    count+=1

### FIXED CODE ###

i=1;count=1
while 1:
    i=input()
    i=int(i)
    if i==0:
        break
    print("Case {0}: {1}".format(count,i))
    count+=1
n = int(input())
a = [int(input()) for i in range(n)]
print(min(a),max(a),sum(a))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
print(min(a),max(a),sum(a))
n,l=map(int,input().split())
s=sorted([input() for i in range(n)])
print(*n,sep="")

### FIXED CODE ###

n,l=map(int,input().split())
s=sorted([input() for i in range(n)])
print(*s,sep="")
A, B = map( int, inpuot().split() )
if A < 10 and B < 10 :
   print( A * B )
else : 
   print( -1 )  

### FIXED CODE ###

A, B = map( int, input().split() )
if A < 10 and B < 10 :
   print( A * B )
else : 
   print( -1 )
n = int(input())
t, a = map(float, input().split())
h = list(map(float, input().split()))
import numpy as np
for i in range(n):
  h[i] = abs( a - (t - h[i] * 0.006))
print(np.armmin(h) + 1)

### FIXED CODE ###

n = int(input())
t, a = map(float, input().split())
h = list(map(float, input().split()))
import numpy as np
for i in range(n):
  h[i] = abs( a - (t - h[i] * 0.006))
print(np.argmin(h) + 1)
N = int(input())
A = list(map(int, input().split())) 

result = 1
if 0 in A:
    result = 0
else:
    for i in A:
    result *= i
    if result > 10**18:
        result = -1
        break

print(result)


### FIXED CODE ###

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

result = 1
A.sort()
for i in A:
    result *= i
    if result > 10**18:
        result = -1
        break

print(result)
while True:
    (n, x) = [int(i) for i in input().split()]
    count = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            for k in range(j + 1, n + 1):
                if x - (i + j + k) == 0:
                    count += 1
                if x - (i + j + k) < 0:
                    break
    print(count)

### FIXED CODE ###

while True:
    (n, x) = [int(i) for i in input().split()]
    if n == x == 0:
        break
    count = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            for k in range(j + 1, n + 1):
                if x - (i + j + k) == 0:
                    count += 1
                if x - (i + j + k) < 0:
                    break
    print(count)
from collections import Counter
n = int(input())
V = list(map(int,input().split()))
V_odd = V[::2]
V_eve = V[1::2]
odd_max = Counter(V_odd).most_common(1)
even_max = Counter(V_eve).most_common(1)

result = n - odd_max[0][1] - even_max[0][1]
if odd_max[0][0] == even_max[0][0]:
    odd_least,even_least = 0,0
    if Counter(V_odd).most_common(1) != Counter(V_odd).most_common(2):
        odd_least = (Counter(V_odd).most_common(2))[0][1]
    if Counter(V_eve).most_common(1) != Counter(V_eve).most_common(2):
        even_least = (Counter(V_eve).most_common(2))[0][1]
    if Counter(V_odd).most_common(1) == Counter(V_odd).most_common(2) and Counter(V_eve).most_common(1) == Counter(V_eve).most_common(2):
        result = int(n/2)
    else:
        result = min(n - odd_least - even_max,n - even_least - odd_max)


print(result)

### FIXED CODE ###

from collections import Counter
n = int(input())
V = list(map(int,input().split()))
V_odd = V[::2]
V_eve = V[1::2]
odd_max = Counter(V_odd).most_common(1)
even_max = Counter(V_eve).most_common(1)

result = n - odd_max[0][1] - even_max[0][1]
if odd_max[0][0] == even_max[0][0]:
    odd_least,even_least = 0,0
    if Counter(V_odd).most_common(1) != Counter(V_odd).most_common(2):
        odd_least = (Counter(V_odd).most_common(2))[1][1]
    if Counter(V_eve).most_common(1) != Counter(V_eve).most_common(2):
        even_least = (Counter(V_eve).most_common(2))[1][1]
    if Counter(V_odd).most_common(1) == Counter(V_odd).most_common(2) and Counter(V_eve).most_common(1) == Counter(V_eve).most_common(2):
        result = int(n/2)
    else:
        result = min(n - odd_least - even_max[0][1],n - even_least - odd_max[0][1])

print(result)
n = int(input())
a = list(map(int,input().split()))
a1 = []
a2 = []
for i in range(n):
    if i % 2 == 0:
        a1.append(a[i])
    else:
        a2.append(a[i])
if n % 2 == 0:
    rev = reversed(a2)
    print(*rev, *a1)
else:
    rev = reversed(a1)
    print(*rev, *a2)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a1 = []
a2 = []
for i in range(n):
    if i % 2 == 0:
        a1.append(a[i])
    else:
        a2.append(a[i])
if n % 2 == 0:
    a2.reverse()
    print(*a2+a1)
else:
    a1.reverse()
    print(*a1+a2)
a, b, c, d, e, f = map(int, input().split())
x = []
y = []
t = 100 * e / (100 + e)
for i in range(f // (100 * a) + 1):
    bb = f - 100 * a * i
    for j in range(bb // (100 * b) + 1):
        if 100 * (a * i + b * j) in x:
            continue
        else:
            x.append(100 * (a * i + b * j))
for i in range(f // c + 1):
    dd = f - c * i
    for j in range(dd // d + 1):
        if c * i + d * j in y:
            continue
        else:
            y.append(c * i + d * j)
y.sort()
rr = 0
ans = []
for i, xi in enumerate(x):
    for j, yi in enumerate(y):
        if xi + yi == 0:
            continue
        r = 100 * yi / (xi + yi)
        if r > t:
            break
        elif xi + yi <= f and rr < r:
            ans = [xi + yi, yi]
            rr = r
print(ans[0], ans[1])

### FIXED CODE ###

a, b, c, d, e, f = map(int, input().split())
x = []
y = []
t = 100 * e / (100 + e)
for i in range(f // (100 * a) + 1):
    bb = f - 100 * a * i
    for j in range(bb // (100 * b) + 1):
        if 100 * (a * i + b * j) in x:
            continue
        else:
            x.append(100 * (a * i + b * j))
for i in range(f // c + 1):
    dd = f - c * i
    for j in range(dd // d + 1):
        if c * i + d * j in y:
            continue
        else:
            y.append(c * i + d * j)
y.sort()
rr = 0
ans = []
for i, xi in enumerate(x):
    for j, yi in enumerate(y):
        if xi + yi == 0:
            continue
        r = 100 * yi / (xi + yi)
        if r > t:
            break
        elif xi + yi <= f and rr <= r:
            ans = [xi + yi, yi]
            rr = r
print(ans[0], ans[1])
a=int(input())
b=input()

count=0
for i in range(a-2):
  if b[i]=='A'and b[i+1]=='B' and b[i+2]=='C':
    count+=1
print(count)


### FIXED CODE ###

a,b=map(int,input().split())
if 500*a>=b:
  print('Yes')
else:
  print('No')
6 9
3 4
6 1
2 4
5 3
4 6
1 5
6 2
4 5
5 6

### FIXED CODE ###

from collections import deque

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

d = {}

for i in range(N):
    d[i+1] = set()

for i in range(M):
    a, b = map(int,input().split())
    d[a].add(b)
    d[b].add(a)

que = deque([1])
checked = set()
ans = {1:-1}

while que:
    now = que.popleft()
    for h in d[now]:
        if not h in ans:
            ans[h] = now
            que.append(h)
    if len(ans) == N:
        break
    
if len(ans) == N:
    print('Yes')
    for i in range(N-1):
        print(ans[i+2]) 
else:
    print('No')
import numpy as np
S = input()
INF = 10**9+7
dp = np.array([0,0,0], dtype=np.int64)
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N%INF
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    dp[1:] = dp[1:]*3+dp[:-1]
    dp[0] = dp[0]*3+N
    dp %= INF
    N *= 3
print(dp[2])

### FIXED CODE ###

S = input()
INF = 10**9+7
dp = [0,0,0]
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N = (3*N)%INF
print(dp[2]%INF)
s = input()
w = input()

if int(s) > int(w):
  print('safe')
else:
  print('unsafe')

### FIXED CODE ###

arg = input()
s = (arg.split())[0]
w = (arg.split())[1]


if int(s) > int(w):
  print('safe')
else:
  print('unsafe')
n, m, x = map(int,input().split())
a = list(map(int,input().split()))
ans1 = 0
ans2 = 0
for i in range(x):
    if a[0] == i:
        ans1 += 1
        a.pop(0)
for i in range(x, n):
    if a[0] == i:
        ans2 += 1
        a.pop(0)
ans = min(ans1,ans2)
print(ans)

### FIXED CODE ###

n, m, x = map(int,input().split())
a = list(map(int,input().split()))
ans1 = 0
ans2 = 0
if x == 1 or x == n:
    print(0)
else:
    for i in range(1, x):
        if len(a) != 0:
            if a[0] == i:
                ans1 += 1
                a.pop(0)
    if len(a) != 0:
        for i in range(x, n):
            if len(a) != 0:
                if a[0] == i:
                    ans2 += 1
                    a.pop(0)
    ans = min(ans1, ans2)
    print(ans)
from math import floor as f
a, b = map(int, input().split())
print(f(a * b))

### FIXED CODE ###

from math import floor as f
a = input().split()
a[0] = int(a[0])
a[1] = int("".join(a[1].split(".")))

print(a[0] * a[1] // 100)
n, gap = int(input()), []
data = list(map(int, [input() for i in range(n)]))
cnt, g = 0, n
while g >= 1:
    g //= 2
    gap.append(g)
m = len(gap)
for i in range(m):
    for idx in range(gap[i], n):
        j = idx - gap[i]
        while j >= 0 and data[j] > data[j+gap[i]]:
            data[j+gap[i]], data[j] = data[j], data[j+gap[i]]
            j -= gap[i]
            cnt += 1
print(m)
print(" ".join(map(str, gap)))
print(cnt)
for i in range(n):
    print(data[i])



### FIXED CODE ###

import sys

def shellSort(data, cnt, g, n):
    for idx in range(g, n):
        j = idx - g
        v = data[idx]
        while j >= 0 and data[j] > v:
            data[j+g] = data[j]
            j -= g
            cnt += 1
        data[j+g] = v
    return data, cnt

n, gap = int(input()), []
a = ([int(i) for i in sys.stdin.readlines()], 0)
g = 0
while g <= n//9:
    g = 3 * g + 1
    gap.append(g)
m = len(gap)
for i in gap[::-1]:
    a = shellSort(a[0], a[1], i, n)
print(m)
print(" ".join(map(str, gap[::-1])))
print(a[1])
for i in range(n):
    print(a[0][i])
x,y = map(int,input().split())
ans = 0

if x == 1 and y == 1:
    ans += 400000
    
li = [0,300000, 200000, 100000]

ans += li[x]
ans += li[y]

print(ans)

### FIXED CODE ###

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

if x == 1 and y == 1:
    ans += 400000
    
li = [0,300000, 200000, 100000]

if x <= 3:
    ans += li[x]
if y <= 3:
    ans += li[y]

print(ans)