Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

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

cnt=0
now=1
cyc=0
visited=[0]*n
flg=False
for i in range(k):
    cnt+=1
    now=a[now-1]
    visited[now-1]+=1
    if visited[now-1]==1:
        cyc+=1
        #print(cyc)
    if visited[now-1]==2:
        flg=True
        cyc-=1
        break
    #print(visited)
#print(cyc,cnt,now,k-cnt+cyc)
if flg:
    for i in range((k-cnt+cyc)%cyc):
        now=a[now-1]
    print(now)
else:
    print(now)

### FIXED CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

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

cnt=0
now=1
cyc=0
visited=[0]*n
flg=False
for i in range(k):
    cnt+=1
    now=a[now-1]
    visited[now-1]+=1
    if visited[now-1]==2:
        cyc+=1
        #print(cyc)
    if visited[now-1]==3:
        flg=True
        #print(visited,cyc,now)
        #cyc-=1
        break
    #print(visited,now)
#print(cyc, cnt, now, (k-cnt+2*cyc) % cyc)
if flg:
    for i in range((k-cnt+2*cyc)%cyc):
        now=a[now-1]
    print(now)
else:
    print(now)
dishes = [int(input()) for i in range(5)] 

d = [abs(d % 10 -10) for d in dishes if d % 10 != 0] # select nums which can be divided by 10
d.remove(max(d)) 
print(sum(dishes) + sum(d))

### FIXED CODE ###

dishes = [int(input()) for i in range(5)] 

d = [abs(d % 10 -10) for d in dishes if d % 10 != 0] # select nums which can be divided by 10
if d: d.remove(max(d)) 
print(sum(dishes) + sum(d))
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
X = [[0 for j in range(w)] for i in range(h)]

xi = -1
hi = 0
for i, ai in enumerate(a):
    for j in range(xi + 1, min(xi + ai + 1, w)):
        X[hi][j] = i + 1
    if j == w - 1:
        hi += 1
        j = -1
        for j in range(max(0, xi + ai + 1 - w)):
            X[hi][j] = i + 1
    xi = j

for i in range(h):
    if i % 2 == 0:
        print(*X[i])
    else:
        print(*X[i][::-1])

### FIXED CODE ###

h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
m = h * w
X = []

for i, ai in enumerate(a):
    X += [i + 1 for _ in range(ai)]

for hi in range(h):
    if hi % 2 == 0:
        print(*X[hi * w:(hi + 1) * w])
    else:
        print(*X[hi * w:(hi + 1) * w][::-1])
N = int(input())
n = "Three"
S = input().split()
for i in range(N):
  If S[i] == "Y":
    n = "Four"
    break

print(n)
    

  

### FIXED CODE ###

N = int(input())
number = "Three"
S = input().split()

for i in range(N):
  if S[i] == "Y":
    number = "Four"
    break

print(number)
#define number of animals and legs
#function for the question can be understood as x=crane+turtles and y=2cranes+4turtles
def equation(numLeg, numAnim):
    for numCrane in range(0, numAnim):
        numTurt=numAnim-numCrane
        totalLeg=4*numTurt+2*numCrane
        if totalLeg==numLeg:
            return[numTurt,numCrane]
    return[None,None]
#input x and y
if __name__ == '__main__':
    x,y=int(input()).split()
    cranes,turtles=equation(y,x)
    if turtles==0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

X,Y = map(int,input().split()) #input number of animals and legs

crane_legs = 2
turtle_legs = 4

answer = "No"

for i in range(X+1): #X+1 because it will only consider 0,1,2
    remaining = X-i
    if crane_legs*i + turtle_legs*remaining == Y:
        answer = "Yes"
#Loop to check combinations of animals is correct

print(answer)
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう

kouho = [x for x in set(A) if A.count(x) == 1]
#target = kouho[:]
maxA = max(kouho)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN):
        buf = A[i]*n
        if buf in kouho:
            kouho.remove(buf)
            #print(A[i]*n)
#target = kouho[:]

print(len(kouho))

### FIXED CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))
s = list(input())
cnt = 0
while True:
    if s[0] == 'T':
        s.pop(0)
        cnt += 1
    else:
        break
    
while True:
    if s[-1] == 'S':
        s.pop(-1)
        cnt += 1
    else:
        break
        
i = 0
now = 'on'
ans = 0
cs = 0
while i < len(s):
    if s[i] == 'S':
        cs += 1
        now = 'on'
        i += 1
    elif now == 'on' and s[i] == 'T':
        i += cs
        cs = 0
        now = 'off'
    elif now == 'off' and s[i] == 'T':
        cnt += 1
        i += 1
        
    if i >= len(s):
        break
print(cnt)

### FIXED CODE ###

s = input()
ans = 0
cnt = 0
for a in s:
    if a == 'S':
        cnt += 1
    else:
        if cnt > 0:
            cnt -= 1
        else:
            ans += 1
print(ans+cnt)
x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

p.sort()
q.sort()
r.sort()
ans=0

z=x+y

while(z!=0):
    while((x!=0)and(y!=0)):
            a=[]
            a.append(p[-1])
            a.append(q[-1])
            a.append(r[-1])
            if max(a)==p[-1]:
                x-=1
                z-=1
                ans+=p[-1]
                p.pop()
            elif max(a)==q[-1]:
                y-=1
                z-=1
                ans+=q[-1]
                q.pop()
            else:
                z-=1
                ans+=r[-1]
                r.pop()
        
    if x==0:
        if q[-1]>=r[-1]:
            y-=1
            z-=1
            ans+=q[-1]
            q.pop() 
        else:
            z-=1
            ans+=r[-1]
            r.pop()
    elif y==0:
        if p[-1]>=r[-1]:
            x-=1
            z-=1
            ans+=p[-1]
            p.pop()
        else:
            z-=1
            ans+=r[-1]
            r.pop()
print(ans)

### FIXED CODE ###

x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

p.sort()
q.sort()
r.sort()
ans=0

z=x+y

while(z!=0):
    while((x!=0)and(y!=0)):
            a=[]
            a.append(p[-1])
            a.append(q[-1])
            a.append(r[-1])
            if max(a)==p[-1]:
                x-=1
                z-=1
                ans+=p[-1]
                p.pop()
            elif max(a)==q[-1]:
                y-=1
                z-=1
                ans+=q[-1]
                q.pop()
            else:
                z-=1
                ans+=r[-1]
                r.pop()
            if z==0:
                break
            if  len(r)==0:
                break
    if len(r)==0:
        break
    if z==0:
        break
        
    if x==0:
        if q[-1]>=r[-1]:
            y-=1
            z-=1
            ans+=q[-1]
            q.pop() 
        else:
            z-=1
            ans+=r[-1]
            r.pop()
            
            
    elif y==0:
        if p[-1]>=r[-1]:
            x-=1
            z-=1
            ans+=p[-1]
            p.pop()
        else:
            z-=1
            ans+=r[-1]
            r.pop()

            
            
if len(r)==0:
    while(z!=0):
        while((x!=0)and(y!=0)):
            a=[]
            a.append(p[-1])
            a.append(q[-1])
            if max(a)==p[-1]:
                x-=1
                z-=1
                ans+=p[-1]
                p.pop()
            elif max(a)==q[-1]:
                y-=1
                z-=1
                ans+=q[-1]
                q.pop()
            if z==0:
                break
        if z==0:
            break
        if x==0:
            y-=1
            z-=1
            ans+=q[-1]
            q.pop() 
        else: 
            x-=1
            z-=1
            ans+=p[-1]
            p.pop()
        
        
        
        
        
        
        
        
        
        
        
        
        
print(ans)
X,N = map(int, input().split())
P = list(map(int, input().split()))

if P.len == 0:
  print(X)
else:
  for i in range(X,1):
    if P.count(X-i) == 0:
      print(X-i)
      break
    elif P.count(X+1) == 0:
      print(X+1)
      break
    else:
      continue

### FIXED CODE ###

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

if len(P) == 0:
  print(X)
else:
  for i in range(0,10000):
    if P.count(X-i) == 0:
      print(X-i)
      break
    elif P.count(X+i) == 0:
      print(X+i)
      break
    else:
      continue
from collections import defaultdict

N = int(input())
g = defaultdict(set)

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)


### FIXED CODE ###


from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = [set() for _ in range(N+1)]

for x, y in [map(int, input().split()) for _ in range(N-1)]:
    g[x].add(y)
    g[y].add(x)

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)
N = int(input())
a = []
for _ in range(N):
    a.append(int(input()))
x = 1
visited = set([1])
answer = 0

while True:
    x = a[x]
    if x in visited:
        answer = -1
        break
    visited.add(x)
    answer += 1
    if x == 2:
        break

print(answer)

### FIXED CODE ###

N = int(input())
a = [0]
for _ in range(N):
    a.append(int(input()))
x = 1
visited = set([1])
answer = 0

while True:
    x = a[x]
    if x in visited:
        answer = -1
        break
    visited.add(x)
    answer += 1
    if x == 2:
        break

print(answer)
import heapq
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
mean_a = sum(a) / k
q = []
for aa in a:
    d = max(math.floor(aa / mean_a), 1)
    q.append((-aa/d, d))
    k -= (d-1)
heapq.heapify(q)

for _ in range(k):
    aa, n = heapq.heappop(q)
    heapq.heappush(q, (aa*n/(n+1), n+1))

ans, _ = heapq.heappop(q)
print(math.ceil(-ans))


### FIXED CODE ###

import heapq
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
if k == 0:
    print(a[0])
    exit(0)
mean_a = sum(a) / k
q = []
for aa in a:
    d = max(math.floor(aa / mean_a), 1)
    q.append((-aa/d, d))
    k -= (d-1)
heapq.heapify(q)

for _ in range(k):
    aa, n = heapq.heappop(q)
    heapq.heappush(q, (aa*n/(n+1), n+1))

ans, _ = heapq.heappop(q)
print(math.ceil(-ans))
import itertools

N = int(input())

evidence_dit = {}

for i in range(N):
    A = int(input())
    x_y = []
    for j in range(A):
        x_y.append(list(map(int,input().split())))
        
        evidence_dit[i+1] =  x_y

attribute = [0,1]
ans = []

for i in itertools.product(attribute,repeat=N):
    for j in range(N):
        if i[j] == 1:
            for k in evidence_dit[j+1]:
                if i[k[0]-1] != k[1]:
                    break
            else:
        
                continue
            break
    else:
        ans.append(i.count(1))
                

print(max(ans))    
    

### FIXED CODE ###

N = int(input())
xy = []
for i in range(N):
    A = int(input())
    xy.append([])
    for j in range(A):
        xy[i].append(tuple(map(int, input().split())))
 
ans = 0
 
for i in range(2 ** N):
    h = [0] * N
 
    for j in range(N):
        if (i >> j) & 1:
            h[j] = 1
    
    flag = False
    for i in range(N):
        if h[i] == 1:
            for x, y in xy[i]:
                if h[x-1] != y:
                    flag = True
                    break
            if flag:
                break
    
    if not flag:
        ans = max(ans, sum(h))
 
print(ans)
n = int(input())
print(a + '+' + a**2  + '+' + a**3)

### FIXED CODE ###

# １変数の標準入力
a = int(input())
# フォーマット関数
print("{}".format(a + a**2 + a**3))
import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = read_input()
K = min(K, 41)

for _ in range(K):
    B = [0]*N
    for i in range(N):
        start = max(i-A[i], 0)
        end = min(i+A[i], N-1)

        B[start] += 1
        if end+1 < N:
            B[end+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()


print(" ".join(map(str, A)))


### FIXED CODE ###

def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = read_input()
K = min(K, 41)

for _ in range(K):
    B = [0]*N
    for i in range(N):
        start = max(i-A[i], 0)
        end = min(i+A[i], N-1)

        B[start] += 1
        if end+1 < N:
            B[end+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()


print(" ".join(map(str, A)))
n = int(input())
a = list(map(int, input().split()))
ca = []
cnt = 0
for i in range(len(a)-1):
  if(a[i]<a[i+1]):
    ca.append(cnt)
    cnt = 0
  else:
    cnt += 1
ans = max(max(ca), cnt)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ca = []
cnt = 0
for i in range(len(a)-1):
  if(a[i]<a[i+1]):
    ca.append(cnt)
    cnt = 0
  else:
    cnt += 1
ca.append(0)
ans = max(max(ca), cnt)
print(ans)
a,b=[int(i) for i in input().split()]

d = b - a

for i in range(1,d):
    h += i

print(h-a)


### FIXED CODE ###

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

d = b - a

h = 0
for i in range(1,d):
    h += i

print(h-a)
a=int(intput())
a+a^2+a^3

### FIXED CODE ###

a=int(input())
print(a+a**2+a**3)
def check(l, r):
    th = 1 + (r - l + 1) // 2 
    for i in range(26):
        if cnt[i] >= th:
            return True
    return False

s = input()
n = len(s)
si = [0] * n
for i in range(n):
    si[i] = ord(s[i]) - 97

l, r = 0, 2
cnt = [0]*26
for i in range(3):
    cnt[si[i]] += 1
while l < n-2 and r < n:
    # print(l, r, cnt)
    if check(l, r):
        print(l+1, r+1)
        exit()
    elif max(cnt) == (r-l) // 2:
        r += 1
        if r < n:
            cnt[si[r]] += 1
    else:
        cnt[si[l]] -= 1
        l += 1     
print(-1, -1)

### FIXED CODE ###

def check(l, r):
    th = 1 + (r - l + 1) // 2 
    for i in range(26):
        if cnt[i] >= th:
            return True
    return False

s = input()
n = len(s)
si = [0] * n
for i in range(n):
    si[i] = ord(s[i]) - 97

l, r = 0, 1
cnt = [0]*26
for i in range(2):
    cnt[si[i]] += 1
while l < n-1 and r < n:
    if check(l, r):
        print(l+1, r+1)
        exit()
    elif max(cnt) == 1 + (r - l + 1) // 2 or r-l == 1:
        r += 1
        if r < n:
            cnt[si[r]] += 1
    else:
        cnt[si[l]] -= 1
        l += 1     
print(-1, -1)
a=int(input())
b=int(input())
c=int(input())
d="No"
if a==(b+c):
        d="Yes"
if b==(c+a):
        d="Yes"
if c==(a+b):
        d="Yes"
print(d)



### FIXED CODE ###

s = list(map(int, input().split()))
a=s[0]
b=s[1]
c=s[2]

d="No"
if a==(b+c):
        d="Yes"
if b==(c+a):
        d="Yes"
if c==(a+b):
        d="Yes"
print(d)
N = int(input())
ans = 0
for i in range(N):
    x, u = str(int,input())
    x = float(x)
    if u == 'JPY':
        ans += x
    else:
        ans += x*380000

print(ans)

### FIXED CODE ###

N = int(input())
mo = 0
for i in range(N):
    x,y = map(str,input().split())
    x = float(x)
    if y == 'JPY':
        mo += x
    else:
        tmp = x*380000
        mo += tmp
print(mo)
a=int(input())
b=[input() for i in range(a)]
c=[AC,WA,TLE,RE]
for value in c:
  print('{0} x {1}'.format(value, b.count(value)))


### FIXED CODE ###

N = int(input())
s = [input() for i in range(N)]
for v in ['AC', 'WA', 'TLE', 'RE']:
  print('{0} x {1}'.format(v, s.count(v)))
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    v, w = V[i-1], W[i-1]
    for j in range(maxL+1):
        if j < w:
            dp[i][j] = dp[i//2][j]
        else:
            dp[i][j] = max(dp[i//2][j], dp[i//2][j - w] + v)

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp //= 2
            idx >>= 1
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()
import sys
A, B, X = map(int, input().split())
def ne(n):
    return A*n + B*len(str(n))
if ne(10**10) <= X:
    print(10**10)
    sys.exit()
high = 10**10
low = 0
ans = (high + low) // 2
while (low < high):
    if ans == 0:
        print(0)
        sys.exit()
    if ne(ans) <= X:
        if ne(ans+1) > X:
            print(ans)
            sys.exit()
        low = ans
    else:
        high = ans
    ans = (high + low) // 2
print(ans)

### FIXED CODE ###

import sys
S = input()
day = ["SAT","FRI","THU","WED","TUE","MON","SUN"]
for i in range(7):
    if S==day[i]:
        print(i+1)
        sys.exit()
N=int(input())
lis=[]
ans=0
for i in range(N):
	x=input()
	try:
		y=lis.index(x)
	except:
		lis+=[x]
		ans+=1
print(ans)


### FIXED CODE ###

[S,W]=[int(i) for i in input().split()]
if S>W:
  print("safe")
else:
  print("unsafe")
N, M = map(int, input().split())
L, R = 1, N

import math

def merge_list(list):
    return (list[-1][0], min(map(lambda x: x[1], list)))

data = []
for i in range(0, M):
    l, r = input().split()
    data.append((int(l), int(r)))
data = sorted(data, key=lambda x: x[0])

def saiki(totyuu):
    if len(totyuu) < 1000:
        mid = int(math.floor(len(totyuu)/2))
        m1 = merge_list(totyuu[:mid])
        m2 = merge_list(totyuu[mid:])
        return merge_list([m1, m2])
    else:
        return merge_list([saiki(totyuu[:mid]), saiki(totyuu[mid:])])

data = saiki(data)

print(max(0, data[1]-data[0]+1))

### FIXED CODE ###

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

Ls = []
Rs = []
for i in range(0, M):
    l, r = input().split()
    Ls.append(int(l))
    Rs.append(int(r))

maxL = max(Ls)
minR = min(Rs)
result = max(0, minR-maxL+1)

print(result)
print(len({input().split()}))

### FIXED CODE ###

print(len({i for i in input().split()}))
from itertools import*;print(sum(p*q*r for p,q,r in combinations([list(s[0]for s in open(0).readlines()).count(s)for s in"MARCH"],3)))

### FIXED CODE ###

import itertools as i;d=[0]*91
for _ in[0]*int(input()):d[ord(input()[0])]+=1
print(sum(d[p]*d[q]*d[r]for p,q,r in i.combinations(map(ord,'MARCH'),3)))
N, a, b = [int(input()) for i in range(3)]

print('Hello World' if N == 1 else str(a + b))

### FIXED CODE ###

N = int(input())

if N == 1:
  print('Hello World')

else:
  print(sum([int(input()) for i in range(2)]))
dp = []
train = []

def subq(l, r):
    global dp, train
    if l == 0 or r == 0:
        return 0
    else:
        tmp1 = dp[l][r]
        if tmp1 != -1:
            return tmp1
        else:
            tmp2 = train[l][r] + subq(l - 1, r) + subq(l, r - 1) -  subq(l - 1, r - 1)
            dp[l][r] = tmp2
            return tmp2

def main():
    global dp, train
    n, m, q = map(int, input().split())
    dp = [[-1] * (n+1) for _ in range(n+1)]
    train = [[0] * (n+1) for _ in range(n+1)]
    for _ in range(m):
        l, r = input().split()
        l = int(l)
        r = int(r)
        train[int(l)][int(r)] += 1


    for _ in range(q):
        p, q = input().split()
        p = int(p)
        q = int(q)
        r = subq(q, q) - subq(p-1, q) - subq(q, p-1) + subq(p-1, p-1)
        print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###


import sys
sys.setrecursionlimit(10**6)
dp = []
train = []

def subq(l, r):
    global dp, train
    if l == 0 or r == 0:
        return 0
    else:
        tmp1 = dp[l][r]
        if tmp1 != -1:
            return tmp1
        else:
            tmp2 = train[l][r] + subq(l - 1, r) + subq(l, r - 1) -  subq(l - 1, r - 1)
            dp[l][r] = tmp2
            return tmp2

def main():
    global dp, train
    n, m, qn = map(int, input().split())
    dp = [[-1] * (n+1) for _ in range(n+1)]
    train = [[0] * (n+1) for _ in range(n+1)]
    for _ in range(m):
        l, r = map(int, input().split())
        train[int(l)][int(r)] += 1

    for _ in range(qn):
        p, q = map(int, input().split())
        r = subq(q, q) - subq(p-1, q) - subq(q, p-1) + subq(p-1, p-1)
        print(r)

if __name__ == '__main__':
    main()
n = input()
i = 0
for number in n:
    if number == '1':
        n[i] = '9'
        i = i + 1
    elif number == '9':
        n[i] = '1'
        i = i + 1
    else:
        i = i + 1

print(n)

### FIXED CODE ###

n = list(input())
i = 0

while i < 3:
    if n[i] == '1':
        n[i] = '9'
        i = i + 1
    else:
        n[i] = '1'
        i = i + 1

print(''.join(n))
iAC = 0
iWA = 0
iTLE = 0
iRE = 0

N = int(input())
for i in range(N):
    S = input()
    if S == "AC":
        iAC += 1
    elif S == "WA":
        iWA += 1
    elif S == "TLE":
        iTLE += 1
    elif S == "RE":
        iRE += 1

print("AC x {}".format(iAC))
print("WA x {}".format(iWA))
print("TLE x {}".format(iTLE))
print("RE x {}".format(iRE))

### FIXED CODE ###

import math
N = int(input())
print(math.ceil(N/1000)*1000 - N)