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

N = int(input())
S = input()
import numpy as np
ans = 0
for i in range(0, N):
    for j in range(i, N):
        if i ==j or S[i] == S[j]:
            continue
        s = ['R', 'G', 'B']
        s.remove(S[i])
        s.remove(S[j])
        k_s = np.where(np.array(list(S[j:])) == s[0])[0] + j
        for k in k_s:
            if j == k or S[j] == S[k]:
                continue
            elif j-i != k-j and S[i] != S[k]:
                ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N):
    for j in range(i + 1, N):
        k = j - i + j
        if k < N:
            if {S[i], S[j], S[k]} == {"R", "G", "B"}:
                ans -= 1
print(ans)
### BUGGY CODE ###

# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():

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

    cnt=0
    for i in range(N):
        if P[i]==min(P[:i+1]):
            cnt+=1
    print(cnt)

resolve()

### FIXED CODE ###

def resolve():

    N=int(input())
    P=list(map(int,input().split()))
    pmin=P[0]
    cnt=0
    for i in range(N):
        if P[i]<=pmin:
            cnt+=1
            pmin=P[i]
    print(cnt)

resolve()
### BUGGY CODE ###

from functools import reduce
import fractions
n=int(input())
a=list(map(int,input().split()))
c=a[1:]
gcdc=reduce(fractions.gcd,c)
d=[gcdc]
for i in range(1,n):
    b=a[:i]+a[i+1:]
    gcd=reduce(fractions.gcd, b)
    d.append(gcd)
print(max(d))

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
ans=1
l=[0]*(n+1)
r=[0]*(n+1)
for i in range(n):
    l[i]=gcd(l[i-1],a[i])
for i in reversed(range(n)):
    r[i]=gcd(r[i+1],a[i])
for i in range(n):
    if gcd(l[i-1],r[i+1])>ans:
        ans=gcd(l[i-1],r[i+1])
print(ans)
### BUGGY CODE ###

NK=input().split()
N=int(NK[0])
K=int(NK[1])
Hlis=list(map(int,input().split()))

if K>=N:
    print(0)
else:
    for i in range(K):
        Hlis[Hlis.index(max(Hlis))]=0
    print(sum(Hlis))



### FIXED CODE ###

NK=input().split()
N=int(NK[0])
K=int(NK[1])
Hlis=list(map(int,input().split()))
ans=0

if K>=N:
    print(0)
else:
    Hlis.sort()
    for i in range(N-K):
        ans+=Hlis[i]
    print(ans)
### BUGGY CODE ###

S=input()
N=len(S)
childs=[1]*N
result=[0]*N

for i in range(N):
  if S[i]=="R": 
    j = i
    count = 0
    for j in range(j+1,N):
      count = count + 1
      if S[j] == "L":
        if count & 1 == 0:
          result[j] = result[j] + 1
        else:
          result[j-1] = result[j-1] + 1
        break
  else:
    j = i
    count = 0
    for j in range(j-1,-1,-1):
      count = count + 1
      if S[j] == "R":
        if count & 1 == 0:
          result[j] = result[j] + 1
        else:
          result[j+1] = result[j+1] + 1
        break

print(" ".join(map(str, result)))


### FIXED CODE ###

s=input()
ans=[0]*len(s)
import itertools
i=0
for key,g in itertools.groupby(s):
  num=len(list(g))
  if key=="R":
    i+=num
    ans[i-1]+=(num//2+(num%2>0))
    ans[i]+=num//2
  elif key=="L":
    ans[i-1]+=num//2
    ans[i]+=(num//2+(num%2>0))
    i+=num
  if i>=len(ans):
    break
print(*ans)
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N,K = LI()
    P = LI()
    # Pk_max_idx = numpy.argmax(numpy.convolve(P,numpy.ones(K)/K,mode="valid"))
    # Pk_max_idx = (numpy.max(numpy.convolve(P,numpy.ones(K)/K,mode="valid"))+1)*(K/2)
    # print((sum(P[Pk_max_idx:Pk_max_idx+K])+K)/2)
    print((numpy.max(numpy.convolve(P,numpy.ones(K)/K,mode="valid"))+1)*(K/2))

main()



### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string,scipy
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N,K = LI()
    P = LI()
    Pe = [(v+1)/2 for v in P]
    P_ms = numpy.cumsum(Pe)
    if K==N:print("{:.12f}".format(sum(Pe)));exit(0)
    ans = 0
    for i in range(K,N):
        ans = max(ans,P_ms[i]-P_ms[i-K])
    print("{:.12f}".format(ans))
main()
### BUGGY CODE ###

import math
A, B = map(int, input().split())

def is_prime(n):
  if n == 1: return False

  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False

  return True

cf=[]
cnt = 0
for i in range(1,min(A,B)+1):
  if A % i == 0 and B % i == 0:
    cf.append(i)
    if is_prime(i) == True:
      cnt += 1

print(cnt+1)

### FIXED CODE ###

from fractions import gcd

def prime_factorize(n):
  factor = []
  for i in range(2, int(n**0.5)+1):
    while n % i == 0:
      n //= i
      factor.append(i)
  if n != 1:
    factor.append(n)
  return factor

A, B = map(int, input().split())
N = gcd(A, B)
l = set(prime_factorize(N))
print(len(l)+1)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
for n in range(N):
    res = True
    for i in range(n):
        if P[n] > P[i]:
            res = False
            break
    if res:
        cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
res = float('Inf')
for n in range(N):
    if P[n] < res:
        res = P[n]
        cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
S = list(input())
count_list = []
for i in range(N):
  count1 = len([S[j] for j in range(N) if j < i and S[j] == "W" ])
  count2 = len([S[i] for j in range(N) if i < j and S[j] == "E"])
  count = count1 + count2
  count_list.append(count)
print(min(count_list))

### FIXED CODE ###

N = int(input())
S = list(input())
count_E = S.count("E")
count_W = 0
ans = count_E
for i in range(N):
    if S[i] == "E":
        count_E -= 1
    if S[i-1] == "W" and i != 0:
        count_W += 1
    if count_E + count_W < ans :
        ans = count_E + count_W
print(ans)
### BUGGY CODE ###

x, y, z, k = [int(i) for i in input().split()]
p = [int(a) for a in input().split()]
q = [int(b) for b in input().split()]
r = [int(c) for c in input().split()]
p = sorted(p, reverse=True)
q = sorted(q, reverse=True)
r = sorted(r, reverse=True)
pqr = []
for a in range(len(p)):
    if a+1 > k:
        continue
    for b in range(len(q)):
        if b+1 > k:
            continue
        elif (a+1)*(b+1) > k:
            continue
        for c in range(len(r)):
            if c+1 > k:
                continue
            elif (a+1)*(c+1) > k:
                continue
            elif (b+1)*(c+1) > k:
                continue
            elif (a+1)*(b+1)*(c+1) > k:
                continue
            pqr.append(p[a] + q[b] + r[c])
pqr = sorted(pqr, reverse=True)
for i in range(k):
    print(pqr[i])

### FIXED CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    if a+1 > K:
        break
    for b in range(len(B)):
        if b+1 > K:
            break
        elif (a+1)*(b+1) > K:
            break
        for c in range(len(C)):
            if c+1 > K:
                break
            elif (a+1)*(c+1) > K:
                break
            elif (b+1)*(c+1) > K:
                break
            elif (a+1)*(b+1)*(c+1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

from collections import Counter
n = int(input())
anslist = []
for i in range(n):
    s = input()
    c = Counter(s)
    anslist.append(c)
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        if anslist[i] == anslist[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
ans = []
cnt = 0
for i in range(n):
    s = input()
    l = list(s)
    l.sort()
    ans.append("".join(l))
c = Counter(ans)


for i in c.values():
    cnt += i*(i-1)//2

print(cnt)
### BUGGY CODE ###

# coding:utf-8

INF = float('inf')


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


N, x = inpl()
A = inpl()

min_index = A.index(min(A))
B = A[min_index:] + A[:min_index]

cost = [[INF] * N for i in range(N)]
for i in range(N):
    cost[i][0] = B[i]

for i in range(N):
    for magic in range(1, N):
        cost[i][magic] = min(cost[i][magic], min(B[max(0, i - magic)], cost[i][magic - 1]))

ans = INF
for magic in range(N):
    tmp = 0
    for i in range(N):
        tmp += cost[i][magic]
    ans = min(ans, tmp + magic * x)

print(ans)

### FIXED CODE ###

# coding:utf-8

INF = float('inf')


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


N, x = inpl()
A = inpl()

min_cost_s = 0
tmp = INF
for i in range(N):
    if A[i] < tmp:
        min_cost_s = i
        tmp = A[i]

A = A[min_cost_s:] + A[:min_cost_s]
B = [A[i] for i in range(N)]

ans = INF
for shift in range(N):
    for i in range(N):
        if i - shift >= 0:
            B[i] = min(B[i], A[i - shift])
    # print(B)

    ans = min(ans, shift * x + sum(B))

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

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

S_list = list(S)

r = 1
a = []
b = []

for i in range(Q):
    q = input().split()
    if q[0] == '1':
        r *= -1
        continue
    elif len(q) == 3:
        if q[1] == '1':
            if r == -1:
                b.append(q[2])
            else:
                a.insert(0, q[2])
        else:
            if r == -1:
                a.insert(0, q[2])
            else:
                b.append(q[2])
                
answer = a + S_list + b

if r == -1:
    answer = answer[::-1]
    
print(''.join(answer))

### FIXED CODE ###

from collections import deque

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

S_list = list(S)

r = 1
a = []
b = []
d = deque(a)

for i in range(Q):
    q = input().split()
    if q[0] == '1':
        r *= -1
        continue
    elif len(q) == 3:
        if q[1] == '1':
            if r == -1:
                b.append(q[2])
            else:
                d.appendleft(q[2])
        else:
            if r == -1:
                d.appendleft(q[2])
            else:
                b.append(q[2])
                
answer = list(d) + S_list + b

if r == -1:
    answer = answer[::-1]
    
print(''.join(answer))
### BUGGY CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    e3 = [[] for _ in range(n)]
    for i in range(n):
        items = set(e[i])
        for _ in range(2):
            nxt = set()
            for __ in items:
                nxt |= set(e[__])
            items = nxt
        items -= {i}
        e3[i] = list(items)

    visited = [True for _ in range(n)]

    ans = -1
    crnt = set(e3[s])
    if t in crnt:
        print(1)
        exit()

    cnt = 1
    while crnt:
        cnt += 1
        nxt = set()
        for ci in crnt:
            for ti in e3[ci]:
                if visited[ti]:
                    visited[ti] = False
                    nxt.add(ti)
        crnt = nxt
        if t in crnt:
            print(cnt)
            exit()

    print(-1)





if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [[True] * 3 for _ in range(n)]

    que = collections.deque()
    que.append([0, s])
    visited[s][0] = False
    cnt = 0
    ans = -1
    flg = True

    while que and flg:
        cnt += 1
        for _ in range(len(que)):
            i, q = que.popleft()
            for ei in e[q]:
                tmp = (i + 1) % 3
                if tmp == 0 and ei == t:
                    ans = cnt // 3
                    flg = False
                    break
                elif visited[ei][tmp]:
                    visited[ei][tmp] = False
                    que.append([tmp, ei])

    print(ans)


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

n = int(raw_input())

li = []
for i in range(n):
    cmd = raw_input().split()
    if cmd[0] == 'insert':
        li.insert(0,cmd[1])
    elif cmd[0] == 'delete':
        try:
            li.remove(cmd[1])
        except:
            pass
    elif cmd[0] == 'deleteFirst':
        li.pop(0)
    elif cmd[0] == 'deleteLast':
        li.pop()
for e in li:
    print e,

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    
    k = int(input())
    s = input()
    n = len(s)
    mod = 10**9+7
    p25 = [0]*(k+1)
    p26 = [0]*(k+1)
    c = [0]*(k+1)

    p25[0], p26[0] = 1, 1
    c[0]= 1
    for i in range(1, k+1):
        p25[i] = p25[i-1]*25
        p25[i] %= mod
        p26[i] = p26[i-1]*26
        p26[i] %= mod
        c[i] = (n+i-1)*c[i-1]
        c[i] *= pow(i, mod-2, mod)
        c[i] %= mod
    p25.reverse()
    c.reverse()
    ans = 0
    for i in range(k+1):
        tmp = p25[i]*p26[i]*c[i]
        tmp %= mod
        ans += tmp
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    
    k = int(input())
    s = input()
    n = len(s)
    mod = 10**9+7
    p25 = [0]*(k+1)
    p26 = [0]*(k+1)
    c = [0]*(k+1)

    p25[0], p26[0] = 1, 1
    c[0]= 1
    for i in range(1, k+1):
        p25[i] = p25[i-1]*25
        p25[i] %= mod
        p26[i] = p26[i-1]*26
        p26[i] %= mod
        c[i] = (n+i-1)*c[i-1]
        c[i] *= pow(i, mod-2, mod)
        c[i] %= mod
    p25.reverse()
    c.reverse()
    ans = 0
    for i in range(k+1):
        tmp = p25[i]*p26[i]*c[i]
        tmp %= mod
        ans += tmp
        ans %= mod
    print(ans)


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

s = input()
k = int(input())


list_pair = []
i = 0
while i <= len(s):
    for j in range(i+1,len(s)+1):
        list_pair.append(s[i:j])
    i = i + 1

list_pair = list(set(list_pair))



if len(s)<=50:
    list_pair.sort()
    print(list_pair[k-1])
else:
    abc = "abcdefghijklmnopqrstuvwxyz"
    tmp = []

    i = 0
    j = 0
    while len(tmp) < k + 1:
        for list_j in list_pair:

            if abc[i]==list_j[0]:
                tmp.append(list_j)

        i = i+1

    tmp.sort()

    print(tmp[k-1])


### FIXED CODE ###

s = input()
k = int(input())


list_pair = []
i = 0
while i <= len(s):
    for j in range(1,min(len(s)-i+1,k+1)):
#        print(j,s[i:i+j])
        list_pair.append(s[i:i+j])
    i = i + 1

list_pair = list(set(list_pair))

list_pair.sort()
print(list_pair[k-1])
### BUGGY CODE ###

N = int(input())
a = [ [str=="#" for str in input()]for _ in range(N)]
all_source = [(i,j) for j in range(N) for i in range(N)]

n =0

def f(i_,j_,A):
    global n
    n+=1
    A_copy =   [[ A[i][j] for j in range(N)]for i in range(N)]
    for i,val in enumerate([A[i_][j] for j in range(N) ]):
        A_copy[i][j_] =val
    return A_copy


def slow_solve(n,a):
    if n>5:
        return 99999
    if all(a[i][j]==True for i,j in all_source):
        return n
    min_val = 999999
    for i,j in all_source:
        a_copy = f(i,j,a)
        min_val = min(min_val,slow_solve(n+1,a_copy))
    return min_val


ans = (slow_solve(0,a))
if ans >100:
    ans = 6
if not any(a[i][j]==True for i,j in all_source):
    ans  = -1
print(ans)

### FIXED CODE ###

N = int(input())
a = [ [str=="#" for str in input()]for _ in range(N)]
#all_source = [(i,j) for j in range(N) for i in range(N)]

n =0
ans =9999999999999
all_black_row = sum(all(a[i][j] for i in range(N)) for j in range(N))
black_count_line  = [(sum(a[i][j] for j in range(N))) for i in range(N)]
black_count_row = [(sum(a[i][j] for i in range(N))) for j in range(N)]
for line_no,blacks in enumerate(black_count_line):
    tmp_ans = N -  all_black_row
    if black_count_row[line_no] ==0:
        tmp_ans +=1
    tmp_ans += N-blacks
    ans = min(ans,tmp_ans)

if not any(black_count_line) and not any(black_count_row):
    ans = -1
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def bellman_ford(N, adj, start):
    ans = [float("inf")] * N
    q = deque()
    q.append((start, 0, {}))
    while len(q):
        i, cost, history = q.popleft()
        if cost >= ans[i]:
            continue
        ans[i] = cost
        history = {k: history[k] for k in history}
        history[i] = cost
        for j in adj[i]:
            ncost = cost + adj[i][j]
            if j in history and history[j] > ncost:
                ncost = -float("inf")
            q.append((j, ncost, history))
    return ans


def main():
    N, M, P = map(int, input().split())
    adj = [{} for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if B-1 in adj[A-1]:
            adj[A-1][B-1] = min(P-C, adj[A-1][B-1])
        else:
            adj[A-1][B-1] = P-C
    costs = bellman_ford(N, adj, 0)
    ans = -costs[N-1]
    if ans < 0:
        print(0)
    elif ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def bellman_ford(N, adj, start):
    ans = [float("inf")] * N
    q = deque()
    q.append((start, 0, 0))
    while len(q):
        i, cost, path = q.pop()
        if cost >= ans[i]:
            continue
        ans[i] = cost
        for j in adj[i]:
            ncost = cost + adj[i][j]
            if path > N:
                ncost = -float("inf")
            q.append((j, ncost, path+1))
    return ans


def main():
    N, M, P = map(int, input().split())
    adj = [{} for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if B-1 in adj[A-1]:
            adj[A-1][B-1] = min(P-C, adj[A-1][B-1])
        else:
            adj[A-1][B-1] = P-C
    costs = bellman_ford(N, adj, 0)
    ans = -costs[N-1]
    if ans < 0:
        print(0)
    elif ans == float("inf"):
        print(-1)
    else:
        print(ans)


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

def divisors(n):
    import math
    ret = set()
    for i in range(1, math.ceil(n**0.5)+1):
        if n % i == 0:
            if i != 1:
                ret.add(i)
            ret.add(n // i)
    return ret


def main():

    N = int(input())
    s = divisors(N)
    ans = divisors(N-1)

    for x in s:
        n = N
        while(n % x == 0):
            n = n // x
        if n % x == 1:
            ans.add(x)

    print(len(ans))

main()


### FIXED CODE ###

def divisors(n):
    ret = set()
    for i in range(1, int(n**0.5)+2):
        if n % i == 0:
            ret.add(i)
            ret.add(n // i)
    ret.remove(1)
    return ret


def main():
    N = int(input())
    s = divisors(N)
    ans = divisors(N-1)

    for x in s:
        n = N
        if x == 1:
            continue
        while(n % x == 0):
            n = n // x
        if n % x == 1:
            ans.add(x)
    print(len(ans))


main()
### BUGGY CODE ###

import numpy as np
height, width = map(int, input().split())
numofsquare = height*width
memoarray = np.zeros((height + 2, width + 2))
memoarray += numofsquare
nokorimasu = numofsquare
kaisu = 0
for i in range(1, height+1):
    S = input()
    for j in range(1, width+1):
        if S[j-1] == "#":
            memoarray[i, j] = 0


while nokorimasu > 0:
    kaisu += 1
    nokorimasu = 0
    for h in range(1, height + 1):
        for w in range(1, width + 1):
            if (memoarray[h, w] > kaisu):
                memolist = [memoarray[h - 1, w],  memoarray[h, w - 1],
                            memoarray[h, w + 1],  memoarray[h + 1, w]]
                if (kaisu-1) in memolist:
                    memoarray[h, w] = kaisu
                    nokorimasu += 1


print("{}".format(kaisu-1))


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while len(check_que) != 0:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)
### BUGGY CODE ###


def solve():
#    num = list(range(N+1))
#    l = [0]*M
    dp = [1]*(N)
    for i in range(M):
#        dp = [dp[j] for j in range(0,LR[i][0])]
#        dp = [dp[j] for j in range(LR[i][1], M)]
        for j in range(0, LR[i][0]-1):
            dp[j] = 0
        for j in range(LR[i][1], N):
            dp[j] = 0
#    print(dp)
    print(sum(dp))


if __name__ == "__main__":
    N,M = list(map(int, input().split()))
    LR = [list(map(int, input().split())) for _ in range(M)]
    solve()  


### FIXED CODE ###


def solve():
    dp = [0] * N
    L = max(l)
    R = min(r)
    if L <= R:
        i = list(range(L,R+1))
        ans = len(i)
    else:
        ans = 0
    print(ans)

if __name__ == "__main__":
    N,M = list(map(int, input().split()))
#    LR = [list(map(int, input().split())) for _ in range(M)]
    l,r = [0]*M, [0]*M
    for c in range(M):
        tmp = list(map(int, input().split()))
        l[c] = tmp[0]
        r[c] = tmp[1]
    solve()