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

from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for i in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append([h, w, 0])

ans = 0
while len(black_cells) > 0:
    one_black_cell = black_cells.popleft()  # キューとして使うのでpop()ではなくpopleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = one_black_cell[0] + dy
        nw = one_black_cell[1] + dx
        d = one_black_cell[2]
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if grid[nh][nw] == '.':
            grid[nh][nw] = '#'
            black_cells.append([nh, nw, d + 1])
        ans = d

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for i in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append([h, w, 0])

ans = 0
while len(black_cells) > 0:
    one_black_cell = black_cells.popleft()  # キューとして使うのでpop()ではなくpopleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = one_black_cell[0] + dy
        nw = one_black_cell[1] + dx
        d = one_black_cell[2]
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if grid[nh][nw] == '.':
            grid[nh][nw] = '#'
            black_cells.append([nh, nw, d + 1])
        ans = d

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

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    btn = [int(input())-1 for _ in range(N)]
    i = 0
    li = [0]
    #print(btn)
    
    for _ in range(N):
        k = btn[i]
        #print(k, li)
        if k in li:
            print('-1')
            break
        else:
            if k != 1:
                li.append(k)
            else:
                print(len(li))
                break
        i = k
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    btn = [int(input())-1 for _ in range(N)]
    i = 0
    li = [False]*N
    #print(btn)
    
    for _ in range(N):
        li[i] = True
        k = btn[i]
        
        #print(k, li)
        if li[k]:
            print('-1')
            break
        elif k == 1:
            print(sum(li))
            break
        
        i = k
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
import fractions
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def is_prime(num):
    for i in range(2, num):  # 第二引数は sqrt(num)+1 でも良い
        if num % i == 0:
            return False

    return True

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

g = fractions.gcd(A, B)

# print(g)
div = make_divisors(g)
# print(div)
p = [i for i in div if is_prime(i)]
# print(p)
print(len(p))
# 2

### FIXED CODE ###

import math
import fractions
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def is_prime(p):
    if p == 1:
        return False
    for i in range(2,int(p ** .5) + 1):
        if p % i == 0:
            return False
    return True

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

g = fractions.gcd(A, B)

div = make_divisors(g)
ans = 1
for i in div:
    if is_prime(i):
        ans += 1
print(ans)
### BUGGY CODE ###

input()
b = [int(i) for i in input().split()]

if 0 not in b:
  last = 1
  for i in b:
      last*=i

  if last > 10**18:
      last = -1

else:
  last = 0
print(last)

### FIXED CODE ###

input()
b = [int(i) for i in input().split()]

if 0 not in b:
  last = 1
  for i in b:
      last*=i
      if last > 10**18:
        last = -1
        break
    
else:
  last = 0
    
print(last)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

ans = [str(a.index(x)+1) for x in range(1, n+1)]

print(" ".join(ans))

### FIXED CODE ###

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

l = [[] for x in range(n)]
for i, num in enumerate(a):
    l[num-1] = (int(i) + 1)

print(*l)
### BUGGY CODE ###

def resolve():
    N = int(input())
    g = {}
    edges = []
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append(b-1)
        g.setdefault(b-1, [])
        g[b-1].append(a-1)
        edges.append((a-1, b-1))

    nodes = [(None, 0)]
    colors = [[None for _ in range(N)] for _ in range(N)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        #print(colors)
        #print(prev, node, prevcol)
        #print(cols)
        idx = 0
        for col in range(1, len(g[node])+1):
            if col == prevcol:
                continue
            nxt = g[node][idx] 
            if colors[node][nxt] is not None:
                idx += 1
                if idx >= len(g[node]):
                    break
                nxt = g[node][idx]
            colors[node][nxt] = col
            colors[nxt][node] = col
            nodes.append((col, nxt))
            idx += 1
            if idx >= len(g[node]):
                break
            
    
    print(maxdeg)
    for src, dst in edges:
        print(colors[src][dst])
            
            




if '__main__' == __name__:
    resolve()


### FIXED CODE ###

def resolve():
    N = int(input())
    g = {}
    edges_to_idx = {}
    edges = []
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        g.setdefault(a-1, [])
        g[a-1].append(b-1)
        g.setdefault(b-1, [])
        g[b-1].append(a-1)
        edges_to_idx.setdefault("{}-{}".format(a-1, b-1), i)
        edges_to_idx.setdefault("{}-{}".format(b-1, a-1), i)
        edges.append((a-1, b-1))

    nodes = [(None, 0)]
    colors = [None for _ in range(N-1)]
    maxdeg = 0
    while nodes:
        prevcol, node = nodes.pop()
        maxdeg = max(maxdeg, len(g[node]))
        idx = 0
        for col in range(1, len(g[node])+1):
            if col == prevcol:
                continue
            nxt = g[node][idx]
            coloridx = edges_to_idx["{}-{}".format(node, nxt)] 
            if colors[coloridx] is not None:
                idx += 1
                if idx >= len(g[node]):
                    break
                nxt = g[node][idx]
                coloridx = edges_to_idx["{}-{}".format(node, nxt)] 
            colors[coloridx] = col
            nodes.append((col, nxt))
            idx += 1
            if idx >= len(g[node]):
                break
            
    
    print(maxdeg)
    for col in colors:
        print(col)
            
            




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

def comb_mod(n,r,m):
    ans = 1
    for i in range(1,r+1):
        ans *= (n-i+1) % m
        ans *= pow(i,m-2,m) % m
        ans = ans % m
    return ans
n,k = map(int,input().split())
m = 10**9+7
for i in range(1,k+1):
    print(comb_mod(n-k+1, i, m)*max(1,comb_mod(k-1, i-1, m))%m)

### FIXED CODE ###

def factorial_mod(n,mod):
    ret = 1
    for i in range(1,n+1):
        ret *= i
        ret %= mod
    return ret
def comb_mod(n,r,mod):
    if r > n or r < 0:
        ret = 0
    else:
        fact_n  = factorial_mod(n, mod)
        fact_r  = factorial_mod(r, mod)
        fact_nr = factorial_mod(n-r, mod)
        ret = fact_n * pow(fact_r, mod-2, mod) * pow(fact_nr, mod-2, mod) % mod
    return ret

n,k = map(int,input().split())
m = 10**9+7
for i in range(1,k+1):
    print(comb_mod(n-k+1, i, m)*comb_mod(k-1, i-1, m)%m)
### BUGGY CODE ###

n = int(input())
nums =[]

for i in range(n):
  nums.append(int(input()))

nums.sort()
a = [nums.pop()]

while not len(nums) == 0:
  try:
    a.insert(0,nums.pop(0))
    a.append(nums.pop(0))
    a.insert(0,nums.pop())
    a.append(nums.pop())
  except IndexError:
    pass

tmp_1 = abs(a[-1] - a[-2])
tmp_2 = abs(a[-1] - a[0])

if tmp_1 < tmp_2:
  a.insert(0,a.pop())

sub = 0
for i in range(1, len(a)):
  sub += abs(a[i-1]-a[i])
print(sub)


### FIXED CODE ###

from collections import deque
n = int(input())
nums =[]

for i in range(n):
  nums.append(int(input()))

nums.sort()
nums = deque(nums)
a = [nums.pop()]
a = deque(a)

while not len(nums) == 0:
  try:
    a.appendleft(nums.popleft())
    a.append(nums.popleft())
    a.appendleft(nums.pop())
    a.append(nums.pop())
  except IndexError:
    pass

tmp_1 = abs(a[-1] - a[-2])
tmp_2 = abs(a[-1] - a[0])

if tmp_1 < tmp_2:
  a.appendleft(a.pop())

sub = 0
for i in range(1, len(a)):
  sub += abs(a[i-1]-a[i])
print(sub)
### BUGGY CODE ###

from itertools import combinations
N=int(input())
triangle=[]
count=0
L=list(map(int,input().split()))
for i in combinations(L,3):
    triangle.append(list(i))
for i in triangle:
    #print(i)
    if i[0]<i[1]+i[2] and i[1]<i[2]+i[0] and i[2]<i[1]+i[0]:
        count+=1
print(count)

### FIXED CODE ###

from bisect import bisect_left
N=int(input())
triangle=[]
count=0
L=list(map(int,input().split()))
L.sort()
#print(L)
for a in range(N):
    for b in range(a+1,N):
        c=L[a]+L[b]
        zahyo=bisect_left(L,c)
        count+=max(0,zahyo-b-1)
print(count)
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [str(input().rstrip('\n')) for _ in range(h)]
    L = [[0] * w for _ in range(h)]
    R = [[0] * w for _ in range(h)]
    U = [[0] * w for _ in range(h)]
    D = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                L[i][j] = 0
            else:
                if i == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i - 1][j] + 1
            if s[-i-1][j] == "#":
                R[-i-1][j] = 0
            else:
                if i == 0:
                    R[-i-1][j] = 1
                else:
                    R[-i-1][j] = R[-i][j] + 1
            if s[i][j] == "#":
                U[i][j] = 0
            else:
                if j == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i][j-1] + 1
            if s[i][-j-1] == "#":
                D[i][-j-1] = 0
            else:
                if j == 0:
                    D[i][-j-1] = 1
                else:
                    D[i][-j-1] = D[i][-j] + 1
    mn = 0
    for i in range(h):
        for j in range(w):
            mn = max(mn, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)
    print(mn)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    h, w = map(int, input().split())
    lst = []
    for i in range(h):
        lst.append(list(input()))

    R = [[0] * w for _ in range(h)]
    L = [[0] * w for _ in range(h)]
    U = [[0] * w for _ in range(h)]
    D = [[0] * w for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if lst[i][j] == '.':
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j - 1] + 1

    for i in range(h):
        for j in range(w - 1, -1, -1):
            if lst[i][j] == '.':
                if j == w - 1:
                    R[i][j] = 1
                else:
                    R[i][j] = R[i][j + 1] + 1

    for i in range(h):
        for j in range(w):
            if lst[i][j] == '.':
                if i == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i - 1][j] + 1

    for i in range(h - 1, -1, -1):
        for j in range(w):
            if lst[i][j] == '.':
                if i == h - 1:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i + 1][j] + 1

    ans = 0
    x = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            x[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, max(x[i]))
    print(ans)


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

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a2=list(range(n))
for f in range(k):
    a1=[0]*(n+1)
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a2[0]=a1[0]
    for x in range(1,n):    
        a2[x]=a2[x-1]+a1[x]
    if a2==a:
        break
    else:
        a=a2[:]
for i in range(n):
    print(a[i])

### FIXED CODE ###

from numba import njit

@njit(cache=True)
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [False] * (A[-1]+1)

for a in A:
    B[a] = True

i = 0
while i < len(A)-1:
    if A[i] == A[i+1]:
        B[A[i]] = False
        A.pop(i)
    i += 1

for a in A:
    for x in range(2*a, len(B), a):
        B[x] = False

print(sum(B))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [False] * (A[-1]+1)

for a in A:
    B[a] = True

for i in range(len(A)-1):
    a = A[i]
    if B[a] == True:
        if A[i] == A[i+1]:
            B[a] = False
        for x in range(2*a, len(B), a):
            B[x] = False

print(sum(B))
### BUGGY CODE ###

N,M = map(int,input().split(' '))
l = [int(input()) for i in range(M)]

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

for i in range(2,N+1):
    if i in l:
        dp[i] = 0
        continue
    else:
        dp[i] = dp[i-1]%mod + dp[i-2]%mod
        dp[i] = dp[i]%mod

print(dp[N]%mod)

### FIXED CODE ###

N,M = map(int,input().split(' '))
l = set([int(input()) for i in range(M)])

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

for i in range(2,N+1):
    if i in l:
        dp[i] = 0
        continue
    else:
        dp[i] = dp[i-1]%mod + dp[i-2]%mod
        dp[i] = dp[i]%mod

print(dp[N]%mod)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

now = 0
count = 0
while True:
    if now == 0 and count != 0:
        print(-1)
        break

    if now == 1:
        print(count)
        break

    now = A[now] - 1
    count += 1


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

now = 0
count = 0
while True:
    if count >= N:
        print(-1)
        break

    if now == 1:
        print(count)
        break

    now = A[now] - 1
    count += 1
### BUGGY CODE ###

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

ans = 0
for i, j in enumerate(p):
    if i == 0:
        ans += 1
        continue
    else:
        if j < min(p[:i]):
            ans += 1
            
print(ans)

### FIXED CODE ###

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

minval = p[0]
ans = 1
for i in p:
    if i < minval:
        ans += 1
        minval = i

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

N = int(input())
A = [int(i) for i in input().split()]

s = []
for i in range(N):
    s.append(str(A.index(i+1)+1))

ans = ' '.join(s)
print(ans)

### FIXED CODE ###

from collections import deque
N = int(input())
A = [int(i) for i in input().split()]
values = [str(i+1) for i in range(N)]
dic = {key: val for key, val in zip(A, values)}
dic_s = deque(sorted(dic.items()))
s =deque()
for i in range(N):
    s.append(dic_s[i][1])

ans = ' '.join(list(s))
print(ans)
### BUGGY CODE ###

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

prod = 1
for i in range(k):
    prod *= As[i]
prods = [prod]

for i in range(k, n):
    prod //= As[i-k]
    prod *= As[i]
    prods.append(prod)
# print(*prods)
prev = prods[0]
for i in range(1,len(prods)):
    if prev < prods[i]:
        print("Yes")
    else:
        print("No")
    prev = prods[i]

### FIXED CODE ###

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


for i in range(k, n):
    if As[i-k] < As[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(k):
    if a>=1:
        a-=1
    elif a==0 and b==0:
        pass
    else:
        if b>=1:
            b-=1
print(a,b)


### FIXED CODE ###

a,b,k=map(int,input().split())
if k<=a:
    print(a-k,b)
elif a<k<=a+b:
    print(0,b-k+a)
elif a+b<k:
    print(0,0)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
l_ls = list(map(int, input().split()))

count = 0
for a,b in combinations(l_ls,2):
    diff = abs(a-b)
    Sum = a + b
    for c in l_ls:
        if c > diff and c < Sum:
            count += 1
    if a > diff and a < Sum:
            count -= 1
    if b > diff and a < Sum:
            count -= 1
print(count//3)


### FIXED CODE ###

n = int(input())
l_ls = list(map(int, input().split()))
l_ls.sort()
stick_count = [0] * (10**3+1)
stick_csum = [0] * (10**3+1)
for i in range(n):
    stick_count[l_ls[i]] += 1
now = 0
for i in range(10**3+1):
    now += stick_count[i]
    stick_csum[i] = now

ans = 0
for first_i in range(n):
    for second_i in range(first_i+1, n):
        #境界は含まない
        greater_than = abs(l_ls[first_i] - l_ls[second_i])
        smaller_than = min(10**3+1,l_ls[first_i] + l_ls[second_i])
        num_canmake = max(0, stick_csum[smaller_than-1] - stick_csum[greater_than])
        if greater_than < l_ls[first_i] < smaller_than:
            num_canmake -= 1
        if greater_than < l_ls[second_i] < smaller_than:
            num_canmake -= 1
        num_canmake = max(0,num_canmake)
        ans += num_canmake
print(ans//3)
### BUGGY CODE ###

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

H.sort(reverse=True)

K = min(K, len(H))
for k in range(K):
    H.pop(0)

print(sum(H))

### FIXED CODE ###

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

H.sort(reverse=True)

K = min(K, len(H))
HH = H[K:]

print(sum(HH))
### BUGGY CODE ###

def main():
    from bisect import bisect_right as br
    import numpy as np
    n = int(input())
    a = np.array(list(map(int, input().split())))
    b = np.array(list(map(int, input().split())))
    #n = 100000
    #a = np.array([i+1 for i in range(n)])
    #b = np.array([2*i+2 for i in range(n)])
    a = np.sort(a)
    b = np.sort(b[::-1])
    m = n % 2
    xor = 0
    for i in b:
        xor ^= i
    b = pow(2, 28) - b
    ans = 0
    for loop in range(28, -1, -1):
        j = pow(2, loop)
        k = (xor & j) // j
        temp = br(b, j-1)
        b[temp:] -= j
        b = np.sort(b)
        temp = br(a, j-1)
        k += np.sum((a & j) // j)
        a[temp:] -= j
        x = (k+br(b, 0))*m % 2
        a = np.sort(a)
        l = 0
        for i in a:
            while l < n:
                if i >= b[l]:
                    l += 1
                else:
                    break
            x += l % 2
        ans += (x % 2)*j
    print(ans)


main()


### FIXED CODE ###

def main():
    from bisect import bisect_right as br
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())), reverse=True)
    m = n % 2
    xor = 0
    for i in b:
        xor ^= i
    for i in range(n):
        b[i] = 2**28 - b[i]
    ans = 0
    for loop in range(28, -1, -1):
        j = pow(2, loop)
        k = (xor & j) // j
        temp = br(b, j-1)
        for i in range(temp, n):
            b[i] -= j
        b.sort()
        temp = br(a, j-1)
        for i in a[:temp]:
            k += (i & j) // j
        for i in range(temp, n):
            k += (a[i] & j) // j
            a[i] -= j
        x = (k+br(b, 0))*m % 2
        a.sort()
        l = 0
        for i in a:
            while l < n:
                if i >= b[l]:
                    l += 1
                else:
                    break
            x += l % 2
        ans += (x % 2)*j
    print(ans)


main()
### BUGGY CODE ###

X = int(input())

for a in range(0, 10**9):
    a *= a
    bb = X + a**5
    B = bb**0.2

    if isinstance(B, float):
        if B.is_integer():
            print(int(B), a)
            break

    a *= -1
    bb = X + a**5
    B = bb**0.2
    if isinstance(B, float):
        if B.is_integer():
            print(int(B), a)
            break


### FIXED CODE ###

def f(B):
    if isinstance(B, float):
        if abs(B - int(B)) < 10**-6:
            return True
        else:
            return False
    return False


X = int(input())

for a in range(0, 10**5):
    bb = X + a**5
    B = bb**0.2
    if f(B):
        print(int(B), a)
        break

    a *= -1
    bb = X + a**5
    B = bb**0.2
    if f(B):
        print(int(B), a)
        break
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from collections import deque
n = int(input())
l = deque([int(input()) for _ in range(n)][::-1])

for i in range(n):
    num = l.pop()
    print(max(l))
    l.appendleft(num)
        
        

### FIXED CODE ###

n = int(input())
l = [int(input()) for _ in range(n)]
max_num = max(l)
second_num = sorted(l)[-2]

for i in range(n):
   if l[i] == max_num:
       print(second_num)
   else:
       print(max_num)
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
d=1
mx=0
i=1
while i<n:
  if(h[i]>h[i-1]):
    if(d>mx):
      mx=d
    d=1
  else:
    d+=1
print(mx)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
d=0
mx=0
i=1
while i<n:
    if(h[i]>h[i-1]):
        if(d>mx):
            mx=d
        d=0
    else:
        d+=1
    i+=1
print(max(mx,d))
### BUGGY CODE ###

N,M,Q = map(int,input().split())
toshi = []
for i in range(M):
  toshi.append(list(map(int,input().split())))
query = []
for i in range(Q):
  query.append(list(map(int,input().split())))
grid = []
for i in range(N+1):
  grid.append([0]*(N+1))
for i in range(M):
  grid[toshi[i][1]][toshi[i][0]] += 1
for i in range(1,N+1):
  for j in range(1,N+1):
    grid[i][j] += grid[i][j-1]
for i in range(Q):
  ans = 0
  for j in range(query[i][1]-query[i][0]+1):
    ans += (grid[query[i][0]+j][query[i][1]]-grid[query[i][0]+j][query[i][0]-1])
  print(ans)

### FIXED CODE ###

N,M,Q = map(int,input().split())
toshi = []
for i in range(M):
  toshi.append(tuple(map(int,input().split())))
query = []
for i in range(Q):
  query.append(tuple(map(int,input().split())))
grid = []
for i in range(N+1):
  grid.append([0]*(N+1))
for i in range(M):
  grid[toshi[i][1]][toshi[i][0]] += 1
for i in range(1,N+1):
  for j in range(1,N+1):
    grid[i][j] += grid[i][j-1]
for i in range(Q):
  ans = 0
  for j in range(query[i][1]-query[i][0]+1):
    ans += (grid[query[i][0]+j][query[i][1]]-grid[query[i][0]+j][query[i][0]-1])
  print(ans)
### BUGGY CODE ###

n,m=map(int, input().split())
pl=[0]*m
yl=[0]*m
sl={}
cl=[0]*m
for i in range(m):
    p,y = map(int, input().split())
    pl[i]=p
    yl[i]=y
    if not p in sl:
        sl[p] = []
    sl[p].append((y, i))

for k, s in sl.items():
    sl[k] = sorted(s)

for i in range(m):
    p=pl[i]
    for j, tl in enumerate(sl[p]):
        if tl[1]==i:
            cl[i] = j+1

for i in range(m):
    print("%06d%06d" % (pl[i], cl[i]))


### FIXED CODE ###

import bisect
n,m=map(int, input().split())
pl=[0]*100000
yl=[0]*100000
ol=[[] for i in range(100001)]
for i in range(m):
    pl[i],yl[i] = map(int, input().split())
    ol[pl[i]].append(yl[i])
for i in range(1,n+1):
    ol[i].sort()
for i in range(m):
    print("%06d%06d" % (pl[i], bisect.bisect_right(ol[pl[i]], yl[i])))