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

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 9)

def main():
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = {}
  shown = set()

  for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # parents[b] = a
    # childrens[a].add(b)
    relations.setdefault(a, [])
    relations.setdefault(b, [])
    relations[a].append(b)
    relations[b].append(a)

  def f(parent, relations, parents, childrens):
    shown.add(parent)
    for c in relations[parent]:
      if c not in shown:
        parents[c] = parent
        childrens[parent].add(c)
        f(c, relations, parents, childrens)

  f(0, relations, parents, childrens)
  points = {}
  result = [0] * N

  for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    points.setdefault(p, 0)
    points[p] += x

  def solve(idx, parents, childrens, points, result):
    # print(idx)
    if idx in points:
      result[idx] += points[idx]
    if parents[idx] is not None:
      result[idx] += result[parents[idx]]
    for child in childrens[idx]:
      solve(child, parents, childrens, points, result)
      
  solve(0, parents, childrens, points, result)
  print(*result)

if __name__ == "__main__":
  main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)

def main():
  input = sys.stdin.buffer.readline
  read = sys.stdin.buffer.read
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())
  ABPX = list(map(int, read().split()))
  AB = iter(ABPX[:N+N-2])
  PX = iter(ABPX[N+N-2:])

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = [[] for _ in range(N)]
  shown = set()

  for a, b in zip(AB, AB):
    a -= 1
    b -= 1
    relations[a].append(b)
    relations[b].append(a)

  points = [0] * N
  result = [0] * N

  for p, x in zip(PX, PX):
    p -= 1
    points[p] += x

  def solve(parent, relations, points, result):
    result[parent] += points[parent]
    shown.add(parent)
    for child in relations[parent]:
      if child not in shown:
        result[child] += result[parent]
        solve(child, relations, points, result)
      
  solve(0, relations, points, result)
  print(*result)

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

N, Q = map(int, input().split())
s = str(input())

t = []
d = []

for _ in range(Q):
    ti, di = map(str, input().split())
    t.append(ti)
    d.append(di)


def main_fanc(s, t, d, N):
    masu = []
    for si in s:
        masu.append({'key': si, 'val': 1})
        
    for ti, di in zip(t, d):
        if di == 'L':
            for i, m in enumerate(masu):
                if m['key'] != ti:
                    continue
                if i == 0:
                    masu[i]['val'] = 0
                else:
                    masu[i - 1]['val'] += masu[i]['val']
                    masu[i]['val'] = 0
                    
        if di == 'R':
            masu.reverse()
            for i, m in enumerate(masu):
                if m['key'] != ti:
                    continue
                if i == 0:
                    masu[i]['val'] = 0
                else:
                    masu[i - 1]['val'] += masu[i]['val']
                    masu[i]['val'] = 0
            masu.reverse()
    
    c = 0
    for m in masu:
        c += m['val']
    
    print(c)
                
main_fanc(s, t, d, N)

### FIXED CODE ###

N, Q = map(int, input().split())
s = str(input())

t = []
d = []

for _ in range(Q):
    ti, di = input().split()
    t.append(ti)
    d.append(di)
    
LEFT_DIE = -1
RIGHT_DIE = N

def is_dead(i):
    for ti, di in zip(t, d):
        if s[i] == ti:
            if di == 'L':
                i -= 1
            if di == 'R':
                i += 1
            if i == LEFT_DIE:
                return LEFT_DIE
            if i == RIGHT_DIE:
                return RIGHT_DIE
    return 0

low = -1
high = N;
# LEFT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == LEFT_DIE:
        low = mid
    else:
        high = mid
left_edge = high

low = -1
high = N;
# RIGHT
while high - low > 1:
    mid = (low + high) // 2;
    if is_dead(mid) == RIGHT_DIE:
        high = mid
    else:
        low = mid
right_edge = low

#print(left_edge, right_edge)
ans_s = s[left_edge:right_edge+1]
#print(ans_s)
ans = len(ans_s)
print(ans)
### BUGGY CODE ###

# coding: utf-8
def get_ln_inputs():
    return input().split()


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def main():
    n = get_ln_int_inputs()[0]
    a = get_ln_int_inputs()
    reverse = n % 2 == 0

    result = list()
    for i in range(n):
        ii = len(result) if i % 2 == 1 else 0
        result.insert(ii, a[i])
    
    if reverse:
        result = result[::-1]

    print(" ".join(str(x) for x in result))


main()

### FIXED CODE ###

# coding: utf-8
def get_ln_inputs():
    return input().split()


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def main():
    n = get_ln_int_inputs()[0]
    a = get_ln_int_inputs()

    ilist = []

    t = n
    while t > 0:
        ilist.append(t)
        t -= 2
    if t == -1:
        t = 2
    else:
        t = 1
    while t < n:
        ilist.append(t)
        t += 2
    
    print(" ".join(str(a[i - 1]) for i in ilist))


main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int(): return int(input())

def map_int_input(): return map(int, input())

MII = map_int_input

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

def MII_to_index(): return map(to_index, input())

def MII_split_to_index(): return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs(): return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number): return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number): return [LII_split() for _ in range(rows_number)]

import math
A, B, N = MII_split()

ma = 0
for x in range(N+1):
    tmp = math.floor(A*x/B)- A*math.floor(x/B)
    if tmp > ma:
        ma = tmp
print(ma)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

import math

A, B, N = MII_split()

def f(x):
    return math.floor(A * x / B) - A * math.floor(x / B)

# max = 0
# for x in range(min(B + 1, N + 1)):
#     if x > N:
#         break
#     fx = f(x)
#     # print(fx)
#     if fx > max:
#         max = fx
print(f(min(B-1, N)))
### BUGGY CODE ###

n = int(input())
s = list(input())

cnt = []
for i in range(n):
    cnt.append(0)
    for j in range(i):
        if s[j] == 'W':
            cnt[i] += 1
    for j in range(i+1, n):
        if s[j] == 'E':
            cnt[i] += 1
print(min(cnt))

### FIXED CODE ###

n = int(input())
s = list(input())

l = [0]
r = [0]
l_cnt = 0
r_cnt = 0
for i in range(n-1):
    if s[i] == 'W':
        l_cnt += 1
    if s[n-i-1] == 'E':
        r_cnt += 1
    l.append(l_cnt)
    r.append(r_cnt)
print(min(l[i]+r[n-i-1] for i in range(n)))
### BUGGY CODE ###

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

cost = [0 for _ in range(N)]
K = min(N, K)
for i in range(1,K):
    cost[i] = abs(h[0] - h[i])
    
for i in range(1,N):
    t = max(0, i - K)
    for j in range(t,i):
        if j == t:
            cost[i] = cost[j] + abs(h[i] - h[j])
        else:
            cost[i] = min(cost[i], cost[j] + abs(h[i] - h[j])) 
    
print(cost[-1])

### FIXED CODE ###

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

cost = [0 for _ in range(N)]
K = min(N, K)
for i in range(1,K):
    cost[i] = abs(h[0] - h[i])
    
for i in range(1,N):
    t = max(0, i - K)
    for j in range(t,i):
        if j == t:
            cost[i] = cost[j] + abs(h[i] - h[j])
        else:
            cost[i] = min(cost[i], cost[j] + abs(h[i] - h[j])) 
    
print(cost[-1])
### BUGGY CODE ###

n,k = map(int,input().split())
p = [i-1 for i in list(map(int,input().split()))]
c = list(map(int,input().split()))
ans = -float("inf")
for i in range(n):
    now = i
    cnt = [0]
    for j in range(n):
        nxt = p[now]
        cnt.append(cnt[j]+c[nxt])
        now = nxt
        if now == i:
            break
    m = len(cnt)-1
    if k <= m:
        s = max(cnt[1:(k+1)])
    elif cnt[-1] < 0:
        s = max(cnt[1:])
    else:
        t = k//m
        s = (t-1)*cnt[-1]+max(cnt[1:])
        s = max(s, t*cnt[-1]+max(cnt[:(k-t*m+1)]))
    ans = max(ans,s)
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
p = [i-1 for i in list(map(int,input().split()))]
c = list(map(int,input().split()))
ans = -float("inf")
for i in range(n):
    now = i
    cnt = [0]
    for j in range(n):
        nxt = p[now]
        cnt.append(cnt[j]+c[nxt])
        now = nxt
        if now == i:
            break
    m = len(cnt)-1
    if k <= m:
        s = max(cnt[1:(k+1)])
    elif cnt[-1] < 0:
        s = max(cnt[1:])
    else:
        t = k//m
        s = (t-1)*cnt[-1]+max(cnt[1:])
        s = max(s, t*cnt[-1]+max(cnt[:(k-t*m+1)]))
    ans = max(ans,s)
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(input())

a_dict = {i:0 for i in set(a)}
for i in a:
    for j in a_dict:
        if i == j:
            a_dict[j] += 1

ans = []
for key, value in a_dict.items():
    if value == max(a_dict.values()):
        ans.append(key)
ans.sort()
for i in ans:
  print(i)

### FIXED CODE ###

n = int(input())

# 入力データ受取り時に、辞書に追加していくやり方
s_dict = {}
for i in range(n):
    s = input()    
    if s not in s_dict:
        s_dict[s] = 1
    s_dict[s] += 1

max_value = max(s_dict.values())
ans = []
for key, value in s_dict.items():
    if value == max_value:
        ans.append(key)

ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.friend = [[] for _ in range(n)]
        self.bad = [[] for _ in range(n)]
        
    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

n, m, k = map(int, input().split())
U = UnionFind(n)

for _ in range(m):
    a, b = map(int, input().split())
    U.union(a - 1, b - 1)
    U.friend[a - 1].append(b - 1)
    U.friend[b - 1].append(a - 1)

for _ in range(k):
    c, d = map(int, input().split())
    U.bad[c - 1].append(d - 1)
    U.bad[d - 1].append(c - 1)

ans_list = []
for i in range(n):
    ans = len(U.friend[i]) * (-1)
    for j in range(n):
        if i != j:
            if U.same_check(i, j):
                if j not in U.bad[i]:
                    ans += 1 
    ans_list.append(str(ans))

print(' '.join(ans_list))

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [-1]*n
        
    def find(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] = self.par[y] + self.par[x]
        self.par[y] = x

    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return self.par[self.find(x)]
    
    

n, m, k = map(int, input().split())
U = UnionFind(n)
fl = [0] * n
bl = [0] * n

for _ in range(m):
    a, b = map(int, input().split())
    U.union(a - 1, b - 1)
    fl[a - 1] += 1
    fl[b - 1] += 1

for _ in range(k):
    c, d = map(int, input().split())
    if U.same_check(c - 1, d - 1):
        bl[c - 1] += 1
        bl[d - 1] += 1

ans_list = []
for i in range(n):
    ans = -U.size(i) - fl[i] - bl[i] - 1
    ans_list.append(ans)
print(*ans_list)
### BUGGY CODE ###

input()
vals = map(int, input().split())
count = 0
is_odd = False
while True:
    for val in vals:
        if val % 2 == 1:
            is_odd = True
    if is_odd:
        break
    vals = map(lambda x: x/2, vals)
    count += 1
print (count)

### FIXED CODE ###

N = int(input())
vals = list(map(int, input().split()))
count = 0
is_odd = False
while True:
    for i in range(0, N):
        if vals[i] % 2 == 1:
            is_odd = True
        vals[i] /= 2
    if is_odd:
        break
    count += 1
print (count)
### BUGGY CODE ###

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

C=[input().split() for i in range(N)]

k=0
l=0#何番目の店
m=0#その店で買う数
money=0
X=0#持ち数

while M>X:
    Min=int(C[0][0])
    for i in C:#どの店で買うか
        if Min>=int(i[0]):
            Min=int(i[0])
            l=k
        k+=1

    for x in range(int(C[l][1])):#何個かえるか

        m+=1
        if M==X+m:#max
            money+=m*Min
            print(money)
            break


    money+=m*Min
    X+=m

    C.pop(l)#取り出す
    #リセット
    k=0
    l=0
    m=0#その店で買う数


### FIXED CODE ###

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

C=[input().split() for i in range(N)]
B=[]
for i in C:
    B.append(list(map(int,i)))

B.sort()

k=0
l=0#何番目の店
m=0#その店で買う数
money=0
X=0#持ち数
for a,b in B:
    if(M<=0):
        break
    if(b<=M):
        money+=a*b
    else:
        money+=M*a
    M-=b
print(money)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
  
n = int(input())
a = list(map(int,input().split()))
 
from fractions import gcd
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
 
ans=0
for i in a:
    ans+=lcm//i
 
print(ans%(10**9+7))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
from fractions import gcd
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
 
ans=0
for i in range(n):
    ans+=lcm//a[i]
 
print(ans%(10**9+7))
### BUGGY CODE ###

import fractions
import sys

input = sys.stdin.readline


def factorization(n):
    primes = []
    while n % 2 == 0:
        n //= 2
        primes.append(2)
    for i in range(3, n + 1, 2):
        while n % i == 0:
            n //= i
            primes.append(i)
        if n == 1:
            break
    return primes


def main():
    a, b = list(map(int, input().split()))

    # 素因数分解
    g = fractions.gcd(a, b)
    print(len(set(factorization(g))) + 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions
import sys

input = sys.stdin.readline


def factorization(n):
    primes = []
    while n % 2 == 0:
        primes.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            primes.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        primes.append(n)
    return primes


def main():
    a, b = list(map(int, input().split()))

    # 素因数分解
    g = fractions.gcd(a, b)
    print(len(set(factorization(g))) + 1)


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

a=list(map(int,input().split()))
k=0
for i in range(a[0],a[1]+1):
  if i/a[2]!=i//a[2]:
    if i/a[3]!=i//a[3]:
      k+=1
  else:
    k+=0
print(k)


### FIXED CODE ###

import math,fractions
a=list(map(int,input().split()))
A=a[1]-a[0]+1
B=(a[1]//a[2])-(a[0]-1)//a[2]
C=(a[1]//a[3])-(a[0]-1)//a[3]
d=(a[2]*a[3])//(fractions.gcd(a[2],a[3]))
D=(a[1]//d)-((a[0]-1)//d)
print(int(A-B-C+D))
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    A,B=map(int, input().split())
    gcd_ab = gcd(A,B)
    ans={1}
    i = 2
    while (A>=i and B>=i) and (i <= gcd_ab):
        if A % i == 0 and B % i == 0:
            ans.add(i)
            A //= i
            B //= i
            gcd_ab = gcd(A,B)
        else:
            i += 1
    print(len(ans))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    A,B=map(int, input().split())
    ans = factorization(gcd(A,B))
    if ans[0][0] == 1:
        print(1)
    else:
        print(len(ans)+1)

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

import numpy as np

#  入力
n, w = map(int, input().split())
wvList = []
for i in range(n):
    wvList.append(list(map(int, input().split())))
wv = np.array(wvList)

#  考えるDPテーブルは
#  重さの総和と使う荷物に関するもの
#  行が重さの上限
#  列が使える荷物の数に相当
dp = np.zeros((w + 1, n + 1), dtype=np.int)
for i in range(1, n + 1):
    #  更新の発想(wに意味はない)
    #  使える荷物が増えたが，利用はしない
    #  dp[w, i] = dp[w, i - 1]
    #  荷物を新しく許可された荷物を使う
    #  dp[w, i] = dp[w - wNew, i-1] + newValue
    #  このうちの価値の大きい方を使う
    dp[:, i] = dp[:, i - 1]
    dp[wv[i - 1, 0]:, :] = np.fmax(
        dp[wv[i - 1, 0]:, :], wv[i - 1, 1] + dp[: -wv[i - 1, 0], :]
    )

print(dp[w, n])


### FIXED CODE ###

import numpy as np


def main():
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.zeros((N, W + 1))
    dp[0, items[0, 0]:] = items[0, 1]
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, weight:] = np.fmax(
            dp[n, weight:],
            value + dp[n - 1, :(- weight)]
        )
    print(int(dp[N - 1, W]))


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

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
bag = [0 for _ in range(W+1)]
for w,v in a:
  for i in range(w,W+1)[::-1]:
    bag[i] = max(bag[i], bag[i-w] + v)
print(bag[W])  

### FIXED CODE ###

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
bag = [0 for _ in range(W+1)]
for w,v in a:
  for i in range(min(w,W+1),W+1)[::-1]:
    bag[i] = max(bag[i], bag[i-w] + v)
print(bag[W])
### BUGGY CODE ###

L , R = map(int,input().split())
if R - L >= 2019:
    print("0")
min = 2020
for i in range(L , R):
    for j in range(i + 1 , R + 1):
        tmp_min = ( i * j) % 2019
        if tmp_min < min:
            min = tmp_min
print(min)

### FIXED CODE ###

L , R = map(int,input().split())
if R - L >= 2019 or L == 0:
    print("0")
    exit()
min = 2020

for i in range(L , R):
    for j in range(i + 1 , R + 1):
        tmp_min = ( i * j) % 2019
        if tmp_min < min:
            min = tmp_min
print(min)
### BUGGY CODE ###

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

L.sort(reverse=True)

List = []
Sum = 0

for i in range(1, N - 1):
    for j in range(i + 1, N):
        List.append(L[i] + L[j])

for i in range(N - 2):
    for j in range(len(List)):
        if List[j] > L[i]:
            Sum += 1

    del List[0:N - i - 2]

print(Sum)



### FIXED CODE ###

import bisect

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

Sum = 0
L.sort(reverse=False)

for i in reversed(range(2,N)):
    for j in reversed(range(1,i)):
        hoge = 0
        hoge = j - bisect.bisect(L, L[i] - L[j])
        if hoge < 0:
            hoge = 0
        Sum += hoge

print(Sum)
### BUGGY CODE ###

H, W = map(int, input().split())

A = [list(map(lambda x: x == "#", input())) for i in range(H)]

lu = [[float("inf") for i in range(W + 2)] for j in range(H + 2)]

for ii in range(H*W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H*W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j]+1, lu[i][j + 1]+1, lu[i][j])


dist = max(sum([l[1:-1] for l in lu[1:-1]], []))
print(dist)

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline()[:-1]


H, W = map(int, input().split())

A = [[1 if s == "#" else 0 for s in input()] for i in range(H)]

lu = [[1<<20] * (W+2) for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = []
[dist.extend(l[1:-1]) for l in lu[1:-1]]
print(max(dist))
### BUGGY CODE ###

s = str(input())
cnt = 0
while len(s) > 1:
    for i in range(len(s) - 1):
        if s[i] != s[i + 1]:
            cnt += 2
            if i == len(s) - 1:
                break
            else:
                s = s[:i] + s[i + 2:]
                break
    else:
        break
print(cnt)


### FIXED CODE ###

s = str(input())
cnt = 0
prev = s[0]
stock = 1
for i in range(1, len(s)):
    if stock == 0:
        prev = s[i]
        stock += 1
    else:
        if s[i] != prev:
            cnt += 2
            stock -= 1
            if stock > 0:
                if s[i] == '0':
                    prev = '1'
                else:
                    prev = '0'
        else:
            prev = s[i]
            stock += 1
print(cnt)
### BUGGY CODE ###

from bisect import bisect_left
 
N,M = map(int, input().split())
Ap = input().split()
A = [0]*N
for i in range(N):
    A[i] = int(Ap[i])
A.sort()

for i in range(M):
    x = A[-1]
    x //= 2
    A = A[:-1]
    A.insert(bisect_left(A, x), x)
 
print(sum(A))

### FIXED CODE ###

from bisect import bisect_left
 
N,M = map(int, input().split())
A = sorted([int(x) for x in input().split()])
 
while M > 0:
    x = A.pop(-1)
    x //= 2
    ind = bisect_left(A, x)
    M -= 1
    if ind < N-1:
        temp = [x] + [A[-i-1]//2 for i in range(min(M, N-1 - ind))]
        A = sorted(A[:N-len(temp)] + temp)
    else:
        A.insert(bisect_left(A, x), x)
    M -= N-1 - ind
 
print(sum(A))
### BUGGY CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

q = 3 if S[0] == '?' else 1
a = b = c = 0
def fq():
    global a, b, c, q
    c = c * 3 + b
    b = b * 3 + a
    a = a * 3 + q
    q *= 3
def fa():
    global a
    a += q
def fb():
    global b
    b += a
def fc():
    global c
    c += b
funcs = {'A':fa, 'B': fb, 'C':fc, '?':fq}
if S[0] in 'A?':
    a = 1
for s in S[1:]:
    funcs[s]()
ans = c % MOD
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

print(ans)