Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02919 (python)

Fixed submission:
N = int(input())
P = [None] + [int(x) for x in input().split()]
id_list = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    id_list[x] = i

# 左隣にあるインデックスを取得できるようにしておく
# Binary Iindex Treeを使うことで、区間[L,R]内での和をとれば[L,R]内のデータ件数を数えられる
class BIT:
    def __init__(self, n):
        # 要素数を与えてインスタンス化
        self.size = n
        self.tree = [0] * (n + 1) # index must be 1-origin

    def add(self, i, x=1):
        # add x(>= 1) to a_i
        while i <= self.size:
            self.tree[i] += x
            i += i&(-i) # i&(-i) = BITでのi番目の区間の長さ

    def sum(self, i):
        # sum of a_1, a_2, ... , a_i
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i) # i&(-i) = BITでのi番目の区間の長さ
        return s

    def search(self, x):
        # 二分探索。a_1 + a_2 + ... + a_i >= xなる最小のインデックスi(>= 1)を返す
        i = 0
        s = 0
        step = 1<<(N.bit_length()-1) # the largest 2^k (= step) <= N
        while step:
            if i+step <= N and s + self.tree[i+step] < x:
                i += step
                s += self.tree[i]
            step >>= 1
        return i+1


def main():
    bit = BIT(N)
    ans = 0
    for x in range(N,0,-1):
        idx = id_list[x]
        L = bit.sum(idx) # 左にある既に書き込んだ数の個数
        bit.add(idx)
        R = N-x-L # 右にある既に書き込んだ数の個数
        ll = bit.search(L-1) if L >= 2 else 0
        l = bit.search(L) if L >= 1 else 0
        r = bit.search(L+2) if R >= 1 else N+1
        rr = bit.search(L+3) if R >= 2 else N+1
        coef = 0
        if l != 0:
            # [b,c]を含むようにする。(a,b) と(c,d)が自由
            coef += (l - ll) * (r - idx)
        if r != 0:
            # [c,d]を含むようにする。
            coef += (rr - r) * (idx - l)
        ans += x * coef
    print(ans)

main()

Buggy submission (verdict: Runtime Error):
import bisect
import numpy as np

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

max_idx = np.argmax(np.array(P))
finished = [-1, -1, max_idx, N, N] # index set
#print(finished)

ans = 0
for i in range(N - 1, 0, -1):
    idx = np.where(np.array(P) == i)[0][0]
    idx2 = bisect.bisect_left(finished, idx)
    bisect.insort_left(finished, idx)
    #print(finished)
    x = finished[idx2 - 1]
    y = finished[idx2 + 1]
    z = finished[idx2 + 2]
    w = finished[idx2 - 2]
    #print('When P_i = {}, w={}, x={}, y={}, z={}'.format(i,w,x,y,z))

    C = (x - w) * (y - idx) + (idx - x) * (z - y)
    ans += i * C
    #print('ans = {}'.format(ans))

print(ans)
Problem p02937 (python)

Fixed submission:
import bisect

s = input()
t = input()
T = set(t)
s_num = len(s)
t_num = len(T)

# make a dictonary whose keys are the alphabets in t
dict = {}
appearing_times = {}

# when each alphabet in t appears in s
for w in T:
    dict[w] = []
    appearing_times[w] = 0
    index = -1
    while True:
        index = s.find(w, index + 1)
        if index == -1 and appearing_times[w] == 0:
            print(-1)
            exit()
        elif index == -1:
            break
        else:
            dict[w].append(index)
            appearing_times[w] += 1

# how many times s is repeated
count = 0
# 0 <= length <= s_num - 1
s_index = 0
w_pre = 'none'

for w in t:
    idx = bisect.bisect_left(dict[w], s_index)
    if w == w_pre:
        idx += 1
        if idx == appearing_times[w]:
            count += 1
            idx = 0

    if idx < appearing_times[w]:
        s_index = dict[w][idx]
    else:
        count += 1
        s_index = dict[w][0]
    w_pre = w

print(count * s_num + s_index + 1)

Buggy submission (verdict: Runtime Error):
import bisect

s = input()
t = input()
T = set(t)
s_num = len(s)
t_num = len(T)

# make a dictonary whose keys are the alphabets in t
dict = {}
appearing_times = {}

# when each alphabet in t appears in s
for w in T:
    dict[w] = []
    appearing_times[w] = 0
    index = -1
    while True:
        index = s.find(w, index + 1)
        if index == -1 and appearing_times[w] == 0:
            print(-1)
            exit()
        elif index == -1:
            break
        else:
            dict[w].append(index)
            appearing_times[w] += 1

# how many times s is repeated
count = 0
# 0 <= length <= s_num - 1
s_index = 0
check = 0

for w in t:
    idx = bisect.bisect_left(dict[w], s_index)
    if check == 'done' and s_index == dict[w][idx]:
        idx = idx + 1

    if idx < appearing_times[w]:
        s_index = dict[w][idx]
    else:
        count += 1
        s_index = dict[w][0]

    check = 'done'
print(count * s_num + s_index + 1)
Problem p02975 (python)

Fixed submission:
from collections import deque

N = int(input())
A = deque(map(int, input().split()))
first = A.popleft()


def round(a):
        B = list(A)
        eval = 0
        pre = first
        post = a
        B.remove(a)
        num = N - 2
        while num != 0:
                c = pre ^ post
                try:
                        B.remove(c)
                        pre = post
                        post = c
                        num -= 1
                except:
                        return 0
                        eval = 1
                        break
        
        if eval == 0 and post ^ first == a:
                return 1
        elif eval == 0:
                return 0

val = first
for i in range(N - 1):
        val = val ^ A[i]

if val != 0:
        print('No')
else:
        ans = 0
        for i in range(0, N - 1):
                ans = round(A[i])
                if ans == 1:
                        print('Yes')
                        break
                        

        if ans == 0:
                print('No')

Buggy submission (verdict: Runtime Error):
n, m = list(map(int, input().split()))
AB = [[int(x) for x in input().split()] for _ in range(m)]

# representation matrix
repn = [[] for j in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    repn[a].append(b)
    repn[b].append(a)


# Minimum Spanning Tree
tree = [[] for i in range(n)]
visited = [True] + [False] * (n - 1)
q = [0]

while q:
    u = q.pop()
    for v in repn[u]:
        if visited[v]:
            continue
        visited[v] = True
        tree[u].append(v)
        tree[v].append(u)
        q.append(v)


# define directions of the edges other than that of MST
degree = [0] * n
ans = []

for a, b in AB:
    a -= 1
    b -= 1
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a + 1, b + 1))
    degree[a] += 1


# defining orientations
def dfs(u = 0, parent = None):
    for v in tree[u]:
        if v == parent:
            continue
        dfs(v, u)
        if degree[v] % 2 == 0:
            ans.append('{} {}'.format(u + 1, v + 1))
            degree[u] += 1
        else:
            ans.append('{} {}'.format(v + 1, u + 1))
            degree[v] += 1

dfs()


# output answer
if degree[0] % 2 == 1:
    print(-1)
else:
    print('\n'.join(ans))
Problem p02993 (python)

Fixed submission:
S = input()

if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print('Bad')
else:
    print('Good')

Buggy submission (verdict: Runtime Error):
i = int(input())
S = []
while i > 0:
    S.append(i%10)
    i //= 10 # 必須
S.reverse()
if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print('Bad')
else:
    print('Good')

Buggy submission (verdict: Runtime Error):
S = int(input())
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3]:
    print('Bad')
else:
    print('Good')
Problem p02995 (python)

Fixed submission:
import fractions

A, B, C, D = list(map(int, input().split()))
C_mult = (B // C) - ((A-1) // C)
D_mult = (B // D) - ((A-1) // D)

E = C * D // fractions.gcd(C, D)

inter = (B // E) - ((A-1) // E)
whole = B - A + 1
print(whole - C_mult - D_mult + inter)

Buggy submission (verdict: Runtime Error):
import math

A, B, C, D = list(map(int, input().split()))
C_mult = (B // C) - ((A-1) // C)
D_mult = (B // D) - ((A-1) // D)

E = C * D // math.gcd(C, D)

inter = (B // E) - ((A-1) // E)
whole = B - A + 1
print(whole - C_mult - D_mult + inter)

Buggy submission (verdict: Runtime Error):
import math

A, B, C, D = list(map(int, input().split()))
C_mult = (B // C) - ((A-1) // C)
D_mult = (B // D) - ((A-1) // D)

E = C * D // math.gcd(C, D)

inter = (B // E) - ((A-1) // E)
whole = B - A + 1
print(whole - C_mult - D_mult + inter)
Problem p03007 (python)

Fixed submission:
from collections import deque

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

# A[cut-1] < 0 and A[cut] >= 0
cut = 0
while cut < N and A[cut] < 0:
    cut += 1

if cut == 0:
    M = sum(A[1:]) - A[0]
    print(M)
    pair = [A[0], A[N-1]]
    for i in range(N-2):
        print(' '.join(map(str, pair)))
        pair = [pair[0] - pair[1], A[N-i-2]]
    pair.reverse()
    print(' '.join(map(str, pair)))

elif cut == N:
    M = A[-1] - sum(A[:N-1])
    print(M)
    pair = [A[N-1], A[0]]
    for i in range(N-2):
        print(' '.join(map(str, pair)))
        pair = [pair[0] - pair[1], A[i+1]]
    print(' '.join(map(str, pair)))

else:
    M = sum(A[cut:]) - sum(A[:cut])
    print(M)

    B = deque(A[cut:]) # Aの正の部分
    C = deque(A[:cut]) # Aの負の部分

    while len(B) != 1:
        pair = [C[-1], B[-1]]
        print(' '.join(map(str, pair)))
        b = B.pop()
        C[-1] = C[-1] - b
    
    b = B.pop()

    while len(C) != 0:
        pair = [b, C[0]]
        print(' '.join(map(str, pair)))
        c = C.popleft()
        b = b - c

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
A.sort()

# A[cut-1] < 0 and A[cut] >= 0
cut = 0
while A[cut] < 0:
    cut += 1

if cut == 0:
    M = sum(A[1:]) - A[0]
    print(M)
    pair = [A[0], A[1]]
    for i in range(N-2):
        print(' '.join(map(str, pair)))
        pair = [pair[0] - pair[1], A[i+2]]
    print(' '.join(map(str, pair)))

elif cut == N-1:
    M = A[-1] - sum(A[:N-1])
    print(M)
    pair = [A[N-1], A[0]]
    for i in range(N-2):
        print(' '.join(map(str, pair)))
        pair = [pair[0] - pair[1], A[i+1]]
    print(' '.join(map(str, pair)))

else:
    M = sum(A[cut:]) - sum(A[:cut])
    print(M)
    pair = [A[cut-1], A[N-1]]
    for i in range(N - cut - 2):
        print(' '.join(map(str, pair)))
        pair = [pair[0] - pair[1], A[N-i-2]]
    print(' '.join(map(str, pair)))
    
    rem = pair[0] - pair[1]
    if cut == 1:
        pair = [A[cut], rem]
        print(' '.join(map(str, pair)))
    else:
        pair = [A[cut], A[0]]
        for i in range(cut - 2):
            print(' '.join(map(str, pair)))
            pair = [pair[0] - pair[1], A[i+1]]
        print(' '.join(map(str, pair)))
        pair = [pair[0]- pair[1], rem]
        print(' '.join(map(str, pair)))

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input()split()))
A.sort()

if N % 2 == 0:
    A_neg = A[:N//2]
    A_pos = A[N//2:]
    M = sum(A_pos) - sum(A_neg)
    print(M)
    print(' '.join(map(str, [A[-1], A[0]])))
    num = A[-1] - A[0]
    for i in range(N-2):
        print(' '.join(map(str, [num, A[i+1]])))

if N % 2 == 1:
    A_neg = A[:N//2]
    A_pos = A[N//2:]
    M = sum(A_pos) - sum(A_neg)
    print(M)
    print(' '.join(map(str, [A[-1], A[0]])))
    num = A[-1] - A[0]
    for i in range(N-2):
        print(' '.join(map(str, [num, A[i+1]])))
Problem p03062 (python)

Fixed submission:
import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    
    """
    もし負の数が偶数個存在すればそれらはすべて正の数にできる。
    もし負の数が奇数個存在すればそれは最終的に１個にできる。
    """

    idx = bisect_left(A, 0)
    if idx % 2 == 0:
        print(sum(A[idx:]) - sum(A[:idx]))
    elif idx < len(A) :
        cand1 = sum(A[idx:]) - sum(A[:idx]) + A[idx - 1] * 2
        cand2 = sum(A[idx:]) - sum(A[:idx]) - A[idx] * 2
        print(max(cand1, cand2))
    else:
        print(-sum(A) + A[-1] * 2)
    


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    
    """
    もし負の数が偶数個存在すればそれらはすべて正の数にできる。
    もし負の数が奇数個存在すればそれは最終的に１個にできる。
    """

    idx = bisect_left(A, 0)
    if idx % 2 == 0:
        print(sum(A[idx:]) - sum(A[:idx]))
    else:
        cand1 = sum(A[idx:]) - sum(A[:idx]) + A[idx - 1] * 2
        cand2 = sum(A[idx:]) - sum(A[:idx]) - A[idx] * 2
        print(max(cand1, cand2))
    


if __name__ == "__main__":
    main()
Problem p03074 (python)

Fixed submission:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    S = input()

    """
    反転させる区間は独立であるとしてよい。実際反転させる２区間が左図のように
    オーバーラップしていたとすると、これは右図のように反転させるのと同値だからである：
               _______________                             _______  
        ______|_______        |     --->    ______        |       |
    ___|______|_______|_______|_____    ___|______|_______|_______|_____ 
    
    そうすると安直には0がなるべく長く連続している区間に反転をかけたくなるが、
    長い順に反転をかけた場合1が連続する保証がないのでダメ。

    そこで1の連続する箇所を固定したうえで、そこから0の連続する区間に順番に反転をかけることを考える。
    当然愚直にやるとTLEなので、累積和で実装する
    """

    A = []
    char = S[0]
    cnt = 1
    for i in range(1, N):
        if S[i] == char:
            cnt += 1
        else:
            A.append(cnt)
            char = S[i]
            cnt = 1
    A.append(cnt)
    #print("A={}".format(A))

    B = list(accumulate(A))
    B.append(B[-1])
    #print("B={}".format(B))
    l = len(A)
    if S[0] == '0':
        ans = B[min(K * 2 - 1, l - 1)]
        for i in range(1, l - K * 2 + 1):
            if i % 2 == 0:
                j = i + K * 2 - 1
                val = B[j] - B[i - 1]
            else:
                j = i + K * 2
                val = B[j] - B[i - 1]
            #print("[{}, {}]->val={}".format(i, j, val))
            ans = max(ans, val)
    else:
        ans = B[min(K * 2, l - 1)]
        for i in range(1, l - K * 2 + 1):
            if i % 2 == 1:
                j = i + K * 2 - 1
                val = B[j] - B[i - 1]
            else:
                j = i + K * 2
                val = B[j] - B[i - 1]
            #print("[{}, {}]->val={}".format(i, j, val))
            ans = max(ans, val)
    print(ans)
       


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
T = input()
S = [int(x) for x in list(str(T))]

L = []
num = 1
for i in range(N-1):
    if S[i] == S[i+1]:
        num += 1
    else:
        L.append(num)
        num = 1
L.append(0)

if S[0] == 0:
    cand = L[0] + L[1]
    l = len(L)
    for i in range(1, (l+1)//2):
        length = L[2*i - 1] + L[2*i] + L[2*i + 1]
        cand = max(cand, length)
    print(cand)
Problem p03129 (python)

Fixed submission:
N_K = list(map(int, input().split()))
N = N_K[0]
K = N_K[1]

if K * 2 - 1 <= N:
    print('YES')
else:
    print('NO')

Buggy submission (verdict: Runtime Error):
N = int(input())
K = int(input())

if K * 2 - 1 <= N:
    print('YES')
else:
    print('NO')
Problem p03213 (python)

Fixed submission:
import sys, math
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit < p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def main():
    N = int(input())
    if N < 10:
        print(0)
        return
    table = get_sieve_of_eratosthenes(N)
    #print(table)
    primes = defaultdict(int)
    for n in range(2, N + 1):
        for p in table:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            primes[p] += cnt
    #print(primes)
    
    over_3 = 0
    over_5 = 0
    over_15 = 0
    over_25 = 0
    over_75 = 0
    for p in primes:
        if primes[p] >= 2: over_3 += 1
        if primes[p] >= 4: over_5 += 1
        if primes[p] >= 14: over_15 += 1
        if primes[p] >= 24: over_25 += 1
        if primes[p] >= 74: over_75 += 1
    #print(over_3)
    #print(over_5)
    #print(over_15)
    #print(over_25)
    #print(over_75)
    
    val1 = over_5 * (over_5 - 1) * (over_3 - 2) // 2
    val2 = over_15 * (over_5 - 1)
    val3 = over_25 * (over_3 - 1)
    print(val1 + val2 + val3 + over_75)

    




if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys, math
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit < p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def main():
    N = int(input())
    table = get_sieve_of_eratosthenes(N)
    #print(table)
    primes = defaultdict(int)
    for n in range(2, N + 1):
        for p in table:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            primes[p] += cnt
    #print(primes)
    
    over_3 = 0
    over_5 = 0
    over_15 = 0
    over_25 = 0
    over_75 = 0
    for p in primes:
        if primes[p] >= 2: over_3 += 1
        if primes[p] >= 4: over_5 += 1
        if primes[p] >= 14: over_15 += 1
        if primes[p] >= 24: over_25 += 1
        if primes[p] >= 74: over_75 += 1
    #print(over_3)
    #print(over_5)
    #print(over_15)
    #print(over_25)
    #print(over_75)
    
    val1 = over_5 * (over_5 - 1) * (over_3 - 2) // 2
    val2 = over_15 * (over_5 - 1)
    val3 = over_25 * (over_3 - 1)
    print(val1 + val2 + val3 + over_75)

    




if __name__ == "__main__":
    main()
Problem p03353 (python)

Fixed submission:
import sys
from heapq import *
def input(): return sys.stdin.readline().strip()


def main():
    """
    文字列のソートをする際には計算量に要注意！
    数字の大小比較と違って文字列の比較の場合は１文字１文字左から順番に見ないといけない。
    そのため一回の比較でO(比較文字列の長さ)分の計算量がかかる。
    特に長さMの文字列N個をソートするのにかかる時間は
            ❌O(NlogN)
            ⭕️O(MNlogN)

    そこで文字列のソート時には文字数をなるべく小さくするのがポイント。
    今回K<=5なので、「答えはK<=5文字以下になる」のがミソ。
    """

    s = input()
    L = len(s)
    K = int(input())
    string = set([])
    for i in range(L):
        for j in range(i + 1, min(i + K, L) + 1):
            string.add(s[i:j])

    string = list(string)
    heapify(string)
    for _ in range(K):
        ans = heappop(string)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from heapq import *
def input(): return sys.stdin.readline().strip()


def main():
    s = input()
    L = len(s)
    K = int(input())

    initial = []
    for i, c in enumerate(s):
        heappush(initial, (c, i))

    appeared = set([])
    string =[]
    cnt = 0
    while True:
        c, i = heappop(initial)
        for j in range(i + 1, L + 1):
            heappush(string, s[i:j])
        while initial[0][0] == c:
            c, i = heappop(initial)
            for j in range(i + 1, L + 1):
                heappush(string, s[i:j])
        while string:
            ans = heappop(string)
            #print(ans)
            if ans not in appeared:
                cnt += 1
                appeared.add(ans)
            if cnt == K:
                print(ans)
                return


if __name__ == "__main__":
    main()
Problem p03547 (python)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    x, y =input().split()
    if ord(x) < ord(y):
        print("<")
    elif ord(x) > ord(y):
        print(">")
    else:
        print("=")
    


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def main():
    x, y =input().split()
    if ord(x) < ord(y):
        print("<")
    elif ord(X) > ord(y):
        print(">")
    else:
        print("=")
    


if __name__ == "__main__":
    main()
Problem p03556 (python)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    n = int(input())
    ans = 1
    while ans ** 2 <= n: ans += 1
    print((ans - 1) ** 2)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()


def main():
    s = input()
    t = input()
    for i, c in enumerate(s):
        if t[-i-1] != c:
            print("NO")
            return
    print("YES")

if __name__ == "__main__":
    main()
Problem p03574 (python)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    H, W = map(int, input().split())
    S = ['.' * W] + [input() for _ in range(H)] + ['.' * W]
    if W == 1:
        for i in range(1, H + 1):
            if S[i] == '#':
                print('#')
                continue
            string = S[i - 1] + S[i + 1]
            cnt = string.count('#')
            print(str(cnt))
        return
    for i in range(1, H + 1):
        code = ""
        for j in range(W):
            if S[i][j] == '#':
                code += '#'
                continue
            if j == 0:
                string = S[i - 1][:2] + S[i][1] + S[i + 1][:2]
                cnt = string.count('#')
                code += str(cnt)
                continue
            if j == W - 1:
                string = S[i - 1][-2:] + S[i][-2] + S[i + 1][-2:]
                cnt = string.count('#')
                code += str(cnt)
                continue
            string = S[i - 1][j - 1:j + 2] + S[i][j - 1] + S[i][j + 1] + S[i + 1][j - 1:j + 2]
            cnt = string.count('#')
            code += str(cnt)
            continue
        print(code)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()

def main():
    H, W = map(int, input().split())
    S = ['.' * W] + [input() for _ in range(H)] + ['.' * W]
    for i in range(1, H + 1):
        code = ""
        for j in range(W):
            if S[i][j] == '#':
                code += '#'
                continue
            if j == 0:
                string = S[i - 1][:2] + S[i][1] + S[i + 1][:2]
                cnt = string.count('#')
                code += str(cnt)
                continue
            if j == W - 1:
                string = S[i - 1][-2:] + S[i][-2] + S[i + 1][-2:]
                cnt = string.count('#')
                code += str(cnt)
                continue
            string = S[i - 1][j - 1:j + 2] + S[i][j - 1] + S[i][j + 1] + S[i + 1][j - 1:j + 2]
            cnt = string.count('#')
            code += str(cnt)
            continue
        print(code)


if __name__ == "__main__":
    main()