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

import math
from functools import reduce

class abc_162:
    
    def __init__(self):
        pass
        
    def C(self):
        K=int(input())
        sum_gcd=0
        
        for i in range(1,K+1):
            for j in range(1,K+1):
                for k in range(1,K+1):
                    sum_gcd+=self.gcd(i,j,k)
        
        print(sum_gcd) 


    def gcd(self,*numbers):
        return reduce(math.gcd,numbers)


if __name__=='__main__':
    obj=abc_162()
    obj.C()

### FIXED CODE ###

import math
from functools import reduce

class abc_162:
    
    def __init__(self):
        pass
        
    def C(self):
        K=int(input())
        sum_gcd=0
        
        for i in range(1,K+1):
            for j in range(1,K+1):
                for k in range(1,K+1):
                    sum_gcd+=self.gcd(i,j,k)
        
        print(sum_gcd) 


    def gcd(self,*numbers):
        return reduce(math.gcd,numbers)


if __name__=='__main__':
    obj=abc_162()
    obj.C()
### BUGGY CODE ###

def RevFlag(flag):
    if flag:
        return False
    else:
        return True

def main():
    S = input()
    N = int(input())
    rev = False
    for i in range(N):
        Q = [i for i in input().split()]
        if len(Q) == 1:
            rev = RevFlag(rev)
        else:
            F = int(Q[1])
            C = Q[2]
            if F == 1:
                if rev:
                    S = '{}{}'.format(S, C)  # 末尾
                else:
                    S = '{}{}'.format(C, S)  # 先頭
            else:
                if rev:
                    S = '{}{}'.format(C, S)  # 先頭
                else:
                    S = '{}{}'.format(S, C)  # 末尾
    if rev:
        S = ''.join(list(reversed(S)))
    print(S)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def RevFlag(flag):
    if flag:
        return False
    else:
        return True

def main():
    from collections import deque
    S = input()
    d = deque()
    for s in S:
        d.append(s)
    N = int(input())
    rev = False

    for i in range(N):
        Q = [i for i in input().split()]
        if len(Q) == 1:
            rev = RevFlag(rev)
        else:
            F = int(Q[1])
            C = Q[2]
            if F == 1:
                if rev:
                    d.append(C)  # 末尾
                else:
                    d.appendleft(C)  # 先頭
            else:
                if rev:
                    d.appendleft(C)  # 先頭
                else:
                    d.append(C)  # 末尾
    if rev:
        d = ''.join(list(reversed(d)))
    else:
        d = ''.join(list(d))
    print(d)


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

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
start = []
q = deque([])

def bfs():
  #q = deque([(y, x)])
  searched = [[0 for _ in range(w)] for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      if 0 <= y+dy < h and 0 <= x+dx < w and searched[y+dy][x+dx] == 0 and a[y+dy][x+dx] == '.' and cnt[y+dy][x+dx] > cnt[y][x]+1:
        searched[y+dy][x+dx] = 1
        q.append([y+dy, x+dx])
        cnt[y+dy][x+dx] = cnt[y][x]+1

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      start.append([i, j])
      cnt[i][j] = 0
      q.append([i, j])

#for i, j in start:
  #bfs(i, j)
bfs()
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
searched = [[0 for _ in range(w)] for _ in range(h)]
q = deque([])

def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      next_y = y + dy
      next_x = x + dx 
      if 0 <= next_y < h and 0 <= next_x < w and searched[next_y][next_x] == 0 and a[next_y][next_x] == '.' and cnt[next_y][next_x] > cnt[y][x]+1:
        searched[next_y][next_x] = 1
        q.append([next_y, next_x])
        cnt[next_y][next_x] = cnt[y][x]+1

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0
      searched[i][j] = 1
      q.append([i, j])

bfs()
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

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

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [0]*N

for i in A:
    ans[i-1] += 1

for k in ans:
    print(k)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

div_cache = {}
def primes(N):
    if N in div_cache:
        return div_cache[N]
    ret = set()
    for i in range(1, min(int(pow(N, 0.5) + 1), N)):
        if N % i == 0:
            ret.add(i)
            if i != 1:
                ret.add(N // i)
    div_cache[N] = ret
    return ret


cache = {}
def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    for i in range(1, K + 1):
        P = pow(K // i, N, M)
        ans += i * P

        affect = {}
        def past(p, sign):
            nonlocal ans
            prim = primes(p)
            for p in prim:
                affect.setdefault(p, 0)
                affect[p] += p * sign
                if p != 1:
                    for k, v in cache[p].items():
                        affect.setdefault(k, 0)
                        affect[k] -= v

        past(i, -1)
        cache[i] = affect
        for v in affect.values():
            ans += v * P
            ans %= M

        ans %= M
    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

def slowsolve(N, K):
    import itertools
    import math
    data = {}
    s = 0
    KK = [i for i in range(1, K + 1)]
    for p in itertools.product(KK, repeat=N):
        cdi = p[0]
        for c in p:
            cdi = math.gcd(cdi, c)
        s += cdi
        data.setdefault(cdi, 0)
        data[cdi] += 1
    print(data)
    return s


cache = {}
def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    for i in range(K, 0, -1):
        P = pow(K // i, N, M)
        j = i + i
        while j <= K:
            P -= cache[j]
            j += i
        while P < 0:
            P += M

        cache[i] = P
        ans += i * P
        ans %= M
    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))
### BUGGY CODE ###

def main():
  n, m = map(int, input().split())
  data = [[int(e) for e in input().split()] for _ in range(n)]
  d1 = {}
  for i in range(n):
    if data[i][0] in d1:
      d1[data[i][0]].append(data[i][1])
    else:
      d1[data[i][0]] = [data[i][1]]
  result = 0
  d2 = {}
  for i in range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j in d2:
          d2[j] += 1
        else:
          d2[j] = 1
    if len(d2.keys()) == 0:
      continue
    maxb = max(d2.keys())
    result += maxb
    if d2[maxb] == 1:
      del d2[maxb]
  print(result)
main()


### FIXED CODE ###

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
# import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):

    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N):
            a, b, c = B[i-1], B[i], B[(i+1) % N]
            if b > A[i] and b > a+c:
                d, m = divmod(b-A[i], a+c)
                count += d
                B[i] = A[i]+m
                flag = True
    # print(*A)
    # print(*B)
    if A != B:
        print(-1)
        return

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):

    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N):
            a, b, c = B[i-1], B[i], B[(i+1) % N]
            if b > A[i] and b > a+c:
                d, m = divmod(b-A[i], a+c)
                if m == 0:
                    B[i] = A[i]
                    count += d
                else:
                    d, m = divmod(b, a+c)
                    count += d
                    B[i] = m
                flag = True
    # print(*A)
    # print(*B)
    if A != B:
        count = -1

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


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

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)

### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

import math
K = int(input())
p = 0
for a in range(K):
  for b in range(K):
    for c in range(K):
      p += math.gcd(math.gcd(a+1, b+1),c+1)
print(p)


### FIXED CODE ###

import math
K = int(input())
p = int(K*(K+1)/2)
for a in range(K):
    for b in range(a+1, K):
        g = math.gcd(a+1, b+1)
        p += 6*g
        for c in range(b+1, K):
                p += 6*math.gcd(g, c+1)
print(p)
### BUGGY CODE ###

N,A,B = map(int, input().split())
ret = 0
for i in range(N):
  c = 0
  while i:
    c,mod = divmod(i,10)
    c += mod
  if A <= c and c <= B:
    ret += i
print(ret)

### FIXED CODE ###

N,A,B = map(int, input().split())
ret = 0
for i in range(N+1):
  s = sum([int(c) for c in str(i)])
  if A <= s and s <= B:
    ret += i
print(ret)
### BUGGY CODE ###

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

m = max(a)
r = -1

for i in range(m):
  t = i + 1
  if t in a:
    pass
  else:
    break

  idx = a.index(t)
  a = a[(idx+1):]
  r = t

if r < 0:
  print(r)
else:
  print(n - r)

### FIXED CODE ###

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

n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[] for i in [0]*n]
rail=[[] for i in [0]*n]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
for i in range(n):
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        for j in road[tmp]:
            if j not in road[i]:
                d.append(j)
                road[i].append(j)
for i in range(n):
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        for j in rail[tmp]:
            if j not in rail[i] and j!=i:
                d.append(j)
                rail[i].append(j)
ans=[]
for i,j in zip(road,rail):
    ans.append(str(len(set(i)&set(j))+1))
print(" ".join(ans))

### FIXED CODE ###

n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[{i} for i in range(n)]
rail=[{i} for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].add(q)
    road[q].add(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].add(s)
    rail[s].add(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].update(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].update(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[0]*n
for i in range(n):
    if ans[i]!=0:
        continue
    sumset=road[i]&rail[i]
    for j in sumset:
        ans[j]=str(len(sumset))
print(" ".join(ans))
### BUGGY CODE ###

a, b, k = map(int, input().split())

ans = []
for i in range(a, b+1):
    if i < a+k :
        if i not in ans:
            ans.append(i)
        
    elif b-k < i:
        if i not in ans:
            ans.append(i)
    
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

a, b, k = map(int, input().split())

ans = []
for i in range(a, a+k):
    if i not in ans and (a <= i and i <= b):
        ans.append(i)

for i in range(b-k+1, b+1):
    if i not in ans and (a <= i and i <= b):
        ans.append(i)
    
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7

pows = [1] * 66
for i in range(65):
    pows[i + 1] = (pows[i] * 2) % mod


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        tmp = a
        for i in range(65):
            if tmp == 0:
                break
            num[i] += tmp % 2
            tmp //= 2

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pows[i] * p(N, num[i])) % mod) % mod

    print(res % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    pows = [1] * 66
    for i in range(65):
        pows[i + 1] = (pows[i] * 2) % mod

    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        tmp = a
        for i in range(65):
            if tmp == 0:
                break
            num[i] += tmp % 2
            tmp //= 2

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pows[i] * p(N, num[i])) % mod) % mod

    print(res % mod)


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

N,K = map(int, input().split(' '))
A = [int(i) for i in input().split(' ')]

num = []
count = []
for a in range(len(A)):
    tmp = A[a]
    if not tmp in num:
        num.append(tmp)
        count.append(1)
    else:
        index = num.index(tmp)
        count[index] += 1

count = sorted(count)
ans = 0
if len(count)<=K:
    pass
else:
    tmp = len(count)-K
    count = count[:tmp]
    ans = sum(count)

print(ans)

### FIXED CODE ###

#辞書型でリトライ
N,K = map(int, input().split(' '))
A = input().split(' ')

dic = {}
for a in range(len(A)):
    tmp = A[a]
    if not tmp in dic:
        dic[tmp] = 1
    else:
        dic[tmp] += 1

values = sorted(dic.values())
ans = 0
if len(values)<=K:
    pass
else:
    tmp = len(values)-K
    values = values[:tmp]
    ans = sum(values)

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

def f(i,w,d):
  if i==n:
    return 0
  if (i,w) not in d:
    if a[i][0]>w:
      d[i,w]=f(i+1,w,d)
    else:
      d[i,w]=max(f(i+1,w,d),f(i+1,w-a[i][0],d)+a[i][1])
  return d[i,w]
n,w=map(int,raw_input().split())
a=[map(int,raw_input().split()) for _ in xrange(n)]
print f(0,w,{})

### FIXED CODE ###

n,w=map(int,raw_input().split())
a=[map(int,raw_input().split()) for _ in xrange(n)]
z=[[0]*(w+1)]
for i in xrange(n):
    z.append(z[-1][:])
    for j in xrange(w+1):
        if a[i][0]<=j:
            z[i+1][j]=max(z[i+1][j],z[i][j-a[i][0]]+a[i][1])
print max(z[-1])
### BUGGY CODE ###

# --------------------------------------
# 関数定義
# --------------------------------------


def chmin(a, b):
    if a > b:
        a = b
    return a

# --------------------------------------
# メイン処理
# --------------------------------------


def main():
    INF = 10 ** 10
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [INF] * N
    dp[0] = 0

    for i in range(1, N):
        for j in range(1, K + 1):
            if i - j < 0:
                continue
            dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

    print(dp[N-1])


# --------------------------------------
# 実行
# --------------------------------------
if __name__ == "__main__":
    main()


### FIXED CODE ###

# --------------------------------------
# 関数定義
# --------------------------------------


def chmin(a, b):
    if a > b:
        a = b
    return a

# --------------------------------------
# メイン処理
# --------------------------------------


def main():
    INF = 10 ** 10
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [INF] * N
    dp[0] = 0

    for i in range(1, N):
        for j in range(1, K + 1):
            if i - j < 0:
                continue
            dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

    print(dp[N-1])


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

import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

###########
Q=10**9+7
@memoize
def dp(n,i):
    if n<i:
        return 0
    elif n==1:
        return 1
    if i==0:
        return (dp(n-1,1)*2+dp(n-1,0))%Q
    else:
        return (dp(n-1,i-1)+dp(n-1,i+1)*2)%Q

n=i()
s=s()
print dp(n,len(s))
        
    


### FIXED CODE ###

mod=1000000007
n=int(raw_input())
l=len(raw_input())
dp=[[0 for i in range(n+2)] for j in range(n+1)]
for i in range(n+1):
    for j in range(i+1):
        if i==0:dp[i][j]=1
        elif j==0:dp[i][j]=(dp[i-1][1]*2+dp[i-1][0])%mod
        else:dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1]*2)%mod
print dp[n][l]
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)


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

ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]


class Tree():
    def __init__(self, v):
        self.parent = None
        self.v = v
        self.x = 0
        self.memo = None

    def add(self, x):
        self.x += x

    def calc(self):
        if self.v == 1:
            return self.x
        if self.memo is not None:
            return self.memo

        tmp = self.parent.calc()
        self.memo = tmp + self.x
        return self.memo



trees = {i: Tree(i) for i in range(1, N + 1)}

for a,b in ab:
    trees[b].parent = trees[a]

for p,x in px:
    trees[p].add(x)


print(" ".join(map(str,[trees[i].calc() for i in range(1,N+1)])))



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


input = raw_input
N, Q = list(map(int, input().split()))

ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]


class Tree():
    def __init__(self, v):
        self.parent = None
        self.v = v
        self.x = 0
        self.memo = None

    def add(self, x):
        self.x += x

    def calc(self):
        if self.v == 1:
            return self.x
        if self.memo is not None:
            return self.memo

        tmp = self.parent.calc()
        self.memo = tmp + self.x
        return self.memo



trees = {i: Tree(i) for i in range(1, N + 1)}

for a,b in ab:
    trees[b].parent = trees[a]

for p,x in px:
    trees[p].add(x)


print(" ".join(map(str,[trees[i].calc() for i in range(1,N+1)])))
### BUGGY CODE ###

import bisect
N,M,Q = map(int,input().split())
lr = [0]*M
for i in range(M):
    l,r = map(int,input().split())
    lr[i] = [l,r]
lr = sorted(lr,key=lambda x:x[0])
lr_t = list(map(list, zip(*lr)))
index_dict={}
r_dict={}
d = {}
for i in range(N):
    index_dict[i+1]=bisect.bisect_left(lr_t[0],i+1)
    r_dict[i+1]=sorted(lr_t[1][index_dict[i+1]:])
for i in range(Q):
    p,q = map(int,input().split())
    if p not in d:
        d[p]={}
        I = index_dict[p]
        r = r_dict[p]
        I = bisect.bisect(r,q)
        print(I)
        d[p][q]=I
    else:
        if q not in d[p]:
            I = index_dict[p]
            r = r_dict[p]
            I = bisect.bisect(r,q)
            print(I)
            d[p][q]=I
        else:
            print(d[p][q])

### FIXED CODE ###

import numpy as np
N,M,Q = map(int,input().split())
c = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    c[l][r] += 1
c = np.cumsum(np.cumsum(c,axis=0),axis=1)
for i in range(Q):
    p,q = map(int,input().split())
    print(c[q][q]-c[q][p-1]-c[p-1][q]+c[p-1][p-1])