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

from collections import deque
import time     #ズルです…
start = time.time()
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
z = 0
Atmp = []
for i in range(10**6):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
            else:
                z += 1
        else:
            t += 1
    if t == N:
        break
    if t+z == N and i != 0:
        ans = 0
        break
    z = 0
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
    aida = time.time()
    if aida-start > 1.9:
        print(N*(N-1)//2)       #ズル
        exit()
print(ans-1)

### FIXED CODE ###

from collections import deque
import time     #ズルです…
start = time.time()
N = int(input())
A = [deque(list(map(int, input().split()))) for _ in range(N)]
ans = 0
t = 0
z = 0
Atmp = []
for i in range(10**6):
    for k in range(N):
        if A[k] != deque([]):
            if A[k][0] == 0:
                A[k].popleft()
            else:
                z += 1
        else:
            t += 1
    if t == N:
        break
    if t+z == N and i != 0:
        ans = 0
        break
    z = 0
    t = 0
    for j in range(N):
        if A[j]:
            tmp = A[j][0]
        else:
            continue
        if tmp-1 > j and A[tmp-1][0] -1 == j:
            A[j][0] = 0
            A[tmp-1][0] = 0
    ans += 1
    aida = time.time()
    if aida-start > 1.7:
        print(N*(N-1)//2)       #ズル
        exit()
print(ans-1)
### BUGGY CODE ###

import sys
from itertools import combinations
try:
    from scipy.special import comb
except ImportError:
    from scipy.misc import comb

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M, K = map(int, input().split())
    # The number of times that pieces are located on certain two tiles.
    num = int(comb(N*M-2, K-2, exact=True))

    ans = 0
    # Column-wise distance
    for a, b in combinations(range(M), 2):
        ans += abs(a - b) * N**2 * num
        ans %= MOD

    # Row-wise distance
    for a, b in combinations(range(N), 2):
        ans += abs(a - b) * M**2 * num
        ans %= MOD

    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys
from itertools import combinations

def comb_mod(n, r, MOD=10**9+7):
    if n < 0 or r < 0 or n < r:
        return 0

    factrial = [1] * (n+1)
    for k in range(1, n+1):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (n+1)
    fact_inv[n] = pow(factrial[n], MOD - 2, MOD)
    for k in range(n-1, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD


def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M, K = map(int, input().split())

    # The number of times that pieces are located on certain two tiles.
    num = comb_mod(N*M-2, K-2)

    ans = 0
    # Column-wise distance
    for i in range(M):
        ans += i * (M - i) * N**2 * num
        ans %= MOD

    # Row-wise distance
    for i in range(N):
        ans += i * (N - i) * M**2 * num
        ans %= MOD

    return ans


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

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
xx = inpl()
L = int(input())
dd = []
for i,x in enumerate(xx):
    ind = bisect.bisect_right(xx,x+L)
    dd.append(ind-1)

Q = int(input())
for i in range(Q):
    a,b = inpl()
    a,b = min(a,b)-1,max(a,b)-1
    tmp = 0
    while a < b:
        a = dd[a]
        tmp += 1
    print(tmp)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
xx = inpl()
L = int(input())

K = N.bit_length()
db_r = [[0]*K for i in range(N)]
for i,x in enumerate(xx):
    ind = bisect.bisect_right(xx,x+L)
    db_r[i][0] = ind-1

for k in range(1,K):
    for i in range(N):
        db_r[i][k] = db_r[db_r[i][k-1]][k-1]

def check(a,b,d):
    L = d.bit_length()
    for k in range(L):
        if d & (1<<k):
            a = db_r[a][k]
    return a >= b

Q = int(input())
for i in range(Q):
    a,b = inpl()
    a -= 1
    b -= 1
    a,b = min(a,b),max(a,b)
    OK = N
    NG = 0
    while OK-NG>1:
        mid = (OK+NG)//2
        if check(a,b,mid): OK = mid
        else: NG = mid
    print(OK)
### BUGGY CODE ###

k = int(input())

if k % 2 == 0:
  print(-1)
  exit()

a = 7
ans = 0
for i in range(10**7):
  if a % k == 0:
    ans = i + 1
    break
  else:
    a = a*10 + 7
    ans = i + 1


print(ans)


### FIXED CODE ###

k = int(input())

if k % 2 == 0 or k % 5 == 0:
  print(-1)
  exit()

a = 7
ans = 0
for i in range(10**7):
  a = a % k
  if a % k == 0:
    ans = i + 1
    break
  else:
    a = a*10 + 7
    ans = i + 1


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

N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
B = [A[0]]
for i in range(1, N):
    j = 0
    while j<len(B):
        if A[i] > B[j]:
            B[j] = A[i]
            break
        j+=1
    else:
        B.append(A[i])

print(len(B))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
B = [A[0]]
for i in range(1, N):

    if A[i] > B[-1]:#2分探索でどこかに入れる
        sm = -1
        la = len(B)-1
        
        while sm+1<la:
            mi = (sm+la)//2
            if B[mi]<A[i]:
                la=mi
            else:
                sm=mi
        B[la]=A[i]
        
    else:#Bに追加
        B.append(A[i])

print(len(B))
### BUGGY CODE ###

import collections
n = int(input())
a = [int(i) for i in input().split()]
cola = collections.Counter(a)
mult = [True] * (10**6+1)
seta = set(a)

for s in seta:
  tmp = s * 2
  while tmp <= 10 ** 6:
    mult[tmp] = False
    tmp += s
  
ans = 0
for s in seta:
  if cola[s] == 1 and mult[s] == True:
    ans += 1
    
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
m = [True] * (10**6+1)
s = list(set(a))
for u in s:
    t = u * 2
    while t <= 10 ** 6:
        m[t] = False
        t += u
r = 0
for u in s:
    if c[u] == 1 and m[u] == True:
        r += 1
print(r)
### BUGGY CODE ###

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

def A(N,a):
    b = []
    for i in range(N):
        b.append(a.index(i+1)+1)
    b = ' '.join(map(str, b))
    print(b)  
A(N,a)

### FIXED CODE ###

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

K = int(input())

def gcd_(a, b):
    if a < b:  a, b = b, a
    if b == 0:  return a
    return gcd_(b, a % b)

def gcd(l):
    ans = l[0]
    for i in l:  ans = gcd_(ans, i)
    return ans

ans = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            ans += gcd([i, j, k])

print(int(ans))

### FIXED CODE ###

K = int(input())

def gcd_(a, b):
    if a < b:  a, b = b, a
    if b == 0:  return a
    return gcd_(b, a % b)

def gcd(l):
    ans = l[0]
    for i in l:  ans = gcd_(ans, i)
    return ans

ans = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            ans += gcd([i, j, k])

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

def gcd(x, y):
    a_x = list()
    a_y = list()

    for i in range(1, x+1):
        if x % i == 0:
            a_x.append(i)

    for i in range(1, y+1):
        if y % i == 0:
            a_y.append(i)

    a_cd = list(set(a_x).intersection(set(a_y)))

    return max(a_cd)

if __name__ == "__main__":
    x, y = map(int, input().split())
    if x > y:
        tmp = x
        x = y
        y = tmp
    print(gcd(x, y))

### FIXED CODE ###

def gcd(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp

    while y > 0:
        r = x % y
        x = y
        y = r

    return x

if __name__ == "__main__":
    x, y = map(int, input().split())
    print(gcd(x, y))
### BUGGY CODE ###

import collections
S = input()[::-1]
N = len(S)
mod = 2019

x = [0] * N
x[0] = int(S[0]) % mod

for i in range(1, N):
    x[i] = ((10 ** i) * int(S[i]) + x[i - 1]) % mod

d = collections.Counter(x)
target = [v for k, v in d.items() if v > 1]

ans = 0
ans += sum([t * (t - 1) // 2 for t in target])

if 0 in d.keys():
    ans += d[0] * (d[0] - 1) // 2 + d[0]
    
print(ans)

### FIXED CODE ###

import collections
S = input()[::-1]
N = len(S)
mod = 2019

ans = 0
x = [0] * N
x[0] = int(S[0]) % mod
ruijo = 10

for i in range(1, N):
    x[i] = (ruijo * int(S[i]) + x[i - 1]) % mod
    if x[i] % mod == 0:
        ans += 1
    ruijo *= 10
    ruijo %= mod
    
d = collections.Counter(x)

for i in d.values():
    ans += i * (i - 1) // 2
    
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0
    for i in range(0, N):
        b = 0
        for j in range(i, N):
            if j==i:
                b = A[i]
            else:
                b = b + A[j]
            if b == 0:
                count += 1
    return count

if __name__ == '__main__':
    print(main())



### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0

    s = [0 for _ in range(N+1)]
    for i in range(N):
        s[i+1] = s[i] + A[i]
    s.sort()
    n = 1
    for i in range(N):
        if s[i+1] == s[i]:
            n+=1
        else:
            count += n*(n-1)//2
            n = 1
    count += n*(n-1)//2
    return count

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

import sys

def INPUT(): return sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 9)


def main():
    S = INPUT()
    fall_point = []
    split_point = [0]
    last_S = [0 for i in range(len(S))]

    for i, s in enumerate(S):
        if not i == len(S) - 1:
            if s + S[i+1] == 'RL':
                fall_point.append(i)
            elif s + S[i+1] == 'LR':
                split_point.append(i+1)
        else:
            split_point.append(i+1)

    for i in range(len(split_point)-1):
        sub_len = split_point[i+1] - split_point[i]

        if sub_len % 2 == 0:
            last_S[fall_point[i]] = sub_len // 2
            last_S[fall_point[i] + 1] = sub_len // 2
        else:
            if (split_point[i+1] - fall_point[i]) % 2 == 0:
                last_S[fall_point[i]] = sub_len // 2
                last_S[fall_point[i] + 1] = sub_len // 2 + 1
            else:
                last_S[fall_point[i]] = sub_len // 2 + 1
                last_S[fall_point[i] + 1] = sub_len // 2

    answer = ""

    for ls in last_S:
        answer += str(ls) + " "

    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
 
def INPUT(): return sys.stdin.readline().strip()
 
sys.setrecursionlimit(10 ** 9)
 
 
def main():
    S = INPUT()
    fall_point = []
    split_point = [0]
    N = len(S)
    last_S = [0] * N
 
    for i in range(N):
        if not i == N - 1:
            if S[i:i+2] == 'RL':
                fall_point.append(i)
            elif S[i:i+2] == 'LR':
                split_point.append(i+1)
        else:
            split_point.append(i+1)
 
    for i in range(len(split_point)-1):
        sub_len = split_point[i+1] - split_point[i]
 
        if sub_len % 2 == 0:
            last_S[fall_point[i]] = sub_len // 2
            last_S[fall_point[i] + 1] = sub_len // 2
        else:
            if (split_point[i+1] - fall_point[i]) % 2 == 0:
                last_S[fall_point[i]] = sub_len // 2
                last_S[fall_point[i] + 1] = sub_len // 2 + 1
            else:
                last_S[fall_point[i]] = sub_len // 2 + 1
                last_S[fall_point[i] + 1] = sub_len // 2
 
    print(" ".join(map(str, last_S)))
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, m = map(int,input().split())
l = []
for i in range(m):
    p,s=map(str,input().split())
    l.append([int(p),s])

ac = 0 
wa = 0
    
for i in range(m):
    if l[i][1] == "WA":
        flag = True
        for j in range(0,i):
            if l[j][1] == "AC" and l[j][0] == l[i][0]:
                flag = False
                break
        if flag:
            wa += 1
        
    if l[i][1] == "AC":
        flag = True
        for j in range(0,i):
            if l[j][1] == "AC" and l[j][0] == l[i][0]:
                flag = False
                break
        if flag:
            ac += 1

print(ac,wa)

### FIXED CODE ###

n,m = map(int, input().split())

a = [0]*n
b = [False]*n
for i in range(m):
    p,s = input().split()
    p = int(p) - 1
    if s == 'AC':
        b[p] = True
    elif b[p] == False:
        a[p] += 1

ac = b.count(True)
wa = 0
for i in range(n):
    if b[i] == True:
        wa += a[i]
print(ac,wa)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
G = dict([[i, []] for i in range(N)])
for _ in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)

dp = [-1] * N


def rec(v):
    if dp[v] >= 0:
        return dp[v]
    if len(G[v]) == 0:
        return 0

    ret = -1
    for nv in G[v]:
        ret = max(ret, rec(nv) + 1)

    return ret


print(max([rec(v) for v in range(N)]))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
G = dict([[i, []] for i in range(N)])
for _ in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)

dp = [-1] * N


def rec(v):
    if dp[v] >= 0:
        return dp[v]
    if len(G[v]) == 0:
        return 0

    ret = -1
    for nv in G[v]:
        ret = max(ret, rec(nv) + 1)

    dp[v] = ret
    return ret


print(max([rec(v) for v in range(N)]))
### BUGGY CODE ###

N = int(input())
l = [False] * (N + 1)
import collections
def count(n):
  ret = 0
  i = 1
  while i*i <= n:
    if n % i == 0:
      ret += 1
      if i != n // i:
        ret += 1
    i += 1
  return ret


ans = 1
l[0] = True
l[1] = True
if N==1:
  print(ans)
else:
  for i in range(2,N+1):
    if l[i]:
      continue
    x = count(i)
    ans += x * i
    l[i] = True

  print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
  x = N//i
  ans += i * x * (x + 1) // 2
  
print(ans)
### BUGGY CODE ###

from math import factorial
def nc2(n):
	if n<2:
		return 0
	else:
		return (n*(n-1))//2

n = int(input())
arr = list(map(int,input().split()))
d = {}
for i in range(n):
	try:
		d[arr[i]].append(i)
	except KeyError:
		d[arr[i]] = [i]

done = {}
for i in range(n):
	try:
		if done[arr[i]] > -1:
			continue
	except KeyError:
		ans = 0
		for j in d.keys():
			if j == arr[i]:
				ans+= nc2(len(d[j])-1)
			else:
				ans+= nc2(len(d[j]))
		done[arr[i]] = int(ans)

for i in arr:
	print(done[i])
	



### FIXED CODE ###

from math import factorial
def nc2(n):
	if n<2:
		return 0
	else:
		return (n*(n-1))//2

n = int(input())
arr = list(map(int,input().split()))
d = {}
for i in range(n):
	try:
		d[arr[i]].append(i)
	except KeyError:
		d[arr[i]] = [i]

pick2 = {}
pick1 = {}
for i in d.keys():
	pick2[i] = nc2(len(d[i]))
	pick1[i] = nc2(len(d[i])-1)

sum_pick2 = sum(pick2.values())

done = {}

for i in d.keys():
	done[i] = (sum_pick2 - pick2[i] + pick1[i])

for i in arr:
	print(done[i])
### BUGGY CODE ###

N, Q = (int(x) for x in input().split())
S = input()
lr = [[0 for i in range(2)] for j in range(Q)]
ans = []
for i in range(Q):
    # lr[i][0], lr[i][1] = (int(x) for x in input().split())
    l, r = (int(x) for x in input().split())
    l -= 1
    r -= 1
    num = 0
    for j in range(l, r):
        if S[j:j+2] == 'AC':
            num += 1
    ans.append(num)
for i in range(Q):
    print(ans[i])


### FIXED CODE ###

N, Q = (int(x) for x in input().split())
S = input()

a_loc = [0] * (N + 1)
for i in range(N):
    a_loc[i+1] = a_loc[i] + (1 if S[i:i+2] == 'AC' else 0)

ans = [0] * Q
for i in range(Q):
    l, r = (int(x) for x in input().split())
    ans[i] = a_loc[r-1] - a_loc[l-1]
    
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit
from numba import jit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

@jit
def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

col = m
for i in range(n-1,-1,-1):
    now = col
    now *= combination(n-1,i)
    if i <= k:
        point += now%mod
    col *= m-1
    col %= mod

print(point%mod)

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

def prepare(n, MOD=mod):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs
facts, invs = prepare(n, mod)
for i in range(n-1,-1,-1):
    now = m
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    now *= wariate%mod

    now *= facts[n-1]*invs[n-1-i]*invs[i]
    if i <= k:
        point += now%mod

print(point%mod)
### BUGGY CODE ###

mod = 10**9 + 7
def add(a,b):#mod下の加算
    return (a+b)%mod

N,K = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
Slen = len(S);Tlen=len(T)
DP = [[0 for j in range(Tlen)] for i in range(Slen)]#DP[i][j]は、Sのi文字目、Tのj文字目までで一致する部分和
DP[0][0] = 1 + (S[0] == T[0])
for i,s in enumerate(S):
    for j,t in enumerate(T):
        if i==0 and j==0:continue
        if s == t:
            if i==0:
                DP[i][j]=DP[i][j-1]+1
            elif j==0:
                DP[i][j]=DP[i-1][j]+1
            else:
                DP[i][j]=(DP[i-1][j]+ DP[i][j-1])%mod
        else:
            if i==0:
                DP[i][j]=DP[i][j-1]
            if j==0:
                DP[i][j]=DP[i-1][j]
            else:
                DP[i][j]=(DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1])%mod
print(DP[Slen-1][Tlen-1]%mod)
            

### FIXED CODE ###

mod = 10**9 + 7
def add(a,b):#mod下の加算
    return (a+b)%mod

N,K = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
Slen = len(S);Tlen=len(T)
DP = [[0 for j in range(Tlen)] for i in range(Slen)]#DP[i][j]は、Sのi文字目、Tのj文字目までで一致する部分和
DP[0][0] = 1 + (S[0] == T[0])
for i,s in enumerate(S):
    for j,t in enumerate(T):
        if i==0 and j==0:continue
        if s == t:
            if i==0:
                DP[i][j]=DP[i][j-1]+1
            elif j==0:
                DP[i][j]=DP[i-1][j]+1
            else:
                DP[i][j]=(DP[i-1][j]+ DP[i][j-1])%mod
        else:
            if i==0:
                DP[i][j]=DP[i][j-1]
            if j==0:
                DP[i][j]=DP[i-1][j]
            else:
                DP[i][j]=(DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1])%mod
print(DP[Slen-1][Tlen-1]%mod)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    S = readline().rstrip()
    N = 13
    dp = [0] * 13  # dp[k]: 13で割った余りがkのパターン数
    dp[0] = 1
    
    mul = 1
    for i in range(len(S)-1, -1, -1):
        next_dp = [0] * N
        s = S[i]
        if s == '?':
            for k in range(10):
                for j in range(N):
                    next_dp[(k * mul + j) % N] += dp[j]
                    next_dp[(k * mul + j) % N] %= MOD
        else:
            k = int(s)
            for j in range(N):
                next_dp[(k * mul + j) % N] += dp[j]
                next_dp[(k * mul + j) % N] %= MOD
        mul *= 10
        mul %= N
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    S = readline().rstrip()
    N = 13
    dp = [0] * 13  # dp[k]: 13で割った余りがkのパターン数
    dp[0] = 1
    
    mul = 1
    for s in S[::-1]:
        next_dp = [0] * N
        if s == '?':
            for k in range(10):
                for j in range(N):
                    next_dp[(k * mul + j) % N] += dp[j]
                    next_dp[(k * mul + j) % N] %= MOD
        else:
            k = int(s)
            for j in range(N):
                next_dp[(k * mul + j) % N] += dp[j]
                next_dp[(k * mul + j) % N] %= MOD
        mul *= 10
        mul %= N
        dp = next_dp

    print(dp[5])

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

def bfs(sx, sy):
    for dx, dy in nb:
        nx = sx + dx
        ny = sy + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w:
            if grid[nx][ny] == "#":
                darker[sx][sy] = True
                break
 
 
h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
ans = 0
 
while True:
    darker = [[False] * w for _ in range(h)]
    flag = False
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                bfs(i, j)
    for i in range(h):
        for j in range(w):
            if darker[i][j]:
                grid[i][j] = "#"
            flag = flag or darker[i][j]
    if not (flag):
        break
    ans += 1
print(ans)

### FIXED CODE ###

from collections import deque
 
H, W = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))
            c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
    y, x = q.popleft()
    for dy, dx in D:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and c[ny][nx] == -1:
            q.append((ny, nx))
            c[ny][nx] = c[y][x]+1
print(max([max(l) for l in c]))
### BUGGY CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7
def combination(N,K):
    bunsi = 1
    bunbo = 1
    for i in range(K):
        bunsi = bunsi*(N-i)%mod
        bunbo = bunbo*(i+1)%mod
    return bunsi*pow(bunbo,mod-2,mod)%mod
all_num = (2**n-1)%mod
ans = all_num-combination(n,a)-combination(n,b)
print(ans%mod)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7
def combination(N,K):
    bunsi = 1
    bunbo = 1
    for i in range(K):
        bunsi = bunsi*(N-i)%mod
        bunbo = bunbo*(i+1)%mod
    return bunsi*pow(bunbo,mod-2,mod)%mod
all_num = pow(2,n,mod)-1
ans = all_num-combination(n,a)-combination(n,b)
print(ans%mod)
### BUGGY CODE ###

n = int(input())
s = input()
print(min(s[:i].count('#') + s[i:].count('.') for i in range(n+1)))

### FIXED CODE ###

n = int(input())
s = input()
m = s.count('.')
c = (0, m)
for i in range(n):
    if s[i] == '#':
        c = (c[0]+1, c[1])
    else:
        c = (c[0], max(c[1]-1, 0))
    m = min(c[0] + c[1], m)
print(m)