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

import sys
input = sys.stdin.readline

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

road = []
x_list = []
for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append((s-x,x,0))
    road.append((t-x,x,1))
    x_list.append(x)

for i in range(Q):
    d = int(input())
    road.append((d,i,2))

road.sort(lambda x:x[2])
road.sort(lambda x:x[0])

x_list = list(set(x_list))
x_list.sort()

x2i_dict = {}
for i,x in enumerate(x_list):
    x2i_dict[x]=i


class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret


xn=len(x_list)
bit = BIT([0]*xn)

def bisectR(l,r):
    while r-l>1:
        if bit.sum((l+r)//2)>0:
            r = (l+r)//2
        else:
            l = (l+r)//2
    return r


ans = [0]*Q
for r in road:
    if r[2]==0:
        bit.add(x2i_dict[r[1]],1)
    elif r[2]==1:
        bit.add(x2i_dict[r[1]],-1)
    else:
        if bit.sum(xn-1)==0:
            ans[r[1]]=-1
        elif bit.sum(0)>0:
            ans[r[1]]=x_list[0]
        else:
            i = bisectR(0,xn-1)
            ans[r[1]] = x_list[i]
for a in ans:
    print(a)

### FIXED CODE ###

import sys

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

def main():
    N,Q = list(map(int,input().split()))

    road = []
    x_list = []

    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append([0,s-x,x])
        road.append([1,t-x,x])

    for i in range(Q):
        road.append([2,int(input()),i])

    from collections import defaultdict

    counter = defaultdict(int)
    counter[10**27] = 1
    ans = [0]*Q

    road.sort(key=lambda x:x[0])
    road.sort(key=lambda x:x[1])

    q = [10**27]

    from heapq import heappop,heappush

    for id,_,x in road:
        if id==0:
            heappush(q,x)
            counter[x]+=1
        elif id==1:
            counter[x]-=1
        else:
            while counter[q[0]]==0:
                heappop(q)
            #print(q)
            if q[0]<10**27:
                ans[x] = q[0]
            else:
                ans[x] = -1
    print("\n".join(map(str,ans)))

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

n,k,q =  map(int,input().split())
a = [int(input()) for i in range(q)]
b = 0

for l in range(1,n+1):
    b = 0
    for m in range(q):
        if l == a[m]:
            b += 1
    if k-(q-b) > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q =  map(int,input().split())
scores = [0]*n
b = 0
while b < q:
    ans = int(input()) - 1 #0からにする
    scores[ans] += 1
    b += 1
for x in scores:
    if k-(q-x) > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from sys import stderr
N = int(input())
a = [[int(e) - 1 for e in input().split()] for _ in range(N)]
next_index = [0] * N
nq = list(range(N))
result = 0
finished = 0
while nq:
  result += 1
  print("day = %d" % result, file = stderr)
  q = nq
  nq = []
  booked = [False] * N
  for player in q:
    if booked[player]:
      continue
    if next_index[player] == N - 1:
      continue
    opponent = a[player][next_index[player]]
    if booked[opponent]:
      continue
    if a[opponent][next_index[opponent]] != player:
      continue
    print('match %d vs %d' % (player, opponent), file = stderr)
    booked[player] = True
    booked[opponent] = True
    next_index[player] += 1
    next_index[opponent] += 1
    if next_index[player] == N - 1:
      finished += 1
    else:
      nq.append(player)
    if next_index[opponent] == N - 1:
      finished += 1
    else:
      nq.append(opponent)
if finished == N:
  print(result)
else:
  print(-1)


### FIXED CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]

s=sum(a)
ans=s
b=a[0]
for i in range(n-3):
	b=0
	for l in range(i+2):
		b+=a[l]
	c=s-b
	j=0
	k=0
	while k-b/2<0:
		k+=a[j]
		j+=1
	if k-b/2>b/2+a[j-1]-k:
		k-=a[j-1]
	x=min(k,b-k)
	y=max(k,b-k)
	j=-1
	k=0
	while k-c/2<0:
		k+=a[j]
		j-=1
	if k-c/2>c/2+a[j+1]-k:
		k-=a[j+1]
	z=min(k,c-k)
	w=max(k,c-k)
	t=max(y,w)-min(x,z)
	if ans>t:
		ans=t
print(ans)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]

s=[a[0]]
for i in range(n-1):
	s.append(s[i]+a[i+1])
ans=s[n-1]
j=0
k=2
for i in range(1,n-2):
	while abs(s[i]-2*s[j]) > abs(s[i]-2*s[j+1]):
		j=j+1
	while abs(s[n-1]-2*s[k]+s[i]) > abs(s[n-1]-2*s[k+1]+s[i]):
		k=k+1
	t=max(s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k])-min(s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k])
	if ans>t:
		ans=t
print(ans)
### BUGGY CODE ###

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

hst = []
btn = 0
cnt = 0

while not btn in hst and cnt <= 10**7:
    hst.append(btn)
    btn = a[btn]
    cnt += 1
    if btn == 1:
        print(cnt)
        exit()

print(-1)

### FIXED CODE ###

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

# if not 1 in a:
#     print(-1)

# hst = []
btn = 0
cnt = 0

while cnt <= 10**7:
    # hst.append(btn)
    btn = a[btn]
    cnt += 1
    if btn == 1:
        print(cnt)
        exit()

print(-1)
### BUGGY CODE ###

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

K = int(input())
S = input()
N = len(S)

MOD = 10 ** 9 + 7

anss = 0
for i in range(K + 1):
  p = comb(N + K - i - 1, N - 1, MOD) * pow(26, i, MOD) * pow(25, K - i, MOD) % MOD
  anss += p
  anss %= MOD
  
print(anss)

### FIXED CODE ###

K = int(input())
S = input()
N = len(S)

MOD = 10 ** 9 + 7

# 逆元を利用してcomb(nCk)をO(1)計算
# https://qiita.com/ophhdn/items/5622ac22cce8fc9432bf
n = N + K + 3
fac = [1] * (n + 1) 
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = (fac[j - 1] * j) % MOD

inv[n] = pow(fac[n], MOD-2, MOD)
for j in range(n - 1, -1, -1):
    inv[j] = (inv[j + 1] * (j + 1)) % MOD

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return (fac[n] * inv[n - r] * inv[r]) % MOD

ans = 0
for i in range(K + 1):
  p = comb(N + K - i - 1, N - 1) * pow(26, i, MOD) * pow(25, K - i, MOD) % MOD
  ans += p
  ans %= MOD
  
print(ans)
### BUGGY CODE ###

a, b, k = map(int, input().split())
print(*[i for i in range(a, b+1) if i < a+k or i > b-k])

### FIXED CODE ###

a, b, k = map(int, input().split())
print(*[i for i in range(a, b+1) if i < a+k or i > b-k], sep="\n")
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
dp = {}
for i in A:
    dp[i] = True
A.sort()
for i in range(N):
    if dp[A[i]]:
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                dp[A[j]] = False
counter = 0
for key in dp.keys():
    if dp[key]:
        counter += 1
print(counter)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]
maxA = max(A)
dp = {}
for i in range(1, maxA+1):
    dp[i] = True
for i in range(N):
    if dp[A[i]]:
        tmp = 2 * A[i]
        while maxA >= tmp:
            if dp[tmp]:
                dp[tmp] = False
            tmp += A[i]
counter = 0
t = Counter(A)
for i in range(N):
    if dp[A[i]] and t[A[i]] == 1:
        counter += 1
print(counter)
### BUGGY CODE ###

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

dp = [0]*N
for i in range(1, N):
    dp[i] = min(dp[j]+abs(hn[i]-hn[j]) for j in range(i-1, i-1-K, -1) if j >= 0)
print(dp[-1])


### FIXED CODE ###

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

dp = [0]*N
for i in range(1, N):
    dp[i] = min(dp[j]+abs(hn[i]-hn[j]) for j in range(i-1, i-1-K, -1) if j >= 0)
print(dp[-1])
### BUGGY CODE ###

s=input()
t=input()
st={}
for i in range(len(s)):
    if s[i]!=t[i]:
        si=s[i]
        ti=t[i]
        s=s.replace(si,'0')
        s=s.replace(ti,si)
        s=s.replace('0',ti)
print('Yes' if s==t else 'No')
#print(s,t)


### FIXED CODE ###

s=input()
t=input()
ns,nt=0,0
anss,anst=s,t
sl,tl=[],[]
for i in range(len(s)):
    if s[i] in sl:
        pass
    else:
        ns+=1
        sl.append(s[i])
        anss=anss.replace(s[i],str(ns))
    if t[i] in tl:
        pass
    else:
        nt+=1
        tl.append(t[i])
        anst=anst.replace(t[i],str(nt))
print('Yes' if anss==anst else 'No')
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list([int(a.index(i))+1 for i in range(1,n+1)])
for i in b:
    print(i,end=" ")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
d = dict(zip(a,range(1,n+1)))
for i in range(1,n+1):
    print(d[i],end=" ")
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    x = input()
    if x not in s:
        s.append(x)
print(len(s))

### FIXED CODE ###

n = int(input())
s = set(input() for i in range(n))
print(len(s))
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())
 
#output
import numpy as np
import bisect as bi
 
X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]
 
damage = np.zeros(N, int)
answer = 0
 
for i in range(N):
    if H[i] <= 0:
        continue
    else:
        J = (H[i]-1+A)//A
        damage[i] = J*A
        a = bi.bisect_right(X, X[i]+2*D)
        if a <= N-1:
            damage[a] = -J*A
    damage = np.cumsum(damage)
    answer += J
    H -= damage
    damage[i:a] = 0
 
print(answer)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())
 
#output
import numpy as np
import bisect as bi
 
X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]
 
damage = np.zeros(N+1, int)
answer = 0
power = 0
for i in range(N):
    power -= damage[i]
    J = (H[i]-1+A)//A
    if J <= power:
        continue
    else:
        a = bi.bisect_right(X, X[i]+2*D)
        damage[a] += J - power
        answer += J-power
        power = J
 
print(answer)
### BUGGY CODE ###

x,y=map(int,input().split())
if(x==y):print(-1)
else:
  i=1
  while(1):
    if((x*i)%y!=0):
      print(x*i)
      break

### FIXED CODE ###

x,y=map(int,input().split())
if(x%y==0):print(-1)
else:
  i=y
  while(1):
    if((x*i)%y!=0):
      print(x*i)
      break
    i+=1
### BUGGY CODE ###

a, b, k = map(int, input().split())

ans = []
for i in range(a, b+1):
  if i <= a+k-1 or i>=b-k+1:
    if i not in ans:
      ans.append(i)
      print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())

if b-a <= k:
  for i in range(a, b+1):
    print(i)
else:
  ans = []
  for i in range(a, a+k):
    if i not in ans:
      ans.append(i)
      print(i)
  for j in range(b-k+1, b+1):
    if j not in ans:
      print(j)
### BUGGY CODE ###

import math
# ????????§??????????????????????????????
def fact(n):
    sum = 0
    for i in range(1,n+1):
        sum += math.log(i)
    return math.exp(sum)
def fact2(n):
    return math.sqrt(2*math.pi*n)*(n/math.exp(1))**n

n = []
while True:
    try:
        tmp = int(input())
        if tmp == 0:
            break
        else:
            n.append(tmp)
    except EOFError:
        break

for i in range(len(n)):
    f = math.factorial(n[i])
    k = 0
    while True:
        if f % (10 ** k) != 0:
            print(k-1)
            break
        else:
            k += 1

### FIXED CODE ###

n = []
while True:
    try:
        tmp = int(input())
        if tmp == 0:
            break
        else:
            n.append(tmp)
    except EOFError:
        break

for i in range(len(n)):
    c = 0
    d = 5
    for j in range(1,n[i]+1):
        while d <= n[i]:
            c += (n[i]//d)
            d *= 5
    print(c)
### BUGGY CODE ###

n,m=map(int, input().split())
for i in range(m//n,0,-1):
    if m%i==0:
        print(i)
        break

### FIXED CODE ###

n,m=map(int, input().split())
from math import sqrt
d0=[]
for i in range(1,int(sqrt(m)+1)):
    if m%i==0:
        d0.append(i)
d=d0[:]
for di in reversed(d0):
    d.append(m//di)
for i in reversed(d):
    if i<=m//n:
        print(i)
        break
### BUGGY CODE ###

k = int(input())

ans = []
memo = 0
for i in range(k):
    memo = 10*memo + 7
    if memo % k == 0:
        ans.append(i)
print(-1 if not len(ans) else ans[0] + 1)


### FIXED CODE ###

k = int(input())

ans = -1
memo = 7 % k
a = 7 % k
for i in range(k):
    if a == 0:
        ans = i+1
        break
    a = (10*a+7) % k
print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
S = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s: S+=1
print(S)

### FIXED CODE ###

k,s=map(int,input().split())
print(sum(0<=s-y-z<=k for z in range(k+1) for y in range(k+1)))
### BUGGY CODE ###

n = int(input())

sList = list(map(int,input().split()))
sEdit = sorted(list(set(sList)),reverse=True)
res = 0
for i in sEdit:
  dcount = sList.count(i)//2
  if dcount >= 2 and res == 0:
    print(i*i)
    exit(0)
  elif dcount >= 1 and res == 0:
    res = i
  elif dcount >= 1 and res != 0:
    print(res*i)
    exit(0)

print(0)



### FIXED CODE ###

n = int(input())

sList = sorted(list(map(int,input().split())),reverse=True)
res = []
acc = False
for i in range(n-1):
  if acc:
    acc = False
  else:
      if sList[i] == sList[i+1]:
        res.append(sList[i])
        acc = True
      if len(res) == 2:
        print(res[0]*res[1])
        exit(0)

print(0)
### BUGGY CODE ###

N = int(input())
A = [str(input()) for i in range(N)]
A.sort()
B = list(set(A))
B.sort()
ans = [0 for _ in range(len(B))]
for i in range(len(B)):
  ans[i] = A.count(B[i])
i_max = [i for i, x in enumerate(ans) if(max(ans)==x)]
for i in range(len(i_max)):
  print(B[i_max[i]])

### FIXED CODE ###

import collections
 
N,*S = open(0).read().split()
C = collections.Counter(S)
 
i = C.most_common()[0][1]
print(*sorted([k for k,v in C.most_common() if v == i]), sep='\n')
### BUGGY CODE ###

N , M = map(int,input().split())
 
H = list(map(int,input().split()))
 
A = [0]*M
B = [0]*M
for i in range(M):
  A[i] ,B[i] = map(int,input().split())
 
 
count = 0
 
for i in range(1,N+1):
  flag = 0
  for m in range(M):
    if i == A[m] and H[i-1]<= H[B[m]-1]:

      flag = 1
      continue
    elif i == B[m] and H[i-1]<=H[A[m]-1]:

      flag = 1
      continue
  if flag:
    continue
  if not flag:

    count += 1
 

print(count)   

### FIXED CODE ###

N , M = map(int,input().split())
 
H = list(map(int,input().split()))
 
A = [0]*M
B = [0]*M
for i in range(M):
  A[i] ,B[i] = map(int,input().split())
 
 
S=[1]*N
 
 
for m in range(M):
  if H[A[m]-1] == H[B[m]-1]:
    S[A[m]-1] = 0
    S[B[m]-1] = 0
  elif H[A[m]-1] <= H[B[m]-1]:
    S[A[m]-1] = 0
  elif H[A[m]-1] >= H[B[m]-1]:
    S[B[m]-1] = 0
 
 
print(sum(S))
### BUGGY CODE ###


def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


#区間更新BIT(BITを2つ用意し、BITの長さをN+2で初期化しておくべし)
def bitaddR(l,r,w,bit1,bit2): #半開区間[l,r)にwを加える

    bitadd(l,-1*w*l,bit1)
    bitadd(r,w*r,bit1)
    bitadd(l,w,bit2)
    bitadd(r,-1*w,bit2)

def bitsumR(r,bit1,bit2): #半開区間[1,r)の区間和

    return bitsum(r,bit1) + r * bitsum(r,bit2)


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

bitA = [0] * (M+2)
bitB = [0] * (M+2)

len_LR = []

for i in range(N):

    l,r = map(int,input().split())
    len_LR.append([r-l,l,r])

len_LR.sort()
len_LR.append([float("inf"),0,float("inf")])
ind = 0
ns = N
ans = []

for d in range(M):

    d += 1

    while len_LR[ind][2]-len_LR[ind][1]+1 < d:

        bitaddR(len_LR[ind][1] , len_LR[ind][2]+1 , 1 ,bitA,bitB)
        ns -= 1
        ind += 1

    np = 0

    for i in range(d,M+1,d):
        np += bitsumR(i+1,bitA,bitB) - bitsumR(i,bitA,bitB)

    ans.append(ns + np)

print ("\n".join(map(str,ans)))


### FIXED CODE ###


def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(x,bit): #ind 1～aまでの和を求める
   
    ret = 0
    while x:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


#区間更新BIT(BITを2つ用意し、BITの長さをN+2で初期化しておくべし)
def bitaddR(l,r,w,bit1,bit2): #半開区間[l,r)にwを加える

    bitadd(l,-1*w*l,bit1)
    bitadd(r,w*r,bit1)
    bitadd(l,w,bit2)
    bitadd(r,-1*w,bit2)

def bitsumR(r,bit1,bit2): #半開区間[1,r)の区間和

    return bitsum(r,bit1) + r * bitsum(r,bit2)


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

BIT = [0] * (M+1)
dic = {}
for i in range(N):
    l,r = map(int,input().split())
    if r-l+1 not in dic:
        dic[r-l+1] = []
    dic[r-l+1].append([l,r])

ind = 0
ns = N
ans = []
for d in range(M):

    d += 1

    if d in dic:
        for L,R in dic[d]:

            bitadd(L , 1 ,BIT)
            bitadd(R+1 , -1 , BIT)
            ns -= 1

    nm = 0
    for i in range(d,M+1,d):
        
        nm += bitsum(i,BIT)
    ans.append(nm+ns)

print ("\n".join(map(str,ans)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(n):
  ans.append(str(a.index(i+1)+1))
print(' '.join(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
for i in range(n):
  ans[a[i]-1] = i + 1
print(*ans)
### BUGGY CODE ###

def readinput():
    h,w=map(int,input().split())
    smat=[]
    for _ in range(h):
        smat.append(input())
    return h,w,smat

def main(h,w,smat):
    tmat=[]
    for _ in range(h):
        t=[0 for tt in range(w)]
        tmat.append(t)
    #print(tmat)
    for i in range(h):
        s=smat[i]
        l=0
        r=s.find('#',l)
        #print(i,l,r)
        while(r>=0):
            for k in range(l,r):
                tmat[i][k]=r-l
            l=r+1
            if (l>=w):
                break
            r=s.find('#',l)
            #print(i,l,r)
        else:
            for k in range(l,w):
                tmat[i][k]=w-l
        #print(tmat[i])
    maxt=0
    for j in range(w):
        u=0
        b=u
        while b<h:
            #print(b,j)
            while b<h and smat[b][j]=='.':
                b+=1
            for k in range(u,b):
                maxt=max(maxt, tmat[k][j]+b-u-1)
            u=b+1
            b=u

    return maxt

if __name__=='__main__':
    h,w,smat=readinput()
    ans=main(h,w,smat)
    print(ans)


### FIXED CODE ###

def readinput():
    h,w=map(int,input().split())
    smat=[]
    for _ in range(h):
        smat.append(input())
    return h,w,smat

def main(h,w,smat):
    tmat=[]
    for _ in range(h):
        t=[0 for tt in range(w)]
        tmat.append(t)
    #print(tmat)
    for i in range(h):
        s=smat[i]
        l=0
        r=s.find('#',l)
        #print(i,l,r)
        while(r>=0):
            for k in range(l,r):
                tmat[i][k]=r-l
            l=r+1
            if (l>=w):
                break
            r=s.find('#',l)
            #print(i,l,r)
        else:
            for k in range(l,w):
                tmat[i][k]=w-l
        #print(tmat[i])
    maxt=0
    for j in range(w):
        u=0
        b=u
        while b<h:
            #print(b,j)
            while b<h and smat[b][j]=='.':
                b+=1
            for k in range(u,b):
                maxt=max(maxt, tmat[k][j]+b-u-1)
            u=b+1
            b=u

    return maxt

if __name__=='__main__':
    h,w,smat=readinput()
    ans=main(h,w,smat)
    print(ans)
### BUGGY CODE ###

from itertools import accumulate

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

S = [0] + list(accumulate(A))

memo = [[-1] * N for _ in range(N)]
def dp(L, R):
    if L == R:
        return 0
    if memo[L][R] >= 0:
        return memo[L][R]

    memo[L][R] = min(dp(L, c) + dp(c + 1, R) + S[R + 1] - S[L] for c in range(L, R))
    return memo[L][R]

print(dp(0, N - 1))

### FIXED CODE ###

from itertools import accumulate

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

S = [0] + list(accumulate(A))

memo = [[-1] * N for _ in range(N)]
def dp(L, R):
    if L == R:
        return 0
    if memo[L][R] >= 0:
        return memo[L][R]

    memo[L][R] = min(dp(L, c) + dp(c + 1, R) + S[R + 1] - S[L] for c in range(L, R))
    return memo[L][R]

print(dp(0, N - 1))
### BUGGY CODE ###

N = int(input())
X = int(input(), 2)

def rev(num, i):
  i = N - 1 - i
  return num ^ (1 << i)

for i in range(N):
  X = rev(X, i)
    
  fn = X
  cnt = 0
  
  while fn != 0:
    fn = fn % bin(fn).count("1")
    cnt += 1
  print(cnt)
  
  X = rev(X, i)

  
      

### FIXED CODE ###

N = int(input())
X = input()

X_int = int(X, 2)
cnt1 = bin(X_int).count('1')
pcXi01 = cnt1 + 1
pcXi10 = cnt1 - 1
zero_idx = N + 5
if cnt1 == 1:
  for i in range(N):
    if X[i] == '1':
      zero_idx = i

if pcXi10 < 1:
  pcXi10 = 1
Xmod01 = X_int % pcXi01
Xmod10 = X_int % pcXi10

tmp01 = [1]
tmp10 = [-1]
for i in range(N - 1):
  tmp01.append(tmp01[i]*2 % pcXi01)
  tmp10.append(tmp10[i]*2 % pcXi10)

init_n = [0] * N
next_n = [0] * N
for i in range(N):
  if X[i] == '0':
    next_n[i] = (Xmod01 + tmp01[N - 1 - i]) % pcXi01
  else:
    next_n[i] = (Xmod10 + tmp10[N - 1 - i]) % pcXi10

for i in range(N):
  fn = 0
  if i == zero_idx:
    print(0)
    continue

  n = next_n[i]
  fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)
### BUGGY CODE ###


def ruisekiseki(l):
    #関数バージョン
    lst = [1]
    s = 1
    for i,v in enumerate(l):
        lst.append(s * v)
        s *= v
    return lst


def main():
    n,k = map(int,input().split())
    test_scores = list(map(int,input().split()))
    r = ruisekiseki(test_scores)
    pre_score = r[k] // r[0]
    for i in range(k+1,n+1):
        #print(r[i] // r[i-k])
        if r[i] // r[i-k] > pre_score:
            print("Yes")
        else:
            print("No")
        pre_score = r[i] // r[i-k]





if __name__ == '__main__':
    main()


### FIXED CODE ###

#尺取り法的な……
#

def main():
    n,k = map(int,input().split())
    scores = [0] + list(map(int,input().split()))
    for i in range(k+1,n+1):
        if scores[i] > scores[i-k]:
            print("Yes")
        else:
            print("No")

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

import numpy as np

n = int(input())
ab = []

for _ in range(n):
    ab.append(list(map(int, input().split())))

a = np.array([x[0] for x in ab])
b = np.array([x[1] for x in ab])

a = a[::-1]
b = b[::-1]

ans = 0
i = 0
for x, y in zip(a, b):
    mod = x % y
    if mod == 0:
        continue
    else:
        add = y - mod
        ans += add
        a[i:] += add
    i += 1

print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())
ab = []

for _ in range(n):
    ab.append(list(map(int, input().split())))

a = np.array([x[0] for x in ab])
b = np.array([x[1] for x in ab])


ans = 0
for x, y in zip(a[::-1], b[::-1]):
    mod = (x + ans) % y
    if mod == 0:
        continue
    else:
        add = y - mod
        ans += add

print(ans)