Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import deque

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

to = [[] for _ in range(n + 1)]
for i in range(n):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

q = deque([1])
dist = [-1] * (n + 1)
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        q.append(u)
        dist[u] = v

print("Yes")
# print(dist)

for i in range(2, n + 1):
    print(dist[i])


Fixed submission:
from collections import deque

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

to = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

q = deque([1])
dist = [-1] * (n + 1)
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        q.append(u)
        dist[u] = v

print("Yes")
# print(dist)

for i in range(2, n + 1):
    print(dist[i])

Buggy python submission (verdict: Runtime Error):
from collections import deque

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

to = [[] for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

q = deque([0])
dist = [-1] * n
dist[0] = 0
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        dist[u] = v
        q.append(u)

print("Yes")
# print(dist)

for i in range(n):
    if i == 0:
        continue
    print(dist[i] + 1)


Fixed submission:
from collections import deque

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

to = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

q = deque([1])
dist = [-1] * (n + 1)
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        q.append(u)
        dist[u] = v

print("Yes")
# print(dist)

for i in range(2, n + 1):
    print(dist[i])

Buggy python submission (verdict: Runtime Error):
from collections import deque

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

to = [[] for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

q = deque([0])
dist = [-1] * n
dist[0] = 0
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        dist[u] = v
        q.append(u)

print("Yes")
# print(dist)

for i in range(n):
    if i == 0:
        continue
    print(dist[i] + 1)


Fixed submission:
from collections import deque

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

to = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

q = deque([1])
dist = [-1] * (n + 1)
# print(to)

while q:
    v = q.popleft()

    for u in to[v]:
        if dist[u] != -1:
            continue
        q.append(u)
        dist[u] = v

print("Yes")
# print(dist)

for i in range(2, n + 1):
    print(dist[i])
Buggy python submission (verdict: Runtime Error):
from collections import deque

n, k = map(int, input().split())
a = deque(list(map(int, input().split())))

r = deque(['1'])

fhinish_roop = 0
index = 0
while not fhinish_roop:
    if str(a[index]) not in r:
        r.append(str(a[index]))
        index = a[index] - 1
    else:
        fhinish_roop = 1
        r_2 = "".join(r)
# print(r, index)
roop_l = r_2.find(str(a[index]))
# print(roop_l)
roop_len = len(r) - roop_l
roop_start_index = roop_l
# print(roop_len)

if k < roop_start_index:
    print(a[k - 1])

else:
    ans = (k - roop_start_index) % roop_len
    # print('ans={}'.format(ans))
    print(r[roop_start_index + ans])


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))

for i in range(n):
    a[i] -= 1

memo = [0] * n

index = 0
memo_index = 0
cnt_k = 1
while 1:
    tmp_move_to = a[index]
    if not memo[tmp_move_to]:
        memo[tmp_move_to] = 1
        index = tmp_move_to
        if cnt_k == k:
            print(tmp_move_to + 1)
            exit()
        cnt_k += 1
    else:
        break
k -= cnt_k

kaburi = tmp_move_to
circle = [kaburi]

index = kaburi
while 1:
    if kaburi == a[index]:
        break
    else:
        circle.append(a[index])
        index = a[index]
# print(circle)
print(circle[k % len(circle)] + 1)

Buggy python submission (verdict: Runtime Error):
from _collections import deque

n, k = map(int, input().split())
a = deque(list(map(int, input().split())))

r = deque(['1'])

fhinish_roop = 0
index = 0
while not fhinish_roop:
    if str(a[index]) not in r:
        r.append(str(a[index]))
        index = a[index] - 1
    else:
        fhinish_roop = 1
        r_2 = "".join(r)
# print(r, index)
roop_l = r_2.find(str(a[index]))
# print(roop_l)
roop_len = len(r) - roop_l
roop_start_index = roop_l
# print(roop_len)

if k < roop_start_index:
    print(a[k - 1])

else:
    ans = (k - roop_start_index) % roop_len
    # print('ans={}'.format(ans))
    print(r[roop_start_index + ans])


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))

for i in range(n):
    a[i] -= 1

memo = [0] * n

index = 0
memo_index = 0
cnt_k = 1
while 1:
    tmp_move_to = a[index]
    if not memo[tmp_move_to]:
        memo[tmp_move_to] = 1
        index = tmp_move_to
        if cnt_k == k:
            print(tmp_move_to + 1)
            exit()
        cnt_k += 1
    else:
        break
k -= cnt_k

kaburi = tmp_move_to
circle = [kaburi]

index = kaburi
while 1:
    if kaburi == a[index]:
        break
    else:
        circle.append(a[index])
        index = a[index]
# print(circle)
print(circle[k % len(circle)] + 1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

for i in range(n):
    print(a.count(i+1))


Fixed submission:
import collections

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

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

for i in range(n):
    print(a.count(i+1))


Fixed submission:
import collections

n = int(input())
a = list(map(int, input().split()))
b = collections.Counter(a)
for i in range(n):
    print(b[i+1])
Buggy python submission (verdict: Runtime Error):
s=input()
if s=='AAA' or s=='BBB':
  print("No")
else:
print("Yes")

Fixed submission:
s = input()

if s == 'AAA' or s == 'BBB':
    print("No")
else:
    print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

a = input()
q = int(input())
rflag = 0
b = []
for i in range(q):
    b.append(input())
# print(b)
# print(len(b[0]))
ans = list(a)

for i in range(len(b)):
    if len(b[i]) == 1:
        rflag = (rflag ^ 1)
    else:
        c = int(b[i][2])
        # print("c="+b[i][2])

        if not rflag:

            if c == 1:
                # print("extend={}".format(b[i][4]))
                extend = b[i][4]
                tmp = deque(ans)
                tmp.appendleft(extend)
                ans = list(tmp)
            else:
                # print('ll')
                ans.append(b[i][4])
        else:
            if c == 1:
                ans.append(b[i][4])
            else:
                # print("extend={}".format(b[i][4]))
                extend = b[i][4]
                tmp = deque(ans)
                tmp.appendleft(extend)
                ans = list(tmp)
        # print(ans,rflag)

if not rflag:
    print("".join(ans))
else:
    print("".join(ans[::-1]))


Fixed submission:
from collections import deque

a = input()
q = int(input())
rflag = 0
b = []
for i in range(q):
    b.append(input())
# print(b)
# print(len(b[0]))
ans = deque(list(a))

for i in range(len(b)):
    if len(b[i]) == 1:
        rflag = (rflag ^ 1)
    else:
        c = int(b[i][2])
        # print("c="+b[i][2])

        if not rflag:

            if c == 1:
                # print("extend={}".format(b[i][4]))
                extend = b[i][4]
                ans.appendleft(extend)
            else:
                # print('ll')
                ans.append(b[i][4])
        else:
            if c == 1:
                ans.append(b[i][4])
            else:
                # print("extend={}".format(b[i][4]))
                extend = b[i][4]
                ans.appendleft(extend)
        # print(ans,rflag)

if not rflag:
    print("".join(ans))
else:
    h="".join(ans)
    print(h[::-1])
Buggy python submission (verdict: Runtime Error):
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7


def choose(n, r, mod):
    r = min(r, n - r)
    x = 1
    y = 1
    for i in range(r):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    y = pow(y, -2, mod)
    return x * y % mod


ans = pow(2, n, mod) - 1 - choose(n, a, mod) - choose(n, b, mod)

while ans < 0:
    ans += mod
print(ans)


Fixed submission:
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7


def choose(n, r, mod):
    r = min(r, n - r)
    x = 1
    y = 1
    for i in range(r):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    y = pow(y, mod-2, mod)
    return x * y % mod


ans = pow(2, n, mod) - 1 - choose(n, a, mod) - choose(n, b, mod)

while ans < 0:
    ans += mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))

l = 0
r = k
ansl = 0
ansr = 0
ans=0
for i in range(n - k + 1):
    tmp = sum(p[i:i + k])
    # print(i,i+k,tmp)
    if tmp > ans:
        ansl = i
        ansr = i + k - 1
        ans=tmp
# print(ansl, ansr)
ans2 = 0
for i in range(ansl, ansr + 1):
    ans2 += (p[i] + 1) / 2
print(ans2)


Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))

ansl = 0
ansr = k-1
ans = 0
tmp = sum(p[:k])
# print(tmp)
for i in range(1,n - k+1):
    tmp = tmp - p[i-1] + p[i + k-1]
    # print(i,i+k-1,tmp)
    if tmp > ans:
        ansl = i
        ansr = i + k - 1
        ans = tmp
# print(ansl, ansr)
ans2 = 0
for i in range(ansl, ansr + 1):
    ans2 += (p[i] + 1) / 2
print(ans2)
Buggy python submission (verdict: Runtime Error):
n = int(input())
ki = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ki[a].append([b, i])
ans = [-1] * (n - 1)


# print(ki)


def d(index, color):
    cnt = 1
    for (t, jid) in ki[index]:
        if cnt == color:
            cnt += 1
        ans[jid] = cnt
        d(t, cnt)
        cnt += 1


d(0, 0)
print(max(ans))
for i in ans:
    print(i)


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
ki = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ki[a].append([b, i])
ans = [-1] * (n - 1)


# print(ki)


def d(index, color):
    cnt = 1
    for (t, jid) in ki[index]:
        if cnt == color:
            cnt += 1
        ans[jid] = cnt
        d(t, cnt)
        cnt += 1


d(0, 0)
print(max(ans))
for i in ans:
    print(i)
Buggy python submission (verdict: Runtime Error):
import collections

n = int(input())
d = list(map(int, input().split()))
e = collections.Counter(d)

if d[0] != 0:
    print(0)
    exit()

cntsum = 1
judge_cnt = 0

if e[1] == 0:
    print(0)
    exit()

m = max(e)
e2 = dict(sorted(e.items()))
e3 = list(e2.values())
e4 = list(e2.keys())
#print(e2)
#print(e3)
#print(e4)

tmp=0
for i in e4:
    if i-tmp>=2:
        print(0)
        exit()
    tmp=i
    
cntsum = 1
for i in range(1, len(e3)):
    cntsum *= e3[i - 1] ** e3[i]
print(cntsum)

Fixed submission:
n=int(input())
print((n-1)//2)
Buggy python submission (verdict: Runtime Error):
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)


def prime_factorize(n):
    p = []
    while n % 2 == 0:
        if 2 not in p:
            p.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in p:
                p.append(f)
                n //= f
        else:
            f += 2
    if n != 1 and n not in p:
        p.append(n)
    return p


a, b = map(int, input().split())
q = prime_factorize(gcd(a, b))
# print(q)
print(len(q) + 1)


Fixed submission:
n = int(input())
cnt = 0
if n % 2 == 0:
    cnt = n // 2
else:
    cnt = n // 2 + 1
print(cnt / n)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import math
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    # print(a)
    # print(math.floor(a[-1] / 2))
    b = bisect.bisect_left(a, math.floor(a[-1] / 2))
    a.insert(b, math.floor(a[-1] / 2))
    a.pop(-1)

    if len(a) == 1:
        print(math.floor(a[0] / 2**(m - i - 1)))
        exit()
print(sum(a))


Fixed submission:
import heapq
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(lambda x: x * (-1), a))

heapq.heapify(b)
for i in range(m):
    h = heapq.heappop(b)
    heapq.heappush(b, math.ceil(h / 2))

c = list(map(lambda x: x * (-1), b))

print(sum(c))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import math
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    # print(a)
    # print(math.floor(a[-1] / 2))
    b = bisect.bisect_left(a, math.floor(a[-1] / 2))
    a.insert(b, math.floor(a[-1] / 2))
    a.pop(-1)

    if len(a) == 1:
        print(math.floor(a[0] / 2**(m - i - 1)))
        exit()
print(sum(a))


Fixed submission:
import heapq
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(lambda x: x * (-1), a))

heapq.heapify(b)
for i in range(m):
    h = heapq.heappop(b)
    heapq.heappush(b, math.ceil(h / 2))

c = list(map(lambda x: x * (-1), b))

print(sum(c))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    # print(a)
    # print(math.floor(a[-1] / 2))
    b = bisect.bisect_left(a, math.floor(a[-1] / 2))
    a.insert(b, math.floor(a[-1] / 2))
    a.pop(-1)

    if len(a) == 1:
        print(math.floor(a[0] / 2**(m - i - 1)))
        exit()
print(sum(a))


Fixed submission:
import heapq
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(lambda x: x * (-1), a))

heapq.heapify(b)
for i in range(m):
    h = heapq.heappop(b)
    heapq.heappush(b, math.ceil(h / 2))

c = list(map(lambda x: x * (-1), b))

print(sum(c))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
c = [0]
d = c + a
s = [0 for _ in range(n + 1)]
 
for i in range(n, 0, -1):
    w = 0
    for j in range(2 * i, n + 1, i):
        w ^= s[j]
    s[i] = w ^ d[i]
    
print(b.count(1) if b.count(1) else 0)
for i in range(1, n + 1):
    if s[i] != 0:
        print(s[i], end=' ')

Fixed submission:
N = int(input())
c = [0]
a = list(map(int, input().split()))
b = [0 for _ in range(N + 1)]

d = c + a

for i in range(N, 0, -1):
    s = 0
    for j in range(2 * i, N + 1, i):
        s ^= b[j]

    b[i] = (s ^ d[i])

# print(b)
print(b.count(1) if b.count(1) else 0)
if len(b):
    for i in range(1, len(b)):
        if b[i] != 0:
            print(i, end=' ')
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
l, r = map(int, input().split())
a = []
if r - l >= 2019:
    print(0)
else:
    for i in range(r - l + 1):
        a.append((l + i) % 2019)
# print(a)
a.sort()
print(a[0] * a[1])


Fixed submission:
l, r = map(int, input().split())
a = []

data = 2019

if r - l + 1 >= 2019:
    print(0)
    exit()

else:
    for i in range(l, r + 1):
        for j in range(i+1, r + 1):
            data = min(data, i * j % 2019)

print(data)
Buggy python submission (verdict: Runtime Error):
import math

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


def combinations_count(N, R):
    return math.factorial(N) // (math.factorial(N - R) * math.factorial(R))


for i in range(1, k + 1):
    answer = combinations_count(k - 1, i - 1) * combinations_count(n - k + 1, i)
    # print(combinations_count(i - 1 + k, i - 1), combinations_count(n - k + 1, i))
    print(answer % (10 ** 9 + 7))

Fixed submission:
import math

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


def combinations_count(N, R):
    return math.factorial(N) // (math.factorial(N - R) * math.factorial(R))


for i in range(1, k + 1):
    # 注意！もし青玉の置く場所がiより少なかったら置くことができないので、0通り
    if n - k + 1 < i:
        print(0)
    else:
        answer = combinations_count(k - 1, i - 1) * combinations_count(n - k + 1, i)
        # print(combinations_count(i - 1 + k, i - 1), combinations_count(n - k + 1, i))
        print(answer % (10 ** 9 + 7))

Buggy python submission (verdict: Runtime Error):
import math
n, k = map(int, input().split())


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


for i in range(1, k + 1):
    answer = combinations_count(k - 1, i - 1) * combinations_count(n - k + 1, i)
    # print(combinations_count(i - 1 + k, i - 1), combinations_count(n - k + 1, i))
    print(answer % (10 ** 9 + 7))


Fixed submission:
import math

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


def combinations_count(N, R):
    return math.factorial(N) // (math.factorial(N - R) * math.factorial(R))


for i in range(1, k + 1):
    # 注意！もし青玉の置く場所がiより少なかったら置くことができないので、0通り
    if n - k + 1 < i:
        print(0)
    else:
        answer = combinations_count(k - 1, i - 1) * combinations_count(n - k + 1, i)
        # print(combinations_count(i - 1 + k, i - 1), combinations_count(n - k + 1, i))
        print(answer % (10 ** 9 + 7))

Buggy python submission (verdict: Runtime Error):
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

for i in range(1, k + 1):
    answer = combinations_count(k-1, i - 1) * combinations_count(n - k + 1, i)
    # print(combinations_count(i - 1 + k, i - 1), combinations_count(n - k + 1, i))
    print(answer % (10 ** 9 + 7))

Fixed submission:
import math

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


def combinations_count(N, R):
    return math.factorial(N) // (math.factorial(N - R) * math.factorial(R))


for i in range(1, k + 1):
    # 注意！もし青玉の置く場所がiより少なかったら置くことができないので、0通り
    if n - k + 1 < i:
        print(0)
    else:
        answer = combinations_count(k - 1, i - 1) * combinations_count(n - k + 1, i)
        # print(combinations_count(i - 1 + k, i - 1), combinations_count(n - k + 1, i))
        print(answer % (10 ** 9 + 7))
Buggy python submission (verdict: Runtime Error):
n = int(input())
w = list(map(int, input().split()))
wa = 0
for i in range(len(w)):
    wa += w[i]
wa2 = 0
wa3 = 0
i = 0
while wa2 <= wa / 2:
    wa2 += w[i]
    i += 1
for j in range(i, len(w)+1):
    wa3 += w[j]
print(abs(wa2 - wa3))
exit()


Fixed submission:
n = int(input())
w = [int(i) for i in input().split()]
p = 100000
a = sum(w)
k = 0
for i in range(n - 1):
    k += w[i]
    p = min(p, abs(k - (a - k)))
print(p)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n, m = map(int, input().split())
br = [int(sys.stdin.readline()) for i in range(m)]

dp = [0 for _ in range(n + 1)]

dp[0] = 1
if 1 not in br:
    dp[1] = 1
for i in range(2, n + 1):
    if i in br:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] = dp[i] % (10 ** 9 + 7)
print(dp[n])



Fixed submission:
n, m = map(int, input().split())
p = {int(input()) for _ in range(m)}
s = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
if 1 in p:
    dp[1] = 0

for i in range(2, n+1):
    if i in p:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % s

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
br = [int(input()) for i in range(m)]

dp = [0 for _ in range(n + 1)]

dp[0] = 1
if 1 not in br:
    dp[1] = 1
for i in range(2, n + 1):
    if i in br:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] = dp[i] % (10 ** 9 + 7)
print(dp[n])


Fixed submission:
n, m = map(int, input().split())
p = {int(input()) for _ in range(m)}
s = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
if 1 in p:
    dp[1] = 0

for i in range(2, n+1):
    if i in p:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % s

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())


ans_w = [[0] * w for i in range(h)]
ans_h = [[0] * w for i in range(h)]

for i in range(h):
    for j in range(w):
        cnt = 0
        if s[i][j] == '#': continue
        if ans_w[i][j] != 0: continue

        while j + cnt < w:
            if s[i][j + cnt] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_w[i][j + k] = cnt
# print(ans_w)

for i in range(w):
    for j in range(h):
        cnt = 0
        if s[j][i] == '#': continue
        if ans_h[j][i] != 0: continue

        while j + cnt < h:
            if s[j + cnt][i] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_h[j + k][i] = cnt
# print(ans_h)

out = 0
for i in range(h):
    for j in range(w):
        out = max(out, ans_h[i][j] + ans_w[i][j])

print(out - 1)


Fixed submission:
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())


ans_w = [[0] * w for i in range(h)]
ans_h = [[0] * w for i in range(h)]

for i in range(h):
    for j in range(w):
        cnt = 0
        if s[i][j] == '#': continue
        if ans_w[i][j] != 0: continue

        while j + cnt < w:
            if s[i][j + cnt] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_w[i][j + k] = cnt
# print(ans_w)

for i in range(w):
    for j in range(h):
        cnt = 0
        if s[j][i] == '#': continue
        if ans_h[j][i] != 0: continue

        while j + cnt < h:
            if s[j + cnt][i] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_h[j + k][i] = cnt
# print(ans_h)

out = 0
for i in range(h):
    for j in range(w):
        out = max(out, ans_h[i][j] + ans_w[i][j])

print(out - 1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
b = [] * M
r = []
for i in range(M):
    x, y = map(int, input().split())
    g = list(range(x, y + 1))
    b.append(g)
# print(b)
for i in range(M - 1):
    r = list(set(b[i]) & set(b[i + 1]))
    # print(r)
    b[i + 1] = r
if M >= 2:
    print(len(r))

else:
    print(len(b[0]))


Fixed submission:
N, M = list(map(int, input().split()))
l = 0
r = 10000000
for i in range(M):
    x, y = map(int, input().split())
    l = max(l, x)
    r = min(r, y)

print(r - l + 1 if l <= r else 0)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
b = [] * M
r = []
for i in range(M):
    x, y = map(int, input().split())
    g = list(range(x, y + 1))
    b.append(g)
# print(b)
for i in range(M - 1):
    r = list(set(b[i]) & set(b[i + 1]))
    # print(r)
    b[i + 1] = r
if M >= 2:
    print(len(r))

else:
    print(len(b[0]))


Fixed submission:
N, M = list(map(int, input().split()))
l = 0
r = 10000000
for i in range(M):
    x, y = map(int, input().split())
    l = max(l, x)
    r = min(r, y)

print(r - l + 1 if l <= r else 0)