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

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n=n0()
a=n1()

from math import factorial
f={x:factorial(x) for x in range(n+1)}
def comb(n):
    if n<=1:
        return 0
    if n==2:
        return 1
    return f[n]//(factorial(2)*f[n-2])

from collections import Counter
c=Counter(a)
d={i:comb(j) for i,j in c.items()}
s=sum(d.values())

for i in a:
    print(s-d[i]+comb(c[i]-1))

### FIXED CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n=n0()
a=n1()

def comb(n):
    if n<=1:
        return 0
    if n==2:
        return 1
    return (n*(n-1))//2

from collections import Counter
c=Counter(a)
# print(c)
d={i:comb(j) for i,j in c.items()}
# print(d)
s=sum(d.values())
# print(s)

for i in a:
    print(s-d[i]+comb(c[i]-1))
### BUGGY CODE ###

n, k = list(map(int, input().split(' ')))
aaa = sorted(list(map(int, input().split(' '))))
def choice(a, b):
    if b == 0 or a == b:
        return 1
    if a <= b:
        return 0
    if b > a - b:
        return choice(a, a - b)
    hoge = 1
    for a in range(a, a-b, -1):
        hoge = hoge * a
    fuga = 1
    for b in range(1, b+1):
        fuga = fuga * b
    return hoge // fuga

ans = 0
for st in range(n):
    for ed in range(st+1, n):
        choice_pattern = choice(ed-1 - st, k-2)  # [st + 1: ed - 1] の範囲から k-2個取るパターン数
        ans = (ans + (aaa[ed] - aaa[st]) * choice_pattern) % 1000000007
        # print(st, ed, ':::', ed-1 - st, k-2, "stCed=", choice_pattern, 'hoge=', (aaa[ed]-aaa[st]), ans)
print(ans)

### FIXED CODE ###

n, k = list(map(int, input().split(' ')))
aaa = sorted(list(map(int, input().split(' '))))
mmm = 1000000000 + 7
# 二項係数 mod [検索]
fac = []
inv = []
inv_fac = []
def init(n):
    fac.append(1)
    fac.append(1)
    inv.append(0)
    inv.append(1)
    inv_fac.append(1)
    inv_fac.append(1)
    for i in range(2, n):
        fac.append(fac[-1] * i % mmm)
        inv.append(mmm - inv[mmm%i] * (mmm // i) % mmm)
        inv_fac.append(inv_fac[-1] * inv[-1] % mmm)

def choice(a, b):
    if a < b:
        return 0
    return fac[a] * (inv_fac[b] * inv_fac[a-b] % mmm) % mmm
ans = 0
init(1000000)
for target in range(n):
    p_pattern = choice(target, k-1)
    #print(target, k-1, 'p_choice', choice(target, k-1))
    n_pattern = choice(n-target-1, k-1)
    #print(n-target-1, k-1, 'n_choice', choice(n-target-1, k-1))
    ans = (ans + aaa[target] * p_pattern - aaa[target] * n_pattern) % mmm
    #print(aaa[target], target-1, n-target, k-1, p_pattern, n_pattern)
print(ans % mmm)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
a=l[0]
for i in range(1,n):
    a*=l[i]
    if a==0:
        break
if a>10**18:
    print(-1)
else:
    print(a)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
a=l[0]
for i in range(1,n):
    a*=l[i]
    if a>10**18:
        break
if a>10**18 and l.count(0)==0:
    print(-1)
elif l.count(0)>0:
    print(0)
else:
    print(a)
### BUGGY CODE ###

n,x=(int(i) for i in input().split())

def makeBurger(s):
    return "B"+s+"P"+s+"B"
s = "P"
if(n>0):
    for i in range(n):
        s = makeBurger(s)
count = 0
for i in range(x):
    if s[i]=='P':
        count += 1
print(count)

### FIXED CODE ###

n , x = map(int, input().split())
# ABCの長さ
a = [1]
for i in range(n):
    a.append(a[i] * 2 + 3)

# パティの枚数
p = [1]
for i in range(n):
    p.append(p[i] * 2 + 1)

def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x == 1:
        return 0
    elif 1 <  x <=  1 + a[n - 1]:
        return f(n - 1, x - 1)
    elif x == 2 + a[n-1]:
        return p[n-1] + 1
    elif 2 + a[n - 1] < x <= 2 + 2 * a[n - 1]:
        return f(n - 1, x - 2 - a[n - 1]) + p[n-1] + 1
    elif x == 3 + 2 * a[n - 1]:
        return 2 * p[n-1] + 1

print(f(n, x))
### BUGGY CODE ###

s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = ""
for i in range(n):
    num = s[-(i+1)] + num
    num_int = int(num)
    memo[num_int%2019] += 1

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

### FIXED CODE ###

s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
t = 1
for i in reversed(s):
    num += int(i) * t
    num %= 2019
    t *= 10
    t %= 2019
    memo[num] += 1

ans = 0
for p in memo:
    ans += p*(p-1)//2

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

import heapq

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

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

heapq.heapify(a)

l = [[] for _ in range(m)]

for i in range(m):
    b,c = map(int,input().split())
    l[i] = [c,b]
l.sort()
for i in range(m):
    b,c = l[i][1],l[i][0]
    for j in range(b):
        x = heapq.heappop(a)
        if(x < c):
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,x)
            break
print(sum(a))

### FIXED CODE ###

import heapq

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

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

heapq.heapify(a)

l = [[] for _ in range(m)]

for i in range(m):
    b,c = map(int,input().split())
    l[i] = [c,b]
l.sort(reverse=True)
for i in range(m):
    b,c = l[i][1],l[i][0]
    for j in range(b):
        x = heapq.heappop(a)
        if(x < c):
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,x)
            break
print(sum(a))
### BUGGY CODE ###

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

kitai = [None]*(1000+1)
for i in range(1, 1001):
    kitai[i] = (0.5*i*(i+1))/i
ans = 0
ans_list=[]
for i in range(0, N-K+1):
    temp = P[i:i+K]
    temp2 = sum(temp)
    if ans < temp2:
        ans = temp2
        ans_list = temp

ans = 0
for al in ans_list:
    ans += kitai[al]
print(ans)


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
P = list(map(int, input().split()))

kitai = [None]*(1001)
for i in range(1, 1001):
    kitai[i] = (0.5*i*(i+1))/i

ruiseki = P.copy()
ruiseki[K-1] = sum(ruiseki[0:K])
for i in range(K, N):
    ruiseki[i] = ruiseki[i-1]+P[i]-P[i-K]

ind = np.array(ruiseki).argmax()
temp = P[ind-K+1:ind+1]
ans = 0
for t in temp:
    ans+=kitai[t]
print(ans)
### BUGGY CODE ###

S = input()
ans = 0
for i in range(len(S)-3):
    for j in range(i+4, len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            ans += 1
            break
print(ans)


### FIXED CODE ###

s = input()[::-1]
length = len(s)
a = [0] * length
d = [0] * length
ans = [0] * 2019
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = [i for i in ans if i != 0]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(len(ans_c))]) / 2) + ans[0])
### BUGGY CODE ###

def inp():
    return input()
def iinp():
    return int(input())
def inps():
    return input().split()
def miinps():
    return map(int,input().split())
def linps():
    return list(input().split())
def lmiinps():
    return list(map(int,input().split()))
def lmiinpsf(n):
    return [list(map(int,input().split()))for _ in range(n)]

s = iinp()
z = 10**9+7
ans = 0
stack = []
n = s

if s == 1 or s == 2:
    print(0)
    exit()

for i in range(s-3,3-1,-1):
    stack.append(i)

while stack:
    n = s
    x = stack.pop()
    y = x
    n -= x
    if n == 0:
        ans += 1
        ans %= z
        continue
    elif 0 < n < 3:
        continue
    for i in range(n,3-1,-1):
        x = y
        x += i
        stack.append(x)

ans += 1
print(ans)

### FIXED CODE ###

def inp():
    return input()
def iinp():
    return int(input())
def inps():
    return input().split()
def miinps():
    return map(int,input().split())
def linps():
    return list(input().split())
def lmiinps():
    return list(map(int,input().split()))
def lmiinpsf(n):
    return [list(map(int,input().split()))for _ in range(n)]

s = iinp()
z = 10**9+7
ans = 0

dp =[0]*2001

dp[0] = 0
dp[1] = 0
dp[2] = 0
dp[3] = 1
dp[4] = 1
dp[5] = 1
dp[6] = dp[3]+1

for i in range(7,s+1):
    dp[i] = dp[i-1]+dp[i-3]

ans = dp[s] % z
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
ID=[0 for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    for j in range(r-l+1):
        ID[l-1+j]+=1
print(ID.count(m))

### FIXED CODE ###

n,m=map(int,input().split())
L=[]
R=[]
for i in range(m):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)
print(min(R)-max(L)+1 if min(R)-max(L)+1>0 else 0)
### BUGGY CODE ###

import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7
    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    b = list(map(lambda x: lcm_of_all_a // x, a))
    return sum(b) % mode


def write(result):
    print(result)


def lcm(a, b):
    return (a * b) // gcd(a, b)


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


if __name__ == '__main__':
    # unittest.main()
    solve()

### FIXED CODE ###

import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = 1
    for e in a:
        lcm_of_all_a = lcm(lcm_of_all_a, e)

    lcm_of_all_a %= mode
    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode) % mode
        result %= mode
    return result


def write(result):
    print(result)


def lcm(a, b):
    return a // gcd(a, b) * b 


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


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

import sys
from collections import deque

n = int(input())
a = [0] + [int(sys.stdin.readline()) for _ in range(n)]

pushed = deque([1])
button = 1

for _ in range(n):
    if a[button] in pushed:
        print(-1)
        break
    pushed.append(a[button])
    button = a[button]
    if button == 2:
        print(len(pushed) - 1)
        break

### FIXED CODE ###

import sys

n = int(input())
a = [0] + [int(sys.stdin.readline()) for _ in range(n)]

button = 1
count = 0

for _ in range(n):
    if button == 2:
        print(count)
        break
    button = a[button]
    count += 1

if count == n:
    print(-1)
### BUGGY CODE ###

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
resultList = []
for a in range(A + 1):
    for b in range(B + 1):
        for c in range(C + 1):
            if (a + b + c == K):
                resultList.append(a - c)
print(max(resultList))


### FIXED CODE ###

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
if (A >= K):
    print(K)
else:
    if (B >= (K - A)):
        print(A)
    else:
        print(2*A + B - K)
### BUGGY CODE ###

import numpy
N=int(input())
A=list(map(int,input().split()))
B=[A[i]-i for i in range(N)]
print(sum([abs(b-int(numpy.median(B))) for b in B]))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=sorted([A[i]-i for i in range(N)])
if N%2==0:
	C=int((B[int(N/2)]+B[int(N/2-1)])/2)
else:
	C=B[int((N-1)/2)]
print(sum([abs(b-C) for b in B]))
### BUGGY CODE ###

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

table = {}
init_table = {}
move = {}

for i in range(N):
    if A[i] in table:
        move[table[A[i]]], move[i] = i+1, init_table[A[i]]+1
    else:
        if A[i] not in init_table:
            init_table[A[i]] = i
    table[A[i]] = i

T = K
next_idx = 0
remain = [0]
for i in range(1, K+1):
    idx = next_idx
    while idx in move and idx < move[idx]:
        idx = move[idx]
    remain.append(idx)
    if idx in move:
        next_idx = move[idx]
    else:
        next_idx += 1
    if(idx == N and i != K):
        T = K % i
        break

if(T == 0):
    print()
    exit()
idx = remain[T]
ret = []
while idx < len(A):
    while idx in move and idx < move[idx]:
        idx = move[idx]
    if(idx >= len(A)):
        break
    ret.append(A[idx])
    idx += 1

print(*ret)



### FIXED CODE ###

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

if n == 1:
    if k % 2:
        print(*arr)
    else:
        print(*[])
    exit()

table = {}
original_table = {}
move = {}

for i, a in enumerate(arr):
    if a not in table:
        table[a] = i
        original_table[a] = i
    else:
        move[table[a]], move[i] = i + 1, original_table[a] + 1
        table[a] = i

res = {}
idx = 0

for i in range(1, k + 1):
    while idx in move and move[idx] > idx:
        idx = move[idx]

    res[i] = idx
    if idx == len(arr):
        k %= len(res)
        if not k:
            k = len(res)
        break

    if idx in move:
        idx = move[idx]
    else:
        idx += 1

idx = res[k]
response = []

while idx < len(arr):
    while idx in move and move[idx] > idx:
        idx = move[idx]
    if idx < len(arr):
        response.append(arr[idx])
    idx += 1

print(*response)
### BUGGY CODE ###

N, K = map(int, input().split())
S = []

for _ in range(K):
  L, R = map(int, input().split())
  S.extend(range(L,R+1))
  
S.sort()

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

for i in range(N-1):
  DP[i+1] = DP[i]
  for j in S:
    
    if i+j<N:
      DP[i+1][i+j] += DP[i][i]
    else:
      break

#for i in range(N):
  #print(DP[i])
print(DP[N-1][-1]%998244353)

### FIXED CODE ###

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

L = []
R = []

for _ in range(K):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)
  
dp = [0]*(N+5)
dp[1] = 1

for i in range(2, N+1):
  dp[i] = dp[i-1]
  for j in range(K):
    if i-L[j] >= 0:
      dp[i] += dp[i-L[j]]
    if i-R[j]-1 >= 0:
      dp[i] -= dp[i-R[j]-1]
    dp[i] %= 998244353
    
print((dp[N]-dp[N-1])%998244353)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    ans =input().rstrip()
    n = int(input())
    li = [input().split() for i in range(n)]
    a = 0 #先頭がどっちかという情報

    for x in li:
        if x[0] == "1": #反転クエリ
            a = (a+1)%2
        else: #追加クエリ
            if (x[1] == "1" and a == 0) or (x[1] == "2" and a == 1):
                ans = x[2] + ans
            else:
                ans += x[2]

    if a == 0: #先頭が前なら
        print(ans)
    else: #先頭が後なら
        print(ans[::-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

ans = input()
q = int(input())
top = 0
first = str()
last = str()

for i in range(q):
    li =input().split()
    if li[0] =="1":
        top = (top+1)%2
    else:
        if li[1] == "1":
            if top ==0:
                first += li[2]
            else:
                last += li[2]
        else:
            if top ==1:
                first += li[2]
            else:
                last += li[2]

if top == 0:
    ans = first[::-1] + ans + last
else:
    ans = last[::-1] + ans[::-1] + first

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

P=[1,10,9,12,3,4]
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p%6]))%13
            B[c]=(B[c]+A[i])%(10**9+7)
    return B
S=reversed(input())
A=[0]
for p,s in enumerate(S):
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
print(A[5])

### FIXED CODE ###

P=[1,10,9,12,3,4]
m=10**9+7
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    p%=6
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p]))%13
            B[c]=(B[c]+A[i])%m
    return B

S=reversed(input())
A=[0]
for p,s in enumerate(S):
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
print(A[5])
### BUGGY CODE ###

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

ans = 0
sub = []
for i, a in enumerate(A, 1):
    sub.append(a - i)
    ans += abs(a - i)

#print(sub)

#b = min(sub)
for b in range(min(sub), max(sub) + 1):
    #cand = 0
    cand = sum([abs(s - b) for s in sub])
    #for s in sub:
    #    cand += abs(s - b)
    ans = min(ans, cand)
print(ans)


### FIXED CODE ###

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

for i, a in enumerate(A):
    A[i] = a - i

A = sorted(A)
b = A[len(A)//2]

ans = 0
for a in A:
    ans += abs(a - b)

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

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

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

def main():
    n,k = readInt()
    a = readInt()
    ans = []
    res = 1
    for i in range(n):
        x = res
        if i<k:
            res *= a[i]
        else:
            res //= a[i-k]
            res *= a[i]
            if res>x:
                ans.append("Yes")
            else:
                ans.append("No")
    print("\n".join(ans))
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

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

def main():
    n,k = readInt()
    a = readInt()
    ans = ["Yes\n" for i in range(n-k)]
    for i in range(n):
        if i<k:
            continue
        if a[i]>a[i-k]:
            print("Yes")
        else:
            print("No")
    return

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

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

N, Q = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1,N+1)}

for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)

propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1,N+1)))


### FIXED CODE ###

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

N, Q = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1,N+1)}

for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)

propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1,N+1)))
### BUGGY CODE ###

import bisect
n, m, q = map(int, input().split())
Tr = []
for i in range(m):
  Tr.append(list(map(int, input().split())))
Tr.sort(key=lambda x: x[0])
Sc = []
L = [x[0] for x in Tr]
R = [x[1] for x in Tr]
for i in range(q):
  Sc.append(list(map(int, input().split())))
#Sc.sort(key=lambda x: x[0])
#print(Sc)

for i in range(q):
  left, right = Sc[i]
  train_l_ok_id = bisect.bisect_left(L, left)
  counter = 0
  for j in range(train_l_ok_id, m):
    if R[j] <= right:
      counter += 1
  print(counter)

### FIXED CODE ###

n, m, q = map(int, input().split())
Arr = []
for i in range(n+1):
  Arr.append([0] * (n+1))
for i in range(m):
  l, r = map(int, input().split())
  Arr[l][r] += 1
#print(Arr)

B = []
for i in range(n+1):
  B_line = [0]
  for j in range(1, n+1):
    B_line.append(B_line[-1] + Arr[i][j])
  B.append(B_line)
#print(B)
  
for x in range(q):
  left, right = map(int, input().split())
  train_num = 0
  for i in range(left, right+1):
    train_num += B[i][right] - B[i][left-1]
  print(train_num)
### BUGGY CODE ###

h,w=map(int, input().split())
maps=[[0]*w for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            maps[i][j]=-1
    
maps_l=[[0]*w for i in range(h)]
maps_r=[[0]*w for i in range(h)]
maps_u=[[0]*w for i in range(h)]
maps_d=[[0]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if maps[i][j]==-1:
            maps_l[i][j]=0
        elif j==0:
            maps_l[i][j]=1
        else:
            maps_l[i][j]=maps_l[i][j-1]+1

for i in range(h):
    for j in range(w-1,-1,-1):
        if maps[i][j]==-1:
            maps_r[i][j]=0
        elif j==w-1:
            maps_r[i][j]=1
        else:
            maps_r[i][j]=maps_r[i][j+1]+1

for j in range(w):
    for i in range(h):
        if maps[i][j]==-1:
            maps_d[i][j]=0
        elif i==0:
            maps_d[i][j]=1
        else:
            maps_d[i][j]=maps_d[i-1][j]+1

for j in range(w):
    for i in range(h-1,-1,-1):
        if maps[i][j]==-1:
            maps_u[i][j]=0
        elif i==h-1:
            maps_u[i][j]=1
        else:
            maps_u[i][j]=maps_u[i+1][j]+1
ans=0
for i in range(h):
    for j in range(w):
        if maps[i][j]!=-1:
            ans=max(ans,maps_u[i][j]+maps_d[i][j]+maps_r[i][j]+maps_l[i][j]-3)

print(ans)

### FIXED CODE ###

h,w=map(int, input().split())
maps=[[0]*w for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            maps[i][j]=-1
    
maps_l=[[0]*w for i in range(h)]
maps_r=[[0]*w for i in range(h)]
maps_u=[[0]*w for i in range(h)]
maps_d=[[0]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if maps[i][j]==-1:
            maps_l[i][j]=0
        elif j==0:
            maps_l[i][j]=1
        else:
            maps_l[i][j]=maps_l[i][j-1]+1

for i in range(h):
    for j in range(w-1,-1,-1):
        if maps[i][j]==-1:
            maps_r[i][j]=0
        elif j==w-1:
            maps_r[i][j]=1
        else:
            maps_r[i][j]=maps_r[i][j+1]+1

for j in range(w):
    for i in range(h):
        if maps[i][j]==-1:
            maps_d[i][j]=0
        elif i==0:
            maps_d[i][j]=1
        else:
            maps_d[i][j]=maps_d[i-1][j]+1

for j in range(w):
    for i in range(h-1,-1,-1):
        if maps[i][j]==-1:
            maps_u[i][j]=0
        elif i==h-1:
            maps_u[i][j]=1
        else:
            maps_u[i][j]=maps_u[i+1][j]+1
ans=0
for i in range(h):
    for j in range(w):
        if maps[i][j]!=-1:
            ans=max(ans,maps_u[i][j]+maps_d[i][j]+maps_r[i][j]+maps_l[i][j]-3)

print(ans)