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

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

n, q = map(int, readline().split())
s = readline().decode().rstrip()

lis = [0]*n
for i in range(n - 1):
    if s[i] + s[i + 1] == 'AC':
        # l.append(i+1)
        lis[i] = 1

for _ in range(q):
    l, r = map(int, readline().split())
    print(sum(lis[l-1:r-1:]))


### FIXED CODE ###

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

n, q = map(int, readline().split())
s = readline().decode().rstrip()

lis = [0]*n
for i in range(n - 1):
    if s[i] + s[i + 1] == 'AC':
        lis[i+1] = 1

a = list(itertools.accumulate(lis))

for _ in range(q):
    l, r = map(int, readline().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ma=max(a)
l=[[] for _ in range(ma+1)]
chk=[0]*n
ans=0
for i,x in enumerate(a):
    l[x].append(i)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(ma,0,-1):
    for j in l[i]:
        for x in range(cnt+1):
            if x==0:
                dp[x][cnt-x]=dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j)
            elif x==cnt:
                dp[x][cnt-x]=dp[x-1][cnt-x]+i*(j-x+1)
            else:
                dp[x][cnt-x]=max(dp[x-1][cnt-x]+i*(j-x+1),dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j))
        cnt+=1
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[]
for i,x in enumerate(a):
    l.append([x,i])
l.sort(reverse=True)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i,j in l:
    for x in range(cnt+1):
        if x==0:
            dp[x][cnt-x]=dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j)
        elif x==cnt:
            dp[x][cnt-x]=dp[x-1][cnt-x]+i*(j-x+1)
        else:
            dp[x][cnt-x]=max(dp[x-1][cnt-x]+i*(j-x+1),dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j))
    cnt+=1
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)
### BUGGY CODE ###

from itertools import product
N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        a = (4 * h * n - N * n - N * h)
        if a > 0 and (N * h * n) % a == 0:
            w = (N * h * n) / a
            int_w = int(w)
            if w == int_w:
                print(n,h,int_w)
                exit()

### FIXED CODE ###

from itertools import product
N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        a = (4 * h * n - N * n - N * h)
        if a > 0 and (N * h * n) % a == 0:
            w = (N * h * n) / a
            int_w = int(w)
            if w == int_w:
                print(n,h,int_w)
                exit()
### BUGGY CODE ###

def eratosthenes2(n):
    D=[-1]*(n+1)
    D[0]=0
    D[1]=1
    for i in range(2, n+1):
        if D[i] == -1:
            D[i] = i
            for j in range(i*i, n+1, i):
                if D[j] == -1:
                    D[j] = i
    return D

N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
D=eratosthenes2(maxA)
count=[0]*(maxA+1)
for x in A:
    pre=x+1
    while x>1:
        if pre!=D[x]:
            count[D[x]]+=1
            pre=D[x]
        x//=D[x]
maxc=max(count)
if maxc==N:
    print('not coprime')
elif maxc<=1:
    print('pairwise coprime')
else:
    print('setwise coprime')

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
count=[0]*(maxA+1)
for x in A:
    count[x]+=1
maxc=0
for i in range(2,maxA+1):
    maxc = max(maxc,sum(count[i::i]))

if maxc==N:
    print('not coprime')
elif maxc<=1:
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

from itertools import product
X = int(input())

tuple_list = []
S = [0, 1, 2, 3, 4, 5]
A = X // 100
B = X - (A * 100)
if A > B:
    print(1)
else:
    for s in product(S, repeat=A):
        if sum(s) == B:
            print(1)
            exit()
    else:
        print(0)

### FIXED CODE ###

from itertools import combinations_with_replacement
X = int(input())

S = [0, 1, 2, 3, 4, 5]
A = X // 100
B = X - (A * 100)
if A > B:
    print(1)
else:
    A_list = list(combinations_with_replacement(S, A))
    for i in A_list:
        if sum(i) == B:
            print(1)
            exit()
    else:
        print(0)
### BUGGY CODE ###

import math
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
a.sort()

div = [True] * (max(a) + 1)
used = defaultdict(int)
for n in a:
    if used[n] > 0:
        div[n] = False
        continue
    used[n] += 1
    if not div[n]:
        continue
    i = 2
    while n * i <= max(a):
        div[n * i] = False
        i += 1

ans = 0
for x in a:
    if div[x]:
        ans += 1

print(ans)

### FIXED CODE ###

import math
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
maxi = max(a)
a.sort()

div = [0] * (maxi + 1)
for n in a:
    div[n] += 1
    if div[n] == 1:
        for j in range(n*2, maxi + 1, n):
            div[j] += 100
print(div.count(1))
### BUGGY CODE ###

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

dp = [-1] * (T + 3000)
dp[0] = 0
for a, b in sorted(AB):
    for j in range(T - 1, -1, -1):
        if dp[j] == -1:
            continue
        if dp[j] + b > dp[j + a]:
            dp[j + a] = dp[j] + b
print(max(dp))


### FIXED CODE ###

def main():
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]

    dp = [-1] * (T + 3000)
    dp[0] = 0
    for a, b in sorted(AB):
        for j in range(T - 1, -1, -1):
            if dp[j] == -1:
                continue
            if dp[j] + b > dp[j + a]:
                dp[j + a] = dp[j] + b
    print(max(dp))


main()
### BUGGY CODE ###

N, A, B = map(int, input().split())
ABalls = ""
BBalls = ""
for a in range(A):
  ABalls += "B" 
for b in range(B):
  BBalls += "R"

Balls = ABalls + BBalls
AB = A + B
NumBBalls = 0

while N > AB:
  N -= AB
  NumBBalls += A

for n in range(N):
  if Balls[n] == "B":
    NumBBalls += 1
  else:
    break

print(NumBBalls)

### FIXED CODE ###

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

AB = A + B
NumABalls = 0

NumABalls = N//AB * A
M = N%AB

if A - M >= 0:
  NumABalls += M
else:
  NumABalls += A

print(NumABalls)
### BUGGY CODE ###

from collections import deque
n=int(input())
league=[deque(map(int,input().split())) for _ in range(n)]

total_match=n*(n-1)//2
match=0
day=0

for _ in range(total_match):
    day+=1
    today_match=deque([])

    for i,li in enumerate(league):
        if not i in today_match and li:
            m=li[0]-1
            lm=league[m]
            if not m in today_match and lm and lm[0]-1==i:
                today_match.append(li.popleft()-1)
                today_match.append(lm.popleft()-1)
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2
    if match>=total_match:
        break

print(day)


### FIXED CODE ###

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

N = int(input())
pair = N * (N - 1) // 2
ptoi = dict()

i = 0
for x in range(1, N):
    for y in range(x + 1, N + 1):
        ptoi[(x, y)] = i
        ptoi[(y, x)] = i
        i += 1

edge = [[] for _ in range(pair)]
indeg = [0] * pair
for i in range(1, N+1):
    inp = list(map(int, input().split()))
    for s, t in zip(inp[:-1], inp[1:]):
        edge[ptoi[(i, s)]].append(ptoi[(i, t)])
        indeg[ptoi[(i, t)]] += 1


now = [i for i, d in enumerate(indeg) if d == 0]
day = 0
while now:
    nxt = []
    while now:
        s = now.pop()
        for t in edge[s]:
            if indeg[t] <= 0:
                continue
            indeg[t] -= 1
            if indeg[t] == 0:
                nxt.append(t)
    day += 1
    now = nxt

if all(i <= 0 for i in indeg):
    print(day)
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            if j - i != k - j and S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
                 ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

R = [i for i in range(N) if S[i] == "R"]
G = [i for i in range(N) if S[i] == "G"]
B = [i for i in range(N) if S[i] == "B"]

ans = len(R) * len(G) * len(B)
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = 2 * j - i
        if k < N and S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
             ans -= 1

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

N,K=map(int,input().split())
h=[int(input()) for i in range(N)]
h.sort()
s=[]
for i in range(N-K+1):
  a=h[i:i+K]
  s.append(a)
cost=[]
for i in range(N-K+1):
  cost.append(max(s[i])-min(s[i]))
print(min(cost))

### FIXED CODE ###

N,K=map(int,input().split())
H=[int(input()) for i in range(N)]
H.sort()

ans=float('inf')
for i in range(N-K+1):
  ans=min(ans,H[i+K-1]-H[i])
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())

prefix = ''
suffix = ''
mode = 0
for _ in range(Q) :
  Query = list(input().split())
  if Query[0] == '1' :
    mode ^= 1
  else :
    _, F, C = Query
    F = int(F) - 1
    
    if mode != F :
      suffix += C
    else :
      prefix += C
      

if mode == 0 :
  print(prefix[::-1] + S + suffix)
else :
  print(suffix[::-1] + S[::-1] + prefix)

### FIXED CODE ###

S = input()
Q = int(input())

prefix = ''
suffix = ''
mode = 0
for _ in range(Q) :
  Query = list(input().split())
  if Query[0] == '1' :
    mode ^= 1
  else :
    _, F, C = Query
    F = int(F) - 1
    
    if mode != F :
      suffix += C
    else :
      prefix += C
      

if mode == 0 :
  print(prefix[::-1] + S + suffix)
else :
  print(suffix[::-1] + S[::-1] + prefix)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
out = 1
for i in range(N):
  out *= A[i]

if out <= 1e18:
  print(out)
else:
  print('-1')

### FIXED CODE ###

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

A.sort(reverse=True)
out = 1
if A[-1] == 0:
  out = 0
else:
  for i in A:
    out *= i
    if out > 1e18:
      out = -1
      break
print(out)
### BUGGY CODE ###

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

def check(X):
  idx = [0]
  ltr = [0]
  for a in A:
    if idx[-1] < a:
      idx.append(a)
      ltr.append(0)
    else:
      while True:
        while idx[-1] > a:
          idx.pop()
          ltr.pop()
        if idx[-1] != a:
          idx.append(a)
          ltr.append(0)
        if idx[-1] == 0:
          return False
        ltr[-1] += 1
        if ltr[-1] < X:
          break
        a = idx[-1] - 1
        idx.pop()
        ltr.pop()
  return ltr[0] == 0

t = [0, N]
while t[1] - t[0] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(t[1])

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if A == sorted(A) and len(A) == len(set(A)):
  print(1)
  exit(0)

def check(X):
  idx = [0]
  ltr = [0]
  for a in A:
    if idx[-1] < a:
      idx.append(a)
      ltr.append(0)
    else:
      while True:
        while idx[-1] > a:
          idx.pop()
          ltr.pop()
        if idx[-1] != a:
          idx.append(a)
          ltr.append(0)
        if idx[-1] == 0:
          return False
        ltr[-1] += 1
        if ltr[-1] < X:
          break
        a = idx[-1] - 1
        idx.pop()
        ltr.pop()
  return ltr[0] == 0

t = [1, N]
while t[1] - t[0] > 1:
  mid = (t[0] + t[1]) // 2
  t[check(mid)] = mid
print(t[1])
### BUGGY CODE ###

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

dp = [True] * (A[-1] + 1)
for a in A:
    n = 2
    while n * a <= A[-1]:
        dp[n * a] = False
        n += 1

score = 0
for a in A:
    score += dp[a] * (A.count(a) == 1)
    
print(score)

### FIXED CODE ###

import collections

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

dp = collections.defaultdict(lambda: True)

for i in range(N):
    if i < N - 1 and A[i] == A[i + 1]:
        dp[A[i]] = False
    k = 2
    while True:
        if A[i] * k > A[-1]:
            break
        else:
            dp[A[i] * k] = False
            k += 1

print(sum(dp[a] for a in A))
### BUGGY CODE ###

def main():
    from heapq import heapify,heapreplace
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    A = list(map(int,input().split()))
    BC = [list(map(int,input().split())) for _ in range(m)]

    heapify(A)

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    for b,c in BC:
        if c<A[0]:
            break
        for i in range(b):
            if A[0]>c:
                break
            heapreplace(A,c)
        
    #print(A)
    print(sum(A))
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    A = list(map(int,input().split()))
    BC = [list(map(int,input().split())) for _ in range(m)]

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    append_list = []
    for b,c in BC:
        if len(append_list)>=n:
            break
        append_list+=[c]*b
    A+=append_list
    A.sort(reverse=True)
    print(sum(A[:n]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

N = int(input())
A  = [int(x) for x in input().split()]
total = 1
for a in A:
    total *= a 

if total > 10 ** 18:
    print(-1)
else:
    print(total)

### FIXED CODE ###

N = int(input())
A  = [int(x) for x in input().split()]
total = 1
if 0 in A:
    print(0)
else:    
    for a in A:
        total *= a 
        if total > 10 ** 18:
            print(-1)
            break

    if total <= 10 ** 18:
        print(total)
### BUGGY CODE ###

#!/usr/bin/env python3


def div_ceil(a, b):
    return (a + b - 1) // b


def solve(n, xs, ys):
    ctr = 0
    for i in range(n)[::-1]:
        diff = div_ceil(xs[i], ys[i]) * ys[i] - xs[i]
        ctr += diff
        for j in range(i + 1):
            xs[j] += diff
    return ctr


def main():
    n = int(input())
    data = (tuple(int(x) for x in input().split()) for _ in range(n))
    xs, ys = (list(line) for line in zip(*data))
    print(solve(n, xs, ys))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env pypy3


def div_ceil(a, b):
    return (a + b - 1) // b


def solve(n, xs, ys):
    ctr = 0
    for i in range(n)[::-1]:
        xs[i] += ctr
        diff = div_ceil(xs[i], ys[i]) * ys[i] - xs[i]
        ctr += diff
    return ctr


def main():
    n = int(input())
    data = (tuple(int(x) for x in input().split()) for _ in range(n))
    xs, ys = (list(line) for line in zip(*data))
    print(solve(n, xs, ys))


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

N = int(input())
A = list(map(lambda x: format(int(x), '060b'), input().split(' ')))
mod = 10 ** 9 + 7
one = [0]*60
ans = 0
for i in A:
    for n, j in enumerate(i[::-1]):
        if int(j):
            one[n] += 1
for n,i in enumerate(one):
    ans = (ans + 2**n *i*(N-i))%mod
print(ans)

### FIXED CODE ###

N = int(input())
A = ''.join(list(map(lambda x: format(int(x), '060b'), input().split(' '))))
mod = 10 ** 9 + 7
ans = 0
for n in range(60):
    one = A[59-n::60].count('1')
    ans = (ans + 2**n *one*(N-one))%mod
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
import copy


# 標準入力
n = int(sys.stdin.readline().strip())
xArray = list(map(int, sys.stdin.readline().strip().split(" ")))

result = []

# 演算処理
for i in range(n):
    tmp = copy.copy(xArray)
    del tmp[i]
    tmp = sorted(tmp)
    result.append(tmp[int((n/2) - 1)]) # (l + 1)/2 の要素を参照


# 標準出力
print('\n'.join(map(str, result)))



### FIXED CODE ###

# coding: utf-8
import sys
import copy


# 標準入力
n = int(sys.stdin.readline().strip())
xArray = list(map(int, sys.stdin.readline().strip().split(" ")))

result = []

sortedArray = sorted(xArray)


# 中央値を算出する
for i in range(n):
    middle = sortedArray[int((n / 2) - 1)]
    if (middle >= xArray[i]):
        result.append(sortedArray[int(n / 2)])
    else:
        result.append(middle)


# 標準出力
print('\n'.join(map(str, result)))
### BUGGY CODE ###

import logging

logger = logging.getLogger(__name__)
logger.setLevel(logging.INFO)
h = logging.FileHandler("logtest.log")
logger.addHandler(h)

N, Q = map(int, input().split())
S = list(map(str, input().strip()))
logger.info("S: {}".format(S))

order = [tuple(map(str, input().split())) for _ in range(Q)]
order = order[::-1]
logger.info("order: {}".format(order))

# left: 左に落ちるゴーレム
# right: 右に落ちるゴーレム
#  N-right-left: 生き残るゴーレム
left, right = 0, N - 1
logger.info("left: {}, right: {}".format(left, right))

# 二分探索
for a in order:
    t, d = a[0], a[1]
    logger.info("t: {}, d: {}".format(t, d))
    logger.info("[before] left: {}, right: {}".format(left, right))

    if d == "L":
        if S[left] == t:
            left += 1
            if left > N - 1:
                pass

        if right < N - 1 and S[right + 1] == t:
            right = min(N - 1, right + 1)

    else:
        if left > 0 and S[left - 1] == t:
            left = max(0, left - 1)

        if S[right] == t:
            right -= 1
            if right < 0:
                pass

    logger.info("[after] left: {}, right: {}\n".format(left, right))


print(right - left + 1)


### FIXED CODE ###

# N, Q = map(int, input().split())
import sys

input = sys.stdin.readline

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

Query = [input().split() for i in range(Q)]

left, right = 0, N - 1

for t, d in reversed(Query):
    if d == "L":
        if t == s[left]:
            left += 1
        if right < N - 1 and t == s[right + 1]:
            right = min(right + 1, N - 1)
    else:
        if left > 0 and t == s[left - 1]:
            left = max(left - 1, 0)
        if t == s[right]:
            right -= 1
print(max(right - left + 1, 0))
### BUGGY CODE ###

s,k = input().split()
mod = 998244353
k = int(k)
k = min(300,k)
raw = [0]
l = len(s)
for i in range(l):
  if s[i] == '0':
    raw.append(0)
  else:
    raw[-1] += 1
#print(raw)
now = [[0 for _ in range(k+1)] for _ in range(k+1)]
l = len(raw)
raw.reverse()
#print(raw)
now[0][0] = 1
for x in raw:
  last = now[:]
  now = [[0 for _ in range(k+1)] for _ in range(k+1)]
  for i in range(k+1):
    for j in range(k+1):
      for mag in range(x+1):
        if mag + i > k or mag + j > k:
          continue
        now[i+mag][j+mag] += last[i][j]
        now[i+mag][j+mag] %= mod
      for dim in range(j):
        now[i][dim] += last[i][j]
        now[i][dim] %= mod
  #print(now)
#print(now)
ans = 0
for i in range(k+1):
  ans += now[i][0]
print(ans%mod)

### FIXED CODE ###

s,k = input().split()
mod = 998244353
k = int(k)
k = min(300,k)
raw = [0]
l = len(s)
for i in range(l):
  if s[i] == '0':
    raw.append(0)
  else:
    raw[-1] += 1
#print(raw)
now = [[0 for _ in range(k+1)] for _ in range(k+1)]
l = len(raw)
raw.reverse()
#print(raw)
now[0][0] = 1
for x in raw:
  last = now[:]
  now = []
  for i in range(k+1):
    use = last[i][:]
    use.reverse()
    cum = []
    for j in range(k+1):
      if cum:
        cum.append(cum[-1]+use[j])
        cum[-1] %= mod
      else:
        cum = [use[0]]
    cum.reverse()
    now.append(cum)
    #print(cum)
  #print('#')
  cum2 = []
  for i in range(k+1):
    cum = [0 for _ in range(i)]
    cum.append(last[i][0])
    #print('%',cum)
    for l in range(i+1,k+1):
      cum.append(cum[-1]+last[l][l-i])
    #print(cum)
    cum2.append(cum)
  for i in range(k+1):
    for j in range(k+1):
      if j > i:
        pass
      now[i][j] += cum2[i-j][i]
      if i - x - 1 >= 0:
        now[i][j] -= cum2[i-j][i-x-1]
      now[i][j] %= mod
  for i in range(k+1):
    for j in range(k+1):
      now[i][j] -= last[i][j]
      now[i][j] %= mod
  #print(now)
  #print('##')
        
  #print(now)
#print(now)
ans = 0
for i in range(k+1):
  ans += now[i][0]
print(ans%mod)
### BUGGY CODE ###

S = input()

ans = 0
for i in range(len(S)):
    Sum = int(S[i])
    for j in range(i+1, len(S)):
        Sum += int(S[j])
        if Sum % 3 != 0:
            continue
        if int(S[i:j+1]) % 2019 == 0:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

S = input()
N = len(S)

dp = [0] * N
dp[N-1] = int(S[N-1])
times = 10
for i in reversed(range(1, N)):
    dp[i-1] = (dp[i] + times * int(S[i-1])) % 2019
    times *= 10
    times %= 2019

T = Counter(dp)
ans = T[0]
for t in T.values():
    ans += t*(t-1)//2

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

import sys
input = sys.stdin.readline

n = input()
n_list = [int(i) for i in input().split()]
value = 1
for i in n_list:
    value = value * i


if value > 10**18:
    value = -1
print(value)



### FIXED CODE ###

import sys
input = sys.stdin.readline

n = input()
n_list = sorted([int(i) for i in input().split()])
value = 1
for i in n_list:
    value = value * i
    if value > 10 ** 18:
        value = -1
        break
print(value)
### BUGGY CODE ###

N=int(input())
A = list(map(int,input().split()))
mod = 10**9+7
Ans = 0
for i in range(60):
  Po=0
  Ne=0
  for j in A:
    if j>>i & 1:
      Po+=1
    else:
      Ne+=1
  Ans += Po*Ne*(2**i)
  Ans = Ans % mod
print(Ans)

### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
mod = 10**9+7
Ans = 0
for i in range(60):
  Po=sum([1 for j in A if j>>i & 1])
  Ans += Po*(N-Po)*(2**i)
  Ans = Ans % mod
print(Ans)
### BUGGY CODE ###

import numpy as np
from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
map = [input() for _ in range(h)]

f_inf = float('inf')
visited = np.array([[f_inf] * w for _ in range(h)])
que = deque([])
for i in range(h):
    for j in range(w):
        if map[i][j] == "#":
            visited[i][j] = 0
            que.append([i, j])

while que:
    y, x = que.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y, next_x = y + i, x + j
        if -1 < next_y < h and -1 < next_x < w and map[next_y][next_x] == ".":
            if visited[next_y][next_x] > visited[y][x] + 1:
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])

print(int(np.max(visited)))


### FIXED CODE ###

from collections import deque

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

cnt = [[-1]*W for _ in range(H)]

que = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            que.append((h, w))
            cnt[h][w] = 0

ans = 0
while que:
    h, w = que.popleft()
    ans = cnt[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        next_h = h + dy
        next_w = w + dx
        if next_h < 0 or H <= next_h or next_w < 0 or W <= next_w:
            continue
        if cnt[next_h][next_w] == -1:
            cnt[next_h][next_w] = ans+1
            que.append((next_h, next_w))

print(int(ans))