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

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = input().split()
    a = int(a)
    b = int(b)
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:
        # 最後の点を追加
        throwgh_point_list[i] = current

        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in Graph_list[current]:
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, j, throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:

        # 全ての点に到達している場合
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の点に移動する        
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)
### BUGGY CODE ###

import sys

def main():

	input = sys.stdin.readline

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

	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort(reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[P[i]-1]

		larger = len(largeind)
		smaller = -1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

	print(x)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():

	input = sys.stdin.readline

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

	RR = [i+1 for i in range(N)]
	LL = [i-1 for i in range(N)]
	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort()

	x = 0
	for i in range(N):
		target = ips[P[i]-1]
		R1ind = RR[target]
		R2ind = RR[ min(R1ind,N-1) ]
		L1ind = LL[target]
		L2ind = LL[ max(L1ind,0) ]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

		if L1ind!=-1:
			RR[L1ind] = R1ind
		if R1ind!=N:
			LL[R1ind] = L1ind

	print(x)

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

from collections import defaultdict

n, p = map(int, input().split())
S = input().strip()

if p == 2 or p == 5:
    count = 0
    digits = '02468' if p == 2 else '05'
    for i, x in enumerate(S, 1):
        if x in digits:
            count += i
    print(count)
else:
    def comb(n):
        if n >= 2:
            return n*(n-1) // 2
        else:
            return 0
    
    counter = [0]*p
    for i in range(n-1, -1, -1):
        counter[int(S[i:]) % p] += 1
    print(counter[0] + sum(comb(i) for i in counter))


### FIXED CODE ###

n, p = map(int, input().split())
if p in (2, 5):
  c = 0
  for i, x in enumerate(map(int, input()[::-1])):
    if x % p == 0:
      c += n-i
  print(c)
else:
  c = [0] * p
  y = 0
  t = 1
  for x in map(int, input()[::-1]):
    y = (y + t*x) % p
    c[y] += 1
    t = (10 * t) % p
  print(sum(i * (i-1) // 2 for i in c) + c[0])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

def solve(H: int, W: int, S: "List[str]"):
    S = np.array(S)
    s = np.ones((H+2, W+2),dtype=np.int)
    s[1:-1,1:-1] = S
    sh = np.ravel(s)
    sw = np.ravel(s.T)

    def lamp(a):
        left = np.arange(len(a))
        left[a==0] = 0
        left = np.maximum.accumulate(left)

        right = np.arange(len(a))
        right[a[::-1]==0] = 0
        right = np.maximum.accumulate(right)
        right = len(a) - right[::-1]
        k = (right-left) - 2
        k[a==1] =0

        return k

    
    s = lamp(sh)+ np.ravel(lamp(sw).reshape(W+2,H+2).T) 

    print(np.max(s)-1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [[ int(_.replace(".", "0").replace("#", "1")) for _ in next(tokens)] for _ in range(H)]  # type: "List[str]"
    solve(H, W, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def solve(H: int, W: int, S: "List[int]"):
    # print(S)

    hcnts = [[0]*W for _ in range(H)]
    for h in range(H):
        hcnts[h][0] = S[h][0]
        for t in range(1,W):
            hcnts[h][t] = (S[h][t]+hcnts[h][t-1])*S[h][t]
    for h in range(H):
        for t in range(W-2,-1,-1):
            hcnts[h][t] = max(hcnts[h][t],hcnts[h][t+1])*bool(hcnts[h][t])

    wcnts = [[0]*W for _ in range(H)]
    for h in range(W):
        wcnts[0][h] = S[0][h]
        for t in range(1,H):
            wcnts[t][h] = (S[t][h]+wcnts[t-1][h])*S[t][h]
    for h in range(W):
        for t in range(H-2,-1,-1):
            wcnts[t][h] = max(wcnts[t][h],wcnts[t+1][h])*bool(wcnts[t][h])
    # print(hcnts)
    # print(wcnts)
    a = [hcnts[h][w]+wcnts[h][w]-1 for h in range(H) for w in range(W)]
    print(max(a))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [[ int(_.replace(".", "1").replace("#", "0")) for _ in next(tokens)] for _ in range(H)]  # type: "List[str]"
    solve(H, W, S)

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

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    H,W = map(int, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]
    q = deque()
    visited = [[False]*W for _ in range(H)]
    black_cnt = 0
    ans = 0
    for y in range(H):
        for x in range(W):
            if grid[y][x] == '#':
                q.append((y,x,0))
                visited[y][x] = True
                black_cnt += 1
    while q:
        y,x,step = q.popleft()
        ans = step
        for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
            ny = y+dy
            nx = x+dx
            if 0<=ny<H and 0<=nx<W and not visited[ny][nx]:
                q.append((ny,nx,step+1))
                visited[ny][nx] = True
                black_cnt += 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H, W = map(int,input().split())
    visited = [[False]*W for _ in range(H)]
    q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                q.append((y, x))
                visited[y][x] = True

    ans = -1
    while q:
        ans += 1
        nq = []
        for y, x in q:
            if 0 < x and not visited[y][x-1]:
                visited[y][x-1] = True
                nq.append((y,x-1))
            if x < W-1 and not visited[y][x+1]:
                visited[y][x+1] = True
                nq.append((y,x+1))
            if 0 < y and not visited[y-1][x]:
                visited[y-1][x] = True
                nq.append((y-1, x))
            if y < H-1 and not visited[y+1][x]:
                visited[y+1][x] = True
                nq.append((y+1,x))
        if nq:
            q = nq
        else:
            break

    print(ans)

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

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

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

tree = [[] for _ in range(n)]

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

add = [0] * n

for i in range(q):
    p, x = map(int, input().split())
    add[p-1] += x

ans = [0] * n

def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in tree[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

print(*ans)

### FIXED CODE ###

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

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

tree = [[] for _ in range(n)]

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

add = [0] * n

for i in range(q):
    p, x = map(int, input().split())
    add[p-1] += x

ans = [0] * n

def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in tree[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

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

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

H=list(map(int,input().split()))
H=sorted(H)[::-1]

if K>=N:
  print(0)
else:
  for i in range(K):
    del H[0]
  print(sum(H))


### FIXED CODE ###

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

H=list(map(int,input().split()))
H=sorted(H)

sum=0
if K>=N:
  print(sum)
else:
  for i in range(N-K):
    sum=sum+H[i]
  print(sum)
### BUGGY CODE ###


from bisect import bisect_left
from math import ceil
import collections.abc


class LazySequence(collections.abc.Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def __len__(self):
        return self.size

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, v):
        while i <= self.size:
            self.tree[i] += v
            i += i & -i


N = int(input())
a = [0] + [int(s) for s in input().split()]


def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(s)

    def f(v):
        i = bisect_left(ss, v)
        return i + 1

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        fi = f(s[i])
        count += b.sum(fi)
        b.add(fi, 1)

    return count


# i: 0, 1, ..., 10 ** 9 + 10
# x: 10 ** 9 + 10, ..., 0
counts = LazySequence(lambda i: count_lr(10 ** 9 + 10 - i), 10 ** 9 + 10)
ans = 10 ** 9 + 10 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)


### FIXED CODE ###


from bisect import bisect_left
from math import ceil
import sys
if sys.version_info[0:2] >= (3, 3):
    from collections.abc import Sequence
else:
    from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def __len__(self):
        return self.size

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, v):
        while i <= self.size:
            self.tree[i] += v
            i += i & -i


N = int(input())
a = [0] + [int(s) for s in input().split()]
# a = [0] * (N + 1)


def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(set(s))
    ind = {v: i + 1 for i, v in enumerate(ss)}

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        j = ind[s[i]]
        count += b.sum(j)
        b.add(j, 1)

    return count


# i: 0, 1, ..., 10 ** 9
# x: 10 ** 9, ..., 0
counts = LazySequence(lambda i: count_lr(10 ** 9 - i), 10 ** 9 + 1)
ans = 10 ** 9 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)
### BUGGY CODE ###

import numpy as np
import math

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j-w_list[i]>=0:
                dp[i][j] = max(dp[i-1][j],
                               dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###


def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j-w_list[i]>=0:
                dp[i][j] = max(dp[i-1][j],
                               dp[i-1][j-w_list[i]]+v_list[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n-1][w])
    return 0
 
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

MOD = 10 ** 9 + 7

_, _ = map(int, input().strip().split())
S = list(map(int, input().strip().split()))
T = list(map(int, input().strip().split()))

sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

for i, s in enumerate(S):
  for j, t in enumerate(T):
    v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
    sdp[i + 1][j + 1] = v % MOD

print(sdp[-1][-1] + 1)
# for row in sdp:
#  print(('{: 4d} ' * len(row)).format(*row))
## print(sdp)

### FIXED CODE ###

MOD = 10 ** 9 + 7


def main(S, T):
  l = len(T) + 1
  dp = [0] * l
  # sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

  # for i, s in enumerate(S):
  #  for j, t in enumerate(T):
  #    v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
  #    sdp[i + 1][j + 1] = v % MOD
  for i, s in enumerate(S):
    tmp = [0] * l
    for j, t in enumerate(T):
      v = dp[j + 1] + tmp[j] + (1 if s == t else -dp[j])
      tmp[j + 1] = v % MOD
    dp = tmp

  # return (sdp[-1][-1] + 1)
  return dp[-1] + 1


if __name__ == '__main__':
  if True:
    _, _ = map(int, input().strip().split())
    S = input().strip().split()
    T = input().strip().split()
  else:
    S = range(1000)
    T = range(1000)
  print(main(S, T))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=1
ans=0
for i in a:
  s=s*i
  if s>10**18:
    ans=1
   
  else:
    ans=0
    
if ans==1:
  print(-1)
  
else:
  print(s)

### FIXED CODE ###

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

a.sort()
if a[0]==0:
  print(0)
  
else:
  s=1
  for i in a:
    s*=i
    if s>10**18:
      print(-1)
      exit()
      
  print(s)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

i  = lambda: int(input())
li = lambda: list(map(int, input().split()))

N = i()
A = li()

D = [0] * N

full_mount = sum(A)
for i in range(0, N):
    t = full_mount
    for j in range(i + 1, N , 2):
        t -= A[j] * 2
    for j in range(i - 2, -1, -2):
        t -= A[j] * 2
    D[i] = str(t)

print(' '.join(D))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

i  = lambda: int(input())
li = lambda: list(map(int, input().split()))

N = i()
A = li()

D = [0] * N

D[0] = sum(A)
for i in range(1, N , 2):
    D[0] -= A[i] * 2

for i in range(1, N):
    D[i] = A[i-1] * 2 - D[i-1]

print(' '.join(map(str, D)))
### BUGGY CODE ###

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

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

visitcount = dict()
n_point = list()

x = 1
count = 0
while(x not in set(visitcount)):
  visitcount[x] = count
  n_point.append(x)
  x = A[x-1]
  count += 1
  
period = count - visitcount[x]

if (K < visitcount[x]):
  print(n_point[K])
else:
  y = (K-visitcount[x]) % period
  print(n_point[visitcount[x] + y])


### FIXED CODE ###

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

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

visitset = set()
visitcount = dict()
n_point = dict()

x = 1
count = 0
while(x not in visitset):
  visitset.add(x)
  visitcount[x] = count
  n_point[count] = x
  x = A[x-1]
  count += 1


period = count - visitcount[x]

if (K < visitcount[x]):
  print(n_point[K])
else:
  y = (K-visitcount[x]) % period
  print(n_point[visitcount[x] + y])
### BUGGY CODE ###

N, M, Rs = map(int, input().split())
R = list(map(int, input().split()))
D = [[float("inf")] * (N+1) for i in range(N+1)]
for i in range(M):
    a, b, c = map(int, input().split())
    D[a][b] = D[b][a] = c

for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            D[i][j] = min(D[i][j], D[i][k]+D[k][j])


def full(L):
    if len(L) == 1:
        return [L]
    else:
        L2 = []
        for i in range(len(L)):
            L2.extend([[L[i]] + Lc for Lc in full(L[:i] + L[i+1:])])
        return L2


L = full(R)
ans = float("inf")
for l in L:
    a = 0
    for i in range(Rs-1):
        a += D[l[i]][l[i+1]]
    ans = min(ans, a)

print(ans)

### FIXED CODE ###

N, M, Rs = map(int, input().split())
R = list(map(int, input().split()))
D = [[float("inf")] * (N+1) for i in range(N+1)]
for i in range(M):
    a, b, c = map(int, input().split())
    D[a][b] = D[b][a] = c

for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            D[i][j] = min(D[i][j], D[i][k]+D[k][j])


def full(L):
    if len(L) == 1:
        return [L]
    else:
        L2 = []
        for i in range(len(L)):
            L2.extend([[L[i]] + Lc for Lc in full(L[:i] + L[i+1:])])
        return L2


L = full(R)
ans = float("inf")
for l in L:
    a = 0
    for i in range(Rs-1):
        a += D[l[i]][l[i+1]]
    ans = min(ans, a)

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

L = list(input())
n = len(L)-1
div = 10**9+7

number = 1
many = 0
for i in range(1,n+1):
  if int(L[i]) == 1:
    many += 3**(n-i)*2**number%div
    number += 1
many += 2**number%div + 3**n%div

print(many%div)

### FIXED CODE ###

mod = 10**9+7

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m) (aとmは互いに素)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


L = list(input())
n = len(L)-1

#これだとTLEする

'''
number = 1
many = 0
for i in range(1,n+1):
  if int(L[i]) == 1:
    many += 3**(n-i) * 2**number %div
    number += 1
many += 2**number + 3**n
'''

beki3 = 3**n % mod
many = beki3
beki2 = 2
for i in range(1,n+1):
  beki3 = (beki3%mod)*mod_inv(3,mod)%mod
  if int(L[i]) == 1:
    many += beki3*beki2 %mod
    beki2 = beki2*2 %mod
many += beki2 % mod
print(many%mod)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(lambda x: int(x), input().split()))
ans = 0
for i in range(M):
  b, c = map(int, input().split())
  if c <= min(A):
    continue
  b = min(b, N)
  A += [c for j in range(b)]
  heapq.heapify(A)
  for i in range(b):
    heapq.heappop(A)
  
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
exc = []

for i in range(M):
  exc.append(list(map(int, input().split())))
exc.sort(key=lambda x: x[1], reverse=True)
e = []
count = 0
for i in range(M):
  e += [exc[i][1]] * exc[i][0]
  count += exc[i][0]
  if count >= N:
    break
cards = sorted(A+e, reverse=True)
print(sum(cards[:N]))
### BUGGY CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h):
        for j in range(w):
            a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
            b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
            c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
            d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(sum(u)-3for t in zip(a,b,c,d)for u in zip(*t)))
main()

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

#137_C
from collections import Counter
n = int(input())
s = [Counter(input()) for _ in range(n)]

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if s[i] == s[j]:
            ans += 1
            
print(ans)

### FIXED CODE ###

#137_C
from collections import Counter
n = int(input())
w = []
for _ in range(n):
    s = sorted(input())
    w.append(''.join(s))
w.sort()
w = Counter(w)
ans = 0
for t, idx in w.items():
    ans += idx * (idx - 1) // 2
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a = []
b = []
ans = 0
for i in range(n):
    tempa,tempb = map(int,input().split())
    a.append(tempa)
    b.append(tempb)
# while m>0:
for i in range(n):
    min_b = b[a.index(min(a))]
    min_a = a.index(min(a))
    if m - min_b > 0:
        m -= min_b
        ans +=  b.pop(min_a)*a.pop(min_a)
    else:
        ans +=  m*a.pop(min_a)
        m = 0
        print(ans)
        exit()

### FIXED CODE ###

n,m=map(int,input().split())
a = []
b = []
ans = 0
for i in range(n):
    tempa,tempb = map(int,input().split())
    a.append(tempa)
    b.append(tempb)
test = list(zip(a,b))
test = sorted(test)
i=0
while m>0:
    if m-test[i][1] >=0:
        ans += test[i][0]*test[i][1]
        m -=test[i][1]
    else:
        ans += test[i][0]*m
        m=0
        print(ans)
        exit()
    i+=1
print(ans)
### BUGGY CODE ###

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

if k == 1:
  print(0)
else:
  mem = 0
  while True:
    mem = n
    n = abs(n-k)
    if mem <= n:
      print(mem)
      break

### FIXED CODE ###

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

a = n % k
b = abs(a-k)
if a > b:
  print(b)
else:
  print(a)
### BUGGY CODE ###

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

cnt = 0
for i in range(N):
  tmp = 0
  for L, R in LR:
    if L-1 <= i <= R-1:
      tmp += 1
    else:
      break
    if tmp == M:
      cnt += 1
      break
print(cnt)

### FIXED CODE ###

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

Lma = 0
Rmi = N + 1
for L, R in LR:
  Lma = max(L, Lma)
  Rmi = min(R, Rmi)

print(max(0, Rmi - Lma + 1))