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

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n = ni()
t = [0] + list(li())
v = [0] + list(li()) + [0]

t_acc = list(accumulate(t))
t_max = t_acc[-1]
t_cur = [10**10]*(2*t_max+1)

interval = dict({(0,0): 0, (t_max,t_max): 0})
for i in range(n):
    interval.update({(t_acc[i], t_acc[i+1]): v[i+1]})
    
for t_idx in range(2*t_max+1):
    for i, ((tl,tr), v) in enumerate(interval.items()):
        
        if t_idx*0.5 < tl:
            t_cur[t_idx] = min(t_cur[t_idx], abs(v+(tl-t_idx*0.5)))
            
        elif tl <= t_idx*0.5 <= tr:
            t_cur[t_idx] = min(t_cur[t_idx], v)
            
        elif tr < t_idx*0.5:
            t_cur[t_idx] = min(t_cur[t_idx], abs(v+(t_idx*0.5-tr)))

ans = 0
for i in range(len(t_cur)-1):
    ans += (1/4)*(t_cur[i] + t_cur[i+1])

print(ans)

### FIXED CODE ###

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

V = [0] + V + [0]

# 0.前処理
# N+2個の条件をつくる
left = [0]
right = [0]

for i in range(N):
    left.append(right[i])
    right.append(left[-1]+T[i])
    
left.append(right[-1])
right.append(right[-1])

INF = float("inf")
vel = [INF]*(2*right[-1]+1)

# 1.各ステップでの許容測度の最大値の最小値を求める
for t in range(2*right[-1]+1):
    for i in range(N+2):
        if (t/2) < left[i]:
            vel[t] = min(vel[t], -(t/2)+(V[i]+left[i]))
        elif left[i] <= (t/2) and (t/2) <= right[i]:
            vel[t] = min(vel[t], V[i])
        elif (t/2) > right[i]:
            vel[t] = min(vel[t], (t/2)+(V[i]-right[i]))
            

# 2.面積を求める
ans = 0
for t in range(2*right[-1]):
    ans += (1/2)*0.5*(vel[t]+vel[t+1])
    
print(ans)
### BUGGY CODE ###

import bisect as bi
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [0] * m
for i in range(m):
    b[i] = list(map(int,input().split()))
a.sort()

for i in b:
    tmp = bi.bisect_left(a,i[1])
    for j in range(min(tmp,i[0])):
        a[j] = i[1]
    a.sort()

print(sum(a))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter

N,M = map(int,readline().split())
A = list(map(int,readline().split()))
m = map(int,read().split())
BC = list(zip(m,m))

BC.sort(key = itemgetter(1),reverse=True)

BC.append((N,-1))

change = []
for b,c in BC:
    change += [c] * b
    if len(change) > N:
        break

A += change
A.sort()
answer = sum(A[-N:])
print(answer)
### BUGGY CODE ###

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

X.sort()
diff=[]
for i in range(M-1):
    diff.append(X[i+1]-X[i])
gap=[]
for i in range(N-1):
    for j in range(M-1):
        x=diff.index(max(diff))
        gap.append(x)
        diff[x]=0
        break
gap.append(M-1)
gap=list(set(gap))
gap.sort()
offset=0
cnt=0
for i in gap:
    cnt+=X[i]-X[offset]
    offset=i+1
print(cnt)

### FIXED CODE ###

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

X.sort()
diff=[]
for i in range(M-1):
    diff.append(X[i+1]-X[i])
diff.sort()
to=M-N
if to<=0:
    ans=0
else:
    ans=sum(diff[:to])
print(ans)
### BUGGY CODE ###

N, Y = map(int, input().split())
a, b, c = -1, -1, -1

if Y >= 2000 * 10000:
    ZN = 1
    YN = 1
    XN = 2000
else:
    ZN = min(N, Y//1000)
    YN = min(N, Y//5000)
    XN = min(N, Y//10000)
    
for z in range(ZN + 1):
    for y in range(YN + 1):
        for x in range(XN + 1):
            if x + y + z == N and 1000*z + 5000*y + 10000*x == Y:
                a, b, c = x, y, z
                break

print(a, b, c)


### FIXED CODE ###

N, Y = map(int, input().split())
ans = []
for x in range(N+1):
    for y in range(N+1):
        z = N - x - y
        if (x * 10000) + (y * 5000) + (z * 1000) == Y and x + y + z == N and z >= 0:
            ans.append([x, y, z])

if len(ans) == 0:
    print(-1, -1, -1)
else:
    print(ans[0][0], ans[0][1],ans[0][2])
### BUGGY CODE ###

import collections
def main():
    n = int(input())
    a = list(map(int,input().split()))
    cnt = collections.Counter(a)
    cnt_m = cnt.most_common()
    if cnt.most_common()[0][1] == 1:
        for i in range(n):
            print(0)

        return

    for i, aa in enumerate(a):
        ans = 0
        for j in range(len(cnt)):
            cnt_a = cnt_m[j][0]
            cnt_num = cnt_m[j][1]
            if cnt_num == 1:
                break
            else:
                if cnt_a == aa:
                    cnt_num -= 1
                ans += cnt_num * (cnt_num - 1)
        print(ans//2)


if __name__=='__main__':
    main()


### FIXED CODE ###

import collections
def main():
    n = int(input())
    a = list(map(int,input().split()))
    cnt_ary = [0] * n

    for i,aa in enumerate(a):
        cnt_ary[aa-1] += 1


    tmp = 0
    ans_ary = [0] * n
    for i, cc in enumerate(cnt_ary):
        ans_ary[i] = cc * (cc-1)

    t = sum(ans_ary)
    ans = 0
    for i, aa in enumerate(a):
        ans = 0
        ans = t - ans_ary[aa-1]
        ans += (cnt_ary[aa-1] - 1) * (cnt_ary[aa-1] - 2)
        print(ans//2)



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

import sys
def main():
    N = int(input())
    A_list = [int(_) for _ in input().split()]
    ans = 1
    for i in range(N):
        ans *= A_list[i]

    out = ans
    if ans>10**18:
        out = -1
    print(out)
main()

### FIXED CODE ###

import sys
def main():
    N = int(input())
    A_list = [int(_) for _ in input().split()]
    ans = 1
    
    if 0 in A_list:
        out = 0
        print(out)
        sys.exit()
    
    for i in range(N):
        ans = ans * A_list[i]
        
        if ans>1000000000000000000:
            ans = -1
            break
    out = ans
    print(out)

main()
### BUGGY CODE ###

n,w=map(int,input().split())
d,f=map(int,input().split())
if n==1:print(f if d<=w else 0);exit()
dp=[[0,0],[d,f]]#w,v
dp_=[]
for i in range(1,n):
  d,f=map(int,input().split())
  if dp_==[]:
    for x,c in dp:
      if x+d<=w:dp_.append([x+d,c+f])
    dp_+=dp
    dp=[]
  else:
    for x,c in dp_:
      if x+d<=w:dp.append([x+d,c+f])
    dp+=dp_
    dp_=[]
print(max(sum(dp+dp_,[])[1::2]))

### FIXED CODE ###

n,w=map(int,input().split())
dp=[0]*(w+1)
for i in range(n):
    wi,vi=map(int,input().split())
    for j in range(w-wi,-1,-1):
        dp[j+wi]=max(dp[j+wi],dp[j]+vi)
print(dp[-1])
### BUGGY CODE ###

import math

def func(h, a, b, count):
  ans = 0
  for v in h:
    if v > b * count:
      ans += math.ceil((v-b*count) / (a-b))
      
  return ans <= count

n,a,b = map(int, input().split())
h = []

for i in range(n):
  # heapqを最大値を取り出すように使いたいのでマイナスにする
  h.append(int(input()))

delta = a-b
start = 1
end = math.ceil(max(h) / b)
middle = (end + start) // 2

# 二分探索する、終了条件はぶっちゃけわからん
while True:
  if(func(h,a,b,middle)):
    end = middle
  else:
    start = middle
    
  middle = (end + start) // 2
  if (end - start) == 1:
    break
    
print(end)

### FIXED CODE ###

import math

def func(h, a, b, count):
  ans = 0
  for v in h:
    if v > b * count:
      ans += math.ceil((v-b*count) / (a-b))
      
  return ans <= count

n,a,b = map(int, input().split())
h = []

for i in range(n):
  # heapqを最大値を取り出すように使いたいのでマイナスにする
  h.append(int(input()))

start = 1
end = math.ceil(max(h) / b)
middle = (end + start) // 2

# 二分探索する、終了条件はぶっちゃけわからん
for i in range(1000):
  if(func(h,a,b,middle)):
    end = middle
  else:
    start = middle
    
  middle = (end + start) // 2
  if (end - start) == 1:
    break
    
print(end)
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 仕方ないので，numpy で同時代入
import numpy as np
import sys
H, W = list(map(int, input().split()))
all_in = sys.stdin.readlines()
all_count = H * W
blacks = [i*W+j for i in range(H) for j in range(W) if all_in[i][j] == "#"]
L = np.asarray([False]*all_count)
L[blacks] = True
black_count = len(blacks)

cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
  next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
  blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
  L[blacks] = True
  black_count += len(blacks)
  #print(blacks)
  result += 1

print(result)

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

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

import numpy as np
N = int(input())
A_list = list(map(int, input().split()))
index = np.arange(1, N+1)
for i in index:
  print(A_list.count(i))

### FIXED CODE ###

import collections
N = int(input())
A_list = list(map(int, input().split()))
ans = collections.Counter(A_list)
for i in range(1, N+1):
	print(ans[i])
### BUGGY CODE ###

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

A.sort()

def f(n): #aiが必要か不必要か判定
    if A[n] >= K:
        return True
    if n == 0:
        L = A[n+1:]
    elif n == N-1:
        L = A[:n]
    else:
        L = A[:n] + A[n+1:]
    
    dp = [[False]*K for _ in range(N)]
    for i in range(N):
        dp[i][0] = True
    for i in range(N-1):
        for j in range(K):
            if j < L[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = dp[i][j] | dp[i][j-L[i]]
                
    res = False
    for j in range(K-A[n], K):
        if dp[-1][j]:
            res = True
            break
            
    return res

l = -1
r = N
while r-l > 1:
    m = (l+r)//2
    if f(m):
        r = m
    else:
        l = m
        
print(r)

### FIXED CODE ###

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

A.sort()
for i in range(N):
    if A[i] >= K:
        A = A[:i]
        break

N = len(A)

def f(n): #aiが必要か不必要か判定
    dp = [0]*K
    dp[0] = 1
    for i in range(N):
        if i == n:
            continue
        for j in range(K-1, A[i]-1, -1):
            dp[j] |= dp[j-A[i]]
            
    res = False
    for j in range(K-A[n], K):
        if dp[j]:
            res = True
            break
    return res

l = -1
r = N
while r-l > 1:
    m = (l+r)//2
    if f(m):
        r = m
    else:
        l = m
        
print(r)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int

def solve(S: str):
    n = len(S)
    b_total = 0
    b_counts = []
    for c in S:
        b_total += ord(c) - ord('0')
        b_counts.append(b_total)
    dp = [[0] * (b_total + 1) for _ in range(2 * n + 1)]
    dp[0][0] = 1
    for i in range(2 * n):
        for j in range(min(i + 1, b_total + 1)):
            b_max = b_counts[i] if i < n else b_total
            r_max = (i + 1) * 2 - b_max if i < n else 2 * n - b_total
            if b_max >= j + 1:
                dp[i + 1][j + 1] += dp[i][j]
            if r_max >= (i + 1) - j:
                dp[i + 1][j] += dp[i][j]
    ret = sum(dp[2 * n])
    print(ret % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int

def comb(n, k):
    if k > n:
        return 0
    k = min(k, n - k)
    ret = 1
    for i in range(k):
        ret *= n - i
        ret //= i + 1
    return ret

def solve(S: str):
    n = len(S)
    b_total = 0
    b_counts = []
    for c in S:
        b_total += ord(c) - ord('0')
        b_counts.append(b_total)
    dp = [[0] * (b_total + 1) for _ in range(2 * n + 1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(min(i + 1, b_total + 1)):
            if b_counts[i] >= j + 1:
                dp[i + 1][j + 1] += dp[i][j]
            if (i + 1) * 2 - b_counts[i] >= (i + 1) - j:
                dp[i + 1][j] += dp[i][j]
    #    print(dp[i])
    #print(dp[n])
    comb = [0] * (n + 1)
    comb[0] = 1
    for i in range(n):
        comb[i + 1] = comb[i] * (n - i) // (i + 1)
    ret = 0
    for b, val in enumerate(dp[n]):
        #ret += val * comb(n, b_total - b)
        if b_total - b >= 0 and b_total - b <= n:
            ret += val * comb[b_total - b]
    print(ret % MOD)
    return

    ##dp[0][0] = 1
    ##for i in range(2 * n):
    ##    for j in range(min(i + 1, b_total + 1)):
    ##        b_max = b_counts[i] if i < n else b_total
    ##        r_max = (i + 1) * 2 - b_max if i < n else 2 * n - b_total
    ##        if b_max >= j + 1:
    ##            dp[i + 1][j + 1] += dp[i][j]
    ##        if r_max >= (i + 1) - j:
    ##            dp[i + 1][j] += dp[i][j]
    ##ret = sum(dp[2 * n])
    ##print(ret % MOD)
    ##return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))
    solve(S)

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n,q=map(int,input().split())
tree = [set() for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    tree[a-1].add(b)
ans=[0]*n
def add_l(x):
    if not tree[x-1]:
        return
    for i in list(tree[x-1]):
        add_l(i)
        tree[x-1] |= tree[i-1]

add_l(1)
#print(tree)

for i in range(q):
    
    p,x=map(int,input().split())
    ans[p-1]+=x
    if tree[p-1]:

        for j in list(tree[p-1]):
            ans[j-1]+=x
print(*ans)


### FIXED CODE ###

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

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l2=sorted(l)
box=[0] #各長さの棒が何本あるか　最初の０は数合わせ
ans=0

num=1
while num<l2[0]: #最小の棒までは０をappend
    box.append(0)
    num+=1
    
now=l2[0]
bounum=1
for i in range(1,n):
    if l2[i]!=now:
        box.append(bounum)
        while now+1<l2[i]:
            box.append(0)
        now=l2[i]
        bounum+=1
    else:
        bounum+=1
if len(box)!=l2[-1]+1:
    box.append(bounum) #boxの完成

for i in range(n-2):
    for j in range(i+1,n-1):
        c=l2[i]+l2[j]-1
        if c>l2[-1]:
            c=l2[-1]
        add=box[c]-(j+1)
        if add<0:
            add=0
        ans+=add

print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l2=sorted(l)
box=[0] #各長さの棒が何本あるか　最初の０は数合わせ
ans=0

num=1
while num<l2[0]: #最小の棒までは０をappend
    box.append(0)
    num+=1
    
now=l2[0]
bounum=1
for i in range(1,n):
    if l2[i]!=now:
        box.append(bounum)
        next=now+1
        while next<l2[i]:
            box.append(bounum)
            next+=1 
        now=l2[i]
        bounum+=1
    else:
        bounum+=1
if len(box)!=l2[-1]+1:
    box.append(bounum) #boxの完成

for i in range(n-2):
    for j in range(i+1,n-1):
        c=l2[i]+l2[j]-1
        if c>l2[-1]:
            c=l2[-1]
        add=box[c]-(j+1)
        if add<0:
            add=0
        ans+=add

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

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = {}
for _ in range(M):
    B, C = list(map(int, input().split()))
    if C in BC:
        BC[C] += B
    else:
        BC[C] = B

CB = sorted(BC.items(), key=lambda x: x[0], reverse=True)
A.sort()
s = 0
for C, B in CB:
    mn = A[0]
    if mn >= C:
        s += sum(A)
        break
    n = len(A)
    if B > n:
        B = n
    if A[B - 1] <= C:
        s += B * C
        if B == n:
            break
        A = A[B:]
    else:
        a, b = 0, B
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        s += b * C
        s += sum(A[b:])
        break
else:
    s += sum(A)
print(s)

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
l, r = 0, N
for B, C in BC:
    if A[l] >= C:
        break
    a, b = l, r
    if A[r - 1] >= C:
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        r = b
    n = B + l
    if n > r:
        n = r
        B = n - l
    if n <= b:
        A[l:n] = [C] * B
        l = n
    else:
        A[l:b] = [C] * B
        l = b
    if l == r:
        break

print(sum(A))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
  ans=ans*i
print(ans if ans<=10**18 else -1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
count=a.count(0)
if count>0:
  print(0)
  quit()
else:
  for i in a:
    ans=ans*i
    if ans>10**18:
      print(-1)
      quit()
print(ans)
### BUGGY CODE ###

from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.linalg import spsolve
import numpy as np

N = int(input())
A = np.array(input().split(), dtype=int)

mat = lil_matrix((N, N))
for i in range(N):
    j = (i + 1) % N
    mat[i, i] = 1
    mat[i, j] = 1
mat = csr_matrix(mat)

ans = spsolve(mat, A) * 2
ans = list(map(int, ans))
print(*ans)


### FIXED CODE ###

from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=deque([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for loop in range(n):
    if loop==0:
        t=sum([i*j for i,j in zip(a,c)])
    else:
        t=2*a[loop-1]-t
    ans.append(str(t))


print(" ".join(ans))
### BUGGY CODE ###

a, b, c, d = map(int, input().split())

num = b - a + 1
c_num = b // c - (a - 1) // c
d_num = b // d - (a - 1) // d

cd_max = max(c, d)
cd_min = min(c, d)
i = 1
while True:
    if (cd_max * i) % cd_min == 0:
        cd = cd_max * i
        break
    i += 1
    
cd_num = b // cd - (a - 1) // cd

#print(num, c_num, d_num, cd_num)

print(num - (c_num + d_num - cd_num))


### FIXED CODE ###

a, b, c, d = map(int, input().split())

big = max(c, d)
small = min(c, d)
lcm = 0
for i in range(1, 10 ** 8):
    surplus = big % small
    if surplus == 0:
        lcm = c * d // small
        break
    
    big = small
    small = surplus
    

c_num = b // c - (a - 1) // c
d_num = b // d - (a - 1) // d
cd_num = b // lcm - (a - 1) // lcm
num = b - a + 1

#print(num, c_num, d_num, cd_num, lcm)
ans = num - (c_num + d_num - cd_num)

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

# -*- coding: utf-8 -*-
import math
num,product = map(int,input().split())
order = len(str(product)) / num

cnt = round(10 ** order)
gcd = 1
while(cnt > 1):
    calc = cnt ** num
    if product % calc == 0:
        gcd = cnt
        break
    else:
        cnt = cnt - 1
print(gcd)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
from math import sqrt,floor
num,product = map(int,input().split())
cnt = int(sqrt(product) + 2)
dd = defaultdict(int)

for i in range(2,cnt):
    if product % i == 0:
        a = 0
        while product % i == 0:
            a += 1
            product = product // i
        dd[i] = a
if product != 1:
    dd[product] =  1
ans = 1
for p,n in dd.items():
    ans *= pow(p,floor(n/num))
print(ans)
### BUGGY CODE ###

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

a = [[0 for i in range(509)] for j in range(509)]
sum = [[0 for i in range(509)] for j in range(509)]

for i in range(M):
  p, q = map(int, input().split())
  a[p][q] += 1

for i in range(1,N+1):
  for j in range(i,N+1):
    sum[i][j] = sum[i][j-1] + a[i][j]

for i in range(Q):
  p, q = map(int, input().split())
  ans = 0
  for j in range(p,q+1):
    ans += sum[j][q] - sum[j][p-1]
  print(ans)


### FIXED CODE ###

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

a = [[0 for i in range(509)] for j in range(509)]
sum = [[0 for i in range(509)] for j in range(509)]
ans = [[0 for i in range(509)] for j in range(509)]

for i in range(M):
  p, q = map(int, input().split())
  a[p][q] += 1

for i in range(1,N+1):
  for j in range(i,N+1):
    sum[i][j] = sum[i][j-1] + a[i][j]

for i in range(1,N+1):
  for j in range(i,N+1):
    for k in range(i,j+1):
      ans[i][j] += sum[k][j] - sum[k][i-1]

for i in range(Q):
  p, q = map(int, input().split())
  #ans = 0
  #for j in range(p,q+1):
  #  ans += sum[j][q] - sum[j][p-1]
  print(ans[p][q])
### BUGGY CODE ###

import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

s = []
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        c_min = b - a
        c_max = a + b
        if c_max > c_min + 1:
            s.append((c_min, c_max, j + 1))

ans = 0
for x, y, j in s:
    i_min = bisect.bisect_right(L[j:], x)
    i_max = bisect.bisect_left(L[j:], y)
    ans += i_max - i_min
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        k = bisect.bisect_left(L, L[i]+L[j])
        ans += k-1 - j
print(ans)
### BUGGY CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,m=map(int,input().split())
a = [-1]+[int(input()) for _ in range(m)]+[n+1]

def comb(dann):
    num_comb = 0
    for i in range((dann//2)+1):
        num_comb += combinations_count(dann-i, i)
    return num_comb

danns = [(a[i+1] - a[i]) - 2 for i in range(len(a)-1)]

ans = 1
for j in danns:
    ans *= comb(j) % 1000000007
print(ans%1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
inf = float("inf")
dp = [0] * (N+1)
for i in A:
	dp[i] = inf
dp[0] = 1
if dp[1] != inf:
	dp[1] = 1
for i in range(2,N+1):
	if dp[i] == inf:
		continue

	a = dp[i-2] if dp[i-2] != inf else 0
	b = dp[i-1] if dp[i-1] != inf else 0

	dp[i] = (a + b) % 1000000007


print(dp[N])