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

H,W=map(int,input().split())

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

#convert mat to graph
#(i0,j0)->(i1,j1,dist)
graph={}
if mat[0][0]:
  graph[(0,0)]=[(1,1,0)]
else:
  graph[(0,0)]=[(1,1,1)]
  
for i in range(H):
  for j in range(W):
    graph[(i+1,j+1)]=[]
    if mat[i][j]:
      if i<H-1:
        if mat[i+1][j]:
          graph[(i+1,j+1)].append((i+2,j+1,0))
        else:
          graph[(i+1,j+1)].append((i+2,j+1,1))
      if j<W-1:
        if mat[i][j+1]:
          graph[(i+1,j+1)].append((i+1,j+2,0))
        else:
          graph[(i+1,j+1)].append((i+1,j+2,1))
    else:
      if i<H-1:
        graph[(i+1,j+1)].append((i+2,j+1,0))
      if j<W-1:
        graph[(i+1,j+1)].append((i+1,j+2,0))
#print(graph)

# init used,queue,dist
dist={}
queue=set()
dist[(0,0)]=0
queue.add((0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    dist[(i,j)]=10**9
    queue.add((i,j))
#print(queue)

#dkjstra
while(True):
  d=10**9
  min_q=None
  for q in queue:
    if dist[q]<d:
      min_q=q
      d=dist[q]
      
  #print(min_q,d)
  if min_q==None:
    break
    
  queue.remove(min_q)
  candlist=graph[min_q]
  for cand in candlist:
    xx,yy,dd=cand
    dist[(xx,yy)]=min(dist[(xx,yy)],dist[min_q]+dd)
  
print(dist[(H,W)])

### FIXED CODE ###

import heapq

H,W=map(int,input().split())

mat=[]
for i in range(H):
  array=[x=='.' for x in input()]
  mat.append(array)
#print(mat)

#convert mat to graph
#(i0,j0)->(i1,j1,dist)
graph={}
if mat[0][0]:
  graph[(0,0)]=[(1,1,0)]
else:
  graph[(0,0)]=[(1,1,1)]
  
for i in range(H):
  for j in range(W):
    graph[(i+1,j+1)]=[]
    if mat[i][j]:
      if i<H-1:
        if mat[i+1][j]:
          graph[(i+1,j+1)].append((i+2,j+1,0))
        else:
          graph[(i+1,j+1)].append((i+2,j+1,1))
      if j<W-1:
        if mat[i][j+1]:
          graph[(i+1,j+1)].append((i+1,j+2,0))
        else:
          graph[(i+1,j+1)].append((i+1,j+2,1))
    else:
      if i<H-1:
        graph[(i+1,j+1)].append((i+2,j+1,0))
      if j<W-1:
        graph[(i+1,j+1)].append((i+1,j+2,0))
#print(graph)

# init used,queue,dist
dist={}
hq=[]
dist[(0,0)]=0
heapq.heappush(hq,(0,0,0))
for i in range(1,H+1):
  for j in range(1,W+1):
    dist[(i,j)]=10**9
    heapq.heappush(hq,(i+j,i,j))
#print(queue)

#dkjstra
while(True):
  if len(hq)==0:
    break

  ij,ii,jj=heapq.heappop(hq)
  
  candlist=graph[(ii,jj)]
  for cand in candlist:
    xx,yy,dd=cand
    dist[(xx,yy)]=min(dist[(xx,yy)],dist[(ii,jj)]+dd)
  
print(dist[(H,W)])
### BUGGY CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re



def main_sum():
    N,M,K=map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    A_len = len(A)
    B_len = len(B)

    Asum = [0] * (A_len + 1)
    Bsum = [0] * (B_len + 1)

    maxA = 0
    maxB = 0

    add = 0
    for i in range(1,A_len+1):
        add += A[i-1]
        Asum[i] = add
        if add <= K:
            maxA = i + 1
        else:
            break

    add = 0
    for i in range(1,B_len+1):
        add += B[i-1]
        Bsum[i] = add
        if add <= K:
            maxB = i + 1
        else:
            break

    ans = 0
    prevmax = 0
    for i in reversed(range(maxA)):
        for j in range(prevmax,maxB):
            if Asum[i] + Bsum[j] <= K:
                if ans < i + j:
                    ans = i + j
                    prevmax = j
            else:
                break
            if j == maxB - 1:
                print(ans)
                exit()

    print(ans)

main_sum()


### FIXED CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re



def main_sum():
    N,M,K=map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    A_len = len(A)
    B_len = len(B)

    Asum = [0] * (A_len + 1)
    Bsum = [0] * (B_len + 1)

    maxA = len(A) + 1
    maxB = len(B) + 1

    add = 0
    for i in range(1,A_len+1):
        Asum[i] = A[i-1] + Asum[i-1]

    add = 0
    for i in range(1,B_len+1):
        Bsum[i] = B[i-1] + Bsum[i-1]

    ans = 0
    prev = 0
    for i in reversed(range(maxA)):
        for j in range(prev,maxB):
            if Asum[i] + Bsum[j] <= K:
                prev = j
                if ans < i + j:
                    ans = i + j
                if j == (maxB - 1):
                    print(ans)
                    exit()
            else:
                break

    print(ans)




main_sum()
### BUGGY CODE ###

import bisect
import numpy as np
N = int(input())
S = input()

dic_ = {}

for i in range(N):
    dic_[S[i]] = dic_.get(S[i], []) + [i]

ans = [False]*1000

def get_first_pos(i, k):
    if dic_.get(str(i)) is not None:
        ind = bisect.bisect_right(dic_[str(i)], k)
        if ind != len(dic_[str(i)]):
            return dic_[str(i)][ind]
    return None

        
for i in range(10):
    x1 = get_first_pos(i, -1)
    if x1 is None:
        continue
    for j in range(10):
        x2 = get_first_pos(j, x1)
        if x2 is None:       
            continue
        for k in range(10):
            x3 = get_first_pos(k, x2)
            if x3 is None:       
                continue
            ans[int(str(i)+str(j)+str(k))] = True
print(np.count_nonzero(ans))


### FIXED CODE ###

import bisect
import numpy as np
N = int(input())
S = input()

dic_ = {}
array =  np.zeros((10, 300001), np.int8)

for i in range(N):
    array[int(S[i]), i] = 1

def get_first_pos(i, k):
    ar = array[i, k+1:]
    wh = np.where(ar>0)
    if len(wh[0]) > 0:
        return wh[0][0] + k+1
    return None

ans = 0
        
for i in range(10):
    x1 = get_first_pos(i, -1)
    if x1 is None:
        continue
    for j in range(10):
        x2 = get_first_pos(j, x1)
        if x2 is None:       
            continue
        for k in range(10):
            x3 = get_first_pos(k, x2)
            if x3 is None:       
                continue
            ans += 1

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

N, M=map(int,input().split())
a=[0]*0
b=[0]*0
choice=[0]*(N-1)
chosen_a=[0]*(N-1)
chosen_b=[0]*(N-1)
c_patern=0
for i in range(M):
    a_tmp, b_tmp=map(int,input().split())
    a.append(a_tmp)
    b.append(b_tmp)
# for i in range(M):
#     c_point = [0] * N
#     if a[i]==1:
#         c_point[a[i]-1]+=1
#     for j in range(M):
#         if a[j]==b[i]:
# for i in range(N):
#     if c_point[i]!=1:
#         break
#     c_patern+=1
for i in range(pow(M,(N-1))):
    flg=0
    for j in range(N-1):
        choice[j]=i//pow(M,(N-1)-j-1)
        chosen_a[j]=a[choice[j]]
        chosen_b[j]=b[choice[j]]
        i=i%pow(M,(N-1)-j-1)
    if chosen_a[0]!=1:
        flg=1
    for k in range(N-1):
        if k>0:
            if chosen_a[k]!=chosen_b[k-1]:
                tmp=chosen_a[k]
                chosen_a[k]=chosen_b[k]
                chosen_b[k]=tmp
                if chosen_a[k]!=chosen_b[k-1]:
                    flg=1
    chosen_b_sorted=sorted(chosen_b)
    for l in range(N-1):
        if chosen_b_sorted[l]!=l+2:
            flg=1
    if flg==0:
        c_patern+=1
print(c_patern)

### FIXED CODE ###

#ABC054C
import itertools
N, M=map(int,input().split())
a=[0]*0
b=[0]*0
order=list(itertools.permutations(range(N-1) ) )#0～N-2のN-1個の順列ができる。2を足すと、2～Nの配列。
c_patern=0
for i in range(M):
    a_tmp, b_tmp=map(int,input().split())
    a.append(a_tmp)
    b.append(b_tmp)
for i in range(len(order)):
    for j in range(N-1):
        flg = False
        if j==0:
            for k in range(M):
                if (a[k]==1 and b[k]==order[i][0]+2):
                    flg=True
                    break
        else:
            for k in range(M):
                if (a[k]==order[i][j-1]+2 and b[k]==order[i][j]+2) or (a[k]==order[i][j]+2 and b[k]==order[i][j-1]+2):
                    flg=True
                    break
        if flg==False:
            break
    if flg==True:
        c_patern+=1
print(c_patern)
### BUGGY CODE ###

n, m=map(int, raw_input().split())
a=map(int, raw_input().split())
for i in range(m):
	x, y=map(int, raw_input().split())
	a[x-1]=y
	cnt=[0]*(n+1)
	for j in a:
		cnt[j]+=1
	cover=[0]*(n+1)
	result=0
	for j in range(n+1):
		for k in range(min(cnt[j], j)):
			cover[j-k]+=1
	result+=cover.count(0)-1
	print result

### FIXED CODE ###

n, m=map(int, raw_input().split())
a=map(int, raw_input().split())
cnt=[0]*(n+1)
for i in a:
	cnt[i]+=1
cover=[0]*(n+1)
for j in range(n+1):
	for k in range(min(cnt[j], j)):
		cover[j-k]+=1
result=cover.count(0)-1

for i in range(m):
	x, new=map(int, raw_input().split())
	old=a[x-1]
	a[x-1]=new
	cnt[old]-=1
	if cnt[old]<old:
		cover[old-cnt[old]]-=1
		if cover[old-cnt[old]]==0:
			result+=1
	if cnt[new]<new:
		if cover[new-cnt[new]]==0:
			result-=1
		cover[new-cnt[new]]+=1
	cnt[new]+=1
	print result
assert result==cover.count(0)-1
for j in range(n+1):
	for k in range(min(cnt[j], j)):
		cover[j-k]-=1
assert cover==[0]*(n+1)
for i in a:
	cnt[i]-=1
assert cnt==[0]*(n+1)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split(" "))
p = np.array(list(map(int, input().split(" "))))
ex = np.array([(i + 1) / 2 for i in p])
ans = 0
for i in range(0, N - K + 1):
    ans = max(np.sum(ex[i: i + K]), ans)
print(ans)

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
ex = [i + 1 for i in p]
ans = sum(ex[0: K])
max_ans = ans
for i in range(K, N):
    ans += ex[i] - ex[i - K]
    max_ans = max(ans, max_ans)
print(max_ans / 2.0)
### BUGGY CODE ###

import numpy as np
from queue import Queue

N, M, K = list(map(int, input().split()))
A = list(map(int, [0] + input().split()))
B = list(map(int, [0] + input().split()))
cost = 0
ind_a = 0
ind_b = 0
cumsum_a = np.cumsum(A)
cumsum_b = np.cumsum(B)
max_book = 1

queue = Queue()
queue.put([0, 0])
num_book = 0
while not queue.empty():
    a, b = queue.get()
    if a+1 <= N and b <= M:
        if cumsum_a[a + 1] + cumsum_b[b] <= K:
            queue.put([a + 1, b])
            num_book = max(num_book, a + b + 1)
    if a <= N and b+1 <= M:
        if cumsum_a[a] + cumsum_b[b + 1] <= K:
            queue.put([a, b + 1])
            num_book = max(num_book, a + b + 1)

print(num_book)


### FIXED CODE ###

import numpy as np

N, M, K = list(map(int, input().split()))
A = list(map(int, [0] + input().split()))
B = list(map(int, [0] + input().split()))
cost = 0
cumsum_a = np.cumsum(A)
cumsum_b = np.cumsum(B)

num_book = 0
max_a = 0
ind_b = 0
max_b = 0
for i in range(1, N + 1):
    if cumsum_a[i] <= K:
        max_a = i
    else:
        break

for i in range(1, M + 1):
    if cumsum_b[i] <= K:
        max_b = i
    else:
        break

for i in range(max_a, -1, -1):
    for j in range(ind_b, max_b+1):
        if cumsum_b[j] + cumsum_a[i] <= K:
            # print("ok")
            num_book = max(i + j, num_book)
            ind_b = j
        else:
            break
print(num_book)
### BUGGY CODE ###


def read_input():
    n = int(input())
    alist = [-1]

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


    return n, alist

def submit():
    n, alist = read_input()

    through = {}
    curr_button = 1
    steps = 0
    while curr_button not in through.keys():
        through[curr_button] = 1
        curr_button = alist[curr_button]
        steps += 1

        if curr_button == 2:
            break

    if curr_button == 2:
        print(steps)
    else:
        print(-1)



if __name__ == '__main__':
    submit()

### FIXED CODE ###

from collections import defaultdict

def read_input():
    n = int(input())
    alist = [-1]

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


    return n, alist

def submit():
    n, alist = read_input()

    through = defaultdict(int)
    curr_button = 1
    steps = 0
    while through[curr_button] == 0:
        through[curr_button] = 1
        curr_button = alist[curr_button]
        steps += 1

        if curr_button == 2:
            break

    if curr_button == 2:
        print(steps)
    else:
        print(-1)



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

import numpy as np
import math
import functools
import operator
N=int(input())
A = list(map(int, input().split()))
#AA=A.sort()
if A.count(0)>0:
    ans=0
else:
    ans=functools.reduce(operator.mul, A)
if ans>10**18 :
    ans=-1
print(ans)

### FIXED CODE ###

import numpy as np
import math
import functools
import operator
N=int(input())
A = list(map(int, input().split()))
#AA=A.sort()
if A.count(0)>0:
    ans=0
elif N>30 and A.count(1)<10:
    ans=-1
    
else:
    ans=functools.reduce(operator.mul, A)
if ans>10**18 :
    ans=-1
print(ans)
### BUGGY CODE ###

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

res = S

is_rev = False

def add_char(s, f, c, is_rev):
  if(f == "1"):
    return c + s if not is_rev else s + c
  else:
    return s + c if not is_rev else c + s

for _ in range(Q):
  q = input().split()
  
  if(q[0] == '1'): # Ti = 1
    is_rev = not is_rev
  
  else: #Ti = 2
    res = add_char(res, q[1], q[2], is_rev)


print(res[::-1] if is_rev else res)

### FIXED CODE ###

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

res = S

is_rev = False

before = []
after = []

def add_char(s, f, c, is_rev):
  if(f == "1"):
    before.append(c)
  else:
    after.append(c)

for _ in range(Q):
  q = input().split()
  
  if(q[0] == '1'): # Ti = 1
    is_rev = not is_rev
    before, after = after, before
  
  else: #Ti = 2
    add_char(res, q[1], q[2], is_rev)

before.reverse()

res = "".join(before) + (res[::-1] if is_rev else res) + "".join(after)

print(res)
### BUGGY CODE ###

# k の剰余での管理は配列が大きいか
# 適当に枝刈りする
import sys
input = sys.stdin.readline

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    if x==x2 and y==y2:
        print(dp[x][y])
        exit()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))

        
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))
            elif dp[x+dx*j][y+dy*j]==dp[x][y]+1:continue###
            elif dp[x+dx*j][y+dy*j]<=dp[x][y]:break###
    
            
            if x+dx*j==x2 and y+dy*j==y2:
                print(dp[x2][y2])
                exit()

        
print(-1)
### BUGGY CODE ###

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

### FIXED CODE ###

from collections import defaultdict


def solve(input_s: str):
    ans = 0
    n = len(input_s)
    mod = 2019
    dp = defaultdict(int)
    cur = 0
    for i in range(n, -1, -1):
        if i == n:
            dp[0] += 1
        else:
            # cur += ((10 ** (n - i - 1)) * int(input_s[i])) % mod これはnがでかくなるとめちゃめちゃ遅い
            cur += pow(10, n - i - 1, 2019) * int(input_s[i]) % mod
            cur %= mod
            dp[cur] += 1
    for v in dp.values():
        if v > 1:
            ans += v * (v - 1) // 2
    return ans


if __name__ == '__main__':
    S = input()
    print(solve(S))
### BUGGY CODE ###

N = int(input())
A = input().split()

A_set = set(A)

#ボールに書かれている 数字の内訳を辞書に登録
A_dic = {}
#すべてのボールから同じボールを取り出す方法数
all_count = 0

for a in A_set:
    count_a = A.count(a)
    all_count += (count_a * (count_a - 1) // 2)
#    A_dic.update({a:A.count(a)})

#n個あるボールから 1個取り除いた場合の方法数
#すべてのボールから取り出す方法数 - (n-1)通り

for i in range(N):
    C =  A.count(A[i])
#    print(all_count - A_dic.get(A[i])+1)
    print(all_count - C + 1)

### FIXED CODE ###

import collections

N = int(input())
A = input().split()

#A_set = set(A)

#ボールに書かれている 数字の内訳を辞書に登録
A_dic = collections.Counter(A)

#すべてのボールから同じボールを取り出す方法数
all_count = 0

for a in A_dic.keys():
    count_a = A_dic.get(a)
    all_count += (count_a * (count_a - 1) // 2)

#n個あるボールから 1個取り除いた場合の方法数
#すべてのボールから取り出す方法数 - (n-1)通り

for i in range(N):
    print(all_count - A_dic.get(A[i])+1)
### BUGGY CODE ###

import copy
n =int(input())
a=[]
b=[]
c=[]
a =list(map(int,input().split()))
a.sort()
b =list(map(int,input().split()))
b.sort()
c =list(map(int,input().split()))

c.sort()
c2 = copy.copy(c)
b_limit = 0
c_limit =0
count =0
c_count =0
b_score =[0]*n
for i in a:
    c_count =0
    c = copy.copy(c2)
    if b_limit == 1:
        break
    for j in  reversed(range(len(b))):
        if b[j] <= i:
            if b[j] == max(b):
                b_limit +=1
            break
        else:
            if not b_score[j] == 0:
                count += b_score[j]
                continue
            if len(c) ==0:
                count +=c_count
                if b_score[j] ==0:
                    b_score[j] = c_count
                continue
        for k in reversed(range(len(c))):
            if c[k] <= b[j]:
                count += c_count
                if b_score[j] ==0:
                    b_score[j] = c_count
                break
            c.pop(k)
            c_count +=1
            if k == 0:
                count +=c_count
                if b_score[j] ==0:
                    b_score[j] = c_count
print(count)



### FIXED CODE ###

import bisect

ans =0

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

for i in b:
    s = bisect.bisect_right(c,i)
    s_num = n-s

    t = bisect.bisect_left(a,i)
    t_num = t

    ans += s_num * t_num

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

def solve():
  n,p = (int(i) for i in input().split())
  upper = round(p**(1/n))
  for i in range(upper+1,0,-1):
    if p%(i**n) == 0:
      print(i)
      exit()
  
solve()

### FIXED CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(1000000)

def solve():
  n,p = (int(i) for i in input().split())
  ans = 1
  if n == 1:
    print(p)
    exit()
  p_dummy = p
  for i in range(2,int(p_dummy**0.5)+4):
    ct = 0
    while p_dummy%i == 0:
      ct += 1
      p_dummy //= i
      if ct >= n:
        ans *= i
        ct -= n
  

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

N = int(input())
H = list(map(int, input().split()))
ans = 0
a = 0
for i in range(N-1):
    n = 0
    for j in range(a,N-1):
        if H[j] >= H[j+1]:
            n += 1
        else:
            a = j+1
            break
    ans = max(ans,n)
print(ans)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
c = 0
ans = 0
for i in range(N-1):
    if H[i] >= H[i+1]:
        c += 1
    else:
        c = 0
    ans = max(ans,c)
print(ans)
### BUGGY CODE ###

import bisect


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

for _ in range(m):
    a_tmp = a.pop()
    a_tmp //= 2
    index = bisect.bisect_left(a,a_tmp)
    a.insert(index,a_tmp)


print(sum(a))

### FIXED CODE ###

import heapq

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

heapq.heapify(a)

for _ in range(m):
    x = heapq.heappop(a) * -1
    x //= 2
    heapq.heappush(a,-1*x)
print(-sum(a))
### BUGGY CODE ###

import sys

A,B,K = map(int, input().split())
for i in range(A,B+1):
  if i <= A + K-1 or i>= B-K+1:
    print(i)

### FIXED CODE ###

import sys
P = []
A,B,K = map(int, input().split())

for i in range(A,min(B,A+K)):
  print(i)
  P.append(i)
for i in range(max(A,B-K+1),B+1):
  if i not in P:
    print(i)
### BUGGY CODE ###

import numpy as np

def solve(n, a, lst):
  m = max(max(lst), a)
  ans = np.zeros((n+1, n+1, n*m+1))
  #ans[i][j][k] : lst[:i]までの中からj枚選んで合計kにする選び方
  for i in range(n+1):
    for j in range(n+1):
      for k in range(n*m+1):
        if i == 0 and j == 0 and k == 0:
          ans[i][j][k] = 1
        elif i >= 1 and k < lst[i-1]:
          ans[i][j][k] = ans[i-1][j][k]
        elif i >= 1 and lst[i-1] <= k and j >= 1:
          ans[i][j][k] = ans[i-1][j-1][k-lst[i-1]] + ans[i-1][j][k]
        else:
          ans[i][j][k] = 0
  ret = 0
  for i in range(1,n+1):
    ret += ans[-1][i][i*a]
  return int(ret)

if __name__ == "__main__":
  n, a = map(int,input().split())
  x_list = [int(i) for i in input().split()]
  ans = solve(n,a,x_list)
  print(ans)


### FIXED CODE ###

def solve(n, a, lst):
  m = max(max(lst), a)
  ans = [[[0]*(n*m+1) for i in range(n+1)] for j in range(n+1)]
  #ans[i][j][k] : lst[:i]までの中からj枚選んで合計kにする選び方
  for i in range(n+1):
    for j in range(n+1):
      for k in range(n*m+1):
        if i == 0 and j == 0 and k == 0:
          ans[i][j][k] = 1
        elif i >= 1 and k < lst[i-1]:
          ans[i][j][k] = ans[i-1][j][k]
        elif i >= 1 and lst[i-1] <= k and j >= 1:
          ans[i][j][k] = ans[i-1][j-1][k-lst[i-1]] + ans[i-1][j][k]
        else:
          ans[i][j][k] = 0
  ret = 0
  for i in range(1,n+1):
    ret += ans[-1][i][i*a]
  return int(ret)

if __name__ == "__main__":
  n, a = map(int,input().split())
  x_list = [int(i) for i in input().split()]
  ans = solve(n,a,x_list)
  print(ans)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
	N, M, Q = MAP()
	LR = [LIST() for _ in range(M)]

	x = [[0]*N for _ in range(N)]
	for L, R in LR:
		x[L-1][R-1] += 1

	pq = [LIST() for _ in range(Q)]

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

	for i in range(N):
		tmp = 0
		C[i] = list(accumulate(x[i]))

	for p, q in pq:
		p = p-1
		q = q-1
		ans = 0
		for i in range(p, q+1):
			if p-1 <= -1:
				ans += C[i][q]
			else:
				ans += C[i][q]-C[i][p-1]
		print(ans)

if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
	N, M, Q = MAP()
	LR = [LIST() for _ in range(M)]

	x = [[0]*N for _ in range(N)]
	for L, R in LR:
		x[L-1][R-1] += 1

	pq = [LIST() for _ in range(Q)]

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

	for i in range(N):
		tmp = 0
		C[i] = list(accumulate(x[i]))

	for p, q in pq:
		p = p-1
		q = q-1
		ans = 0
		for i in range(p, q+1):
			if p-1 <= -1:
				ans += C[i][q]
			else:
				ans += C[i][q]-C[i][p-1]
		print(ans)

if __name__ == "__main__":
	main()