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

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

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

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  if t>10**6:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          nlist.append(vv)          
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  vlist = nlist
  


### FIXED CODE ###

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

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

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  #if t>300003:
  #  print(-1)
  #  sys.exit()
  
  #nlist = []
  nset = set()
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          #nlist.append(vv)
          nset.add(vv)
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  #vlist = nlist
  vlist = list(nset)
  if len(vlist) == 0:
    print(-1)
    break
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

BASE, MOD = 1999849216943526259, (1<<61)-1

d = dict()
ans = 0
ss = [input()[::-1] for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	if n == 1:
		ans += zero[ord(s[n-1])-97]
	else:
		hashes = [0 for _ in range(n-1)]
		hashes[0] = ord(s[0])
		for i in range(1, n-1):
			hashes[i] = (hashes[i-1] * BASE + ord(s[i])) % MOD
		if hashes[n-2] in d:
			ans += d[hashes[n-2]][ord(s[n-1])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[n-1])-97] = 1
		for i in range(n-2, 0, -1):
			alph[ord(s[i])-97] = 1
			if hashes[i-1] not in d:
				d[hashes[i-1]] = [0 for _ in range(26)]
			for j, a in enumerate(alph):
				d[hashes[i-1]][j] += a
		alph[ord(s[0])-97] = 1
		for j, a in enumerate(alph):
			zero[j] += a
print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

BASE, MOD = 1999849216943526259, (1<<61)-1

d = dict()
ans = 0
ss = [str(input())[2:-1][::-1] for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	if n == 1:
		ans += zero[ord(s[n-1])-97]
	else:
		hashes = [0 for _ in range(n-1)]
		hashes[0] = ord(s[0])
		for i in range(1, n-1):
			hashes[i] = (hashes[i-1] * BASE + ord(s[i])) % MOD
		if hashes[n-2] in d:
			ans += d[hashes[n-2]][ord(s[n-1])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[n-1])-97] = 1
		for i in range(n-2, 0, -1):
			alph[ord(s[i])-97] = 1
			if hashes[i-1] not in d:
				d[hashes[i-1]] = [0 for _ in range(26)]
			for j, a in enumerate(alph):
				d[hashes[i-1]][j] += a
		alph[ord(s[0])-97] = 1
		for j, a in enumerate(alph):
			zero[j] += a
print(ans)
### BUGGY CODE ###

import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_left # bisect_left(list, value)
#from fractions import gcd
from operator import mul
from functools import reduce

sys.setrecursionlimit(10**7)
n, a, b = map(int, input().split())
div = 10**9+7

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x**2%div, n//2)
    else:
        return x * pow_r(x**2%div, (n-1)//2)

num = pow_r(2, n)
num %= div

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, n+2):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

num -= cmb(n, a, mod)
num -= cmb(n, b, mod)
num %= div

print(num-1)



### FIXED CODE ###

import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_left # bisect_left(list, value)
#from fractions import gcd
enu = enumerate

sys.setrecursionlimit(10**7)
n, a, b = map(int, input().split())
mod = 10**9 + 7

def cmb(n, r, p):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = 1
    for i in range(n, n - r, -1):
        over = over * i % p
    under = 1
    for i in range(1, r + 1):
        under = under * i % p
    inv = pow(under, p - 2, p)
    return over * inv % p

cnt = pow(2, n, mod)
ng1 = cmb(n, a, mod)
ng2 = cmb(n, b, mod)

res = (cnt - ng1 - ng2 - 1) % mod

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

def main():
    s=input()
    n= len(s)
    dp = [[0 for _ in range(13)]for _ in range(n)]

    ss = s[0]
    if ss == '?':
        for i in range(10):
            dp[0][i] = 1
    else:
        ss = int(ss)
        dp[0][ss] = 1

    for i in range(1,n):
        ss = s[i]
        if ss == "?":
            for k in range(10):
                for j in range(13):
                    t = (j * 10 +k) % 13
                    dp[i][t] += dp[i-1][j]
        else:
            ss = int(ss)
            for j in range(13):
                t = (j * 10 +ss) % 13
                dp[i][t] += dp[i-1][j]

    print(dp[n-1][5] % (10**9+7))

main()

### FIXED CODE ###

def main():
    sts=input()
    n= len(sts)
    mod = 10**9+7
    s = []
    for c in sts:
        s.append(c)

    dp = [[0 for _ in range(13)]for _ in range(n)]

    ss = s[0]
    if ss == '?':
        for i in range(10):
            dp[0][i] = 1
    else:
        ss = int(ss)
        dp[0][ss] = 1

    for i in range(1,n):
        ss = s[i]
        if ss == "?":
            for k in range(10):
                for j in range(13):
                    dp[i][(j * 10 +k) % 13] += dp[i-1][j]
        else:
            for j in range(13):
                dp[i][(j * 10 +int(ss)) % 13] += dp[i-1][j]
        for j in range(13):
            dp[i][j]%= mod


    print(dp[n-1][5])

main()
### BUGGY CODE ###

from sys import stdin

readline = stdin.readline


def nf():
    """
    入力全て(EOFまで)を`int iter`に変換
    """
    return map(int, open(0).read().split())


def main():
    n, *l = nf()
    al = list(l)
    for i in range(n):
        ma = 0
        if i > 0:
            ma = max(al[:i])
        if i < n-1:
            ma = max(max(al[i+1:]), ma)
        print(ma)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin

readline = stdin.readline


def nf():
    """
    入力全て(EOFまで)を`int iter`に変換
    """
    return map(int, open(0).read().split())


def main():
    n, *al = nf()
    s, f = sorted(al)[-2:]
    if s == f:
        for _ in range(n):
            print(f)
        return
    for a in al:
        if a == f:
            print(s)
            continue
        print(f)


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

import bisect

n, m = map(int, input().split())

nums = list(map(int, input().split()))

nums.sort()
for i in range(m):
    b, c = map(int, input().split())
    
    index = bisect.bisect_left(nums, c)
    if index > 0:
        temp = nums[0:index]
        temp.extend([c]*b)
        temp.extend(nums[index:])
        nums = temp[-n:]
        
print(sum(nums))

### FIXED CODE ###

n, m = map(int, input().split())

nums = list(map(int, input().split()))

ops = []
for i in nums:
    ops.append([1, i])
    
for i in range(m):
    b, c = map(int, input().split())
    ops.append([b, c])

total = 0
sums = []
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if total > n:
        break
    sums.extend([c]*b)
    total = total + b
print(sum(sums[:n]))
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
final=[0]*n
if k>=n:
  print(abs(l[n-1]-l[0]))
else:   
   for i in range(1,k+1):
      final[i]=abs(l[i]-l[0])
  
   for i in range(k+1,n):

      mini=10**9+1



  
      x=k
      for j in range(1,x+1):

           mini=min(mini,final[i-j]+abs(l[i]-l[i-j]))
      final[i]=mini
   print(final[-1])


### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
final=[0]*n
if k>=n:
  print(abs(l[n-1]-l[0]))
else:   
   for i in range(1,k+1):
      final[i]=abs(l[i]-l[0])
  
   for i in range(k+1,n):

      li=[abs(l[i]-l[ik])+final[ik] for ik in range(i-1,i-k-1,-1) ]
      final[i]=min(li)
   print(final[-1])
### BUGGY CODE ###

from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0] * (n+1)

q = []

def bfs(x):
	q.append(x)
	while(len(q) != 0):
		now = q.pop(0)
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				#reached.remove(k)
				q.append(k)

for i in range(m):
	a,b = map(int, input().split())
	g[a].append(b)
	g[b].append(a)

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(True):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")

### FIXED CODE ###

from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
reached = list(range(1,n+1))
misi = [0] * (n+1)

#q = []

def bfs(x):
	q = deque()
	q.append(x)
	while(len(q) != 0):
		now = q.popleft()
#		print(now)
		for k in g[now]:
			if(misi[k] == 0):
#				print(now,"->",k)
				misi[k] = now
				#reached.remove(k)
				q.append(k)

for i in range(m):
	a,b = map(int, input().split())
	g[a].append(b)
	g[b].append(a)

misi[1] = 1
reached.remove(1)
bfs(1)

#print("---")
#print(reached)
if(True):
	print("Yes")
	for i in range(2,n+1):
		#print(i,":misi",misi[i])
		print(misi[i])
else:
	print("no")
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int, input().split()))
 
A = 0
for i in range(N-K+1):
  B = 0
  for j in range(K):
    B += (1 + P[i+j])/2
    if B > A:
      A = B
 
print(A)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
E = [(1+i)/2 for i in p]
S = [0]*(N+1)
sum = 0
for i in range(N):
  sum += E[i]
  S[i+1] = sum
ans = 0
i = 0
while N-K-i >= 0:
  A = S[K+i] -S[i]
  ans = max(ans,A)
  i += 1
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

s = input()
n = len(s)
dp = [1] + [0]*2019
now = 0
i = 1

for c in reversed(s):
    now = (now+i*int(c))%2019
    dp[now] += 1
    i *= 10
    i %= 2019

ans = sum([i*(i-1)/2 for i in dp])
print(int(ans))
### BUGGY CODE ###

N,Q=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x

que=[0]
done=[-1]*N
while len(que)>0:
    t=que.pop(0)
    now=t
    done[now]=1
    for nex in G[now]:
        if done[nex]!=-1:
            continue
        else:
            X[nex]+=X[now]
            que.append(nex)

print(*X)

### FIXED CODE ###

from collections import deque 
N,Q=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x
que=deque([(0,-1)])
#print(que)
while que:
    now, pre=que.pop()
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

print(" ".join(map(str, X)))
### BUGGY CODE ###

import math

a, b = map(int, input().split())
fa = []
fb = []

tmp = a//2 + 1
for i in range(2,tmp):
    while a % i == 0:
        a //= i
        fa.append(i)
fa.append(a)

tmp = b//2 + 1
for i in range(2,tmp):
    while b % i == 0:
        b //= i
        fb.append(i)
fb.append(b)

print(len(list(set(fa) & set(fb))))

### FIXED CODE ###

import math

a, b = map(int, input().split())
fa = []
fb = []

tmp = int(math.sqrt(a)) + 1
for i in range(2,tmp):
    while a % i == 0:
        a //= i
        fa.append(i)
if a != 1:
    fa.append(a)

tmp = int(math.sqrt(b)) + 1
for i in range(2,tmp):
    while b % i == 0:
        b //= i
        fb.append(i)
if b != 1:
    fb.append(b)

print(len(list(set(fa) & set(fb))) + 1)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
items = []
ap = items.append
a_sum =0
b_sum = 0
for i in range(N):
    a, b, c = map(int, input().split())
    ap((a, b, c))
    a_sum += a
    b_sum += b

inf = float("inf")
dp = [[[inf for _ in range(b_sum + 10)] for _ in range(a_sum + 10)] for i in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
    for a in range(a_sum):
        for b in range(b_sum):
            if dp[i + 1][a][b] > dp[i][a][b]:
                dp[i + 1][a][b] = dp[i][a][b]
            if dp[i + 1][a + items[i][0]][b + items[i][1]] > dp[i][a][b] + items[i][2]:
                dp[i + 1][a + items[i][0]][b + items[i][1]] = dp[i][a][b] + items[i][2]

ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 100)] for _ in range(b_sum + 100)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
results = []
if m:
    results = [input().split() for _ in range(m)]
ac = []
wa = {}
cnt_ac = 0
cnt_wa = 0
for res in results:
    if res[1] == "AC" and not res[0] in ac:
        cnt_ac += 1
        ac.append(res[0])
        if res[0] in wa.keys():
            cnt_wa += wa[res[0]]
    else:
        if res[0] in wa.keys():
            wa[res[0]] += 1
        else:
            wa[res[0]] = 1
print(cnt_ac, cnt_wa)

### FIXED CODE ###

N,M=map(int,input().split())
AC=[0]*N
WA=[0]*N
wa=0
for i in range(M):
  p,s=input().split()
  p=int(p)-1
  if AC[p]==0 and s=="AC":
  	AC[p]=1
  	wa+=WA[p]
  WA[p]+=1
print(sum(AC),wa)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
s1 = s
list = [0]*q

start = []
end = []
c = s.count("AC")

for i in range(q):
    s1, e1 = [int(i) for i in input().split()]
    start.append(s1-1)
    end.append((e1-1))

for i in range(c):
    list[i] = s.find("AC")
    s = s.replace("AC", "XX", 1)

result = [0]*q

for i in range(q):
    for j in range(c):
        #print(str(start[i]) + " : " + str(end[i]))
        if start[i] <= list[j] < end[i]:
            result[i] += 1


for i in result:
    print(i)



### FIXED CODE ###

n, q = map(int, input().split())
s = input()
x = [0]*(n+1)

for i in range(n):
    x[i+1] = x[i] + (1 if s[i:i+2] == "AC" else 0)

for i in range(q):
    l, r = map(int, input().split())
    print(x[r-1] - x[l-1])
### BUGGY CODE ###

S=int(input())
cond=0

if S<=10**9:
 print(0,0,1,0,0,S)
else:
 for x2 in reversed(range(1,10**9+1)):
   if int(S/x2)>0 and int(S/x2)+1 <=10**9:
      print(0,0,x2,1,x2-S%x2,int(S/x2)+1)
      break



### FIXED CODE ###

S=int(input())
cond=0

if S<=10**9:
 print(0,0,1,0,0,S)
elif S==10**18:
 print(0,0,10**9,0,0,10**9)
else:
 for x2 in reversed(range(1,10**9+1)):
   if int(S/x2)+1 <=10**9:
      print(0,0,x2,1,x2-S%x2,int(S/x2)+1)
      break
### BUGGY CODE ###

from math import gcd
k = int(input())+1
ans = 0
for i in range(1,k):
  for j in range(1,k):
    for l in range(1,k):
      if 1 in [i,j,k]:
          ans+=1
      else:
          ans += gcd(gcd(i,j),l)
print(ans)


### FIXED CODE ###

from math import gcd
k = int(input())+1
ans = 0
for i in range(1,k):
  for j in range(1,k):
    for l in range(1,k):
      ans += gcd(gcd(i,j),l)
print(ans)
### BUGGY CODE ###

r, g, b, n = map(int,input().split())
ans = 0

for i in range(n+1):
    if (i*r) > n:
        break
    for j in range(n+1):
        if (i*r) + (j*g) > n:
            break
        if n-(i*r)-(j*g) >= 0 and (n-(i*r)-(j*g))%b == 0:
            ans += 1

print(ans)


### FIXED CODE ###

r,g,b,n=map(int, input().split())

sum=0

for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n-i*r-j*g)%b==0:
            sum=sum+1
        #    print(i*r,j*g,(n-(i*r)-(j*g))%b)

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

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

def gcd(m, n):
  while n:
    m, n = n, m%n
  return m

ans = []
for i in range(N):
  tmp = A[:i] + A[i+1:]
  res = tmp[0]
  for r in range(1,len(tmp)):
    res = gcd(res, tmp[r])
  ans.append(res)
print(max(ans))

### FIXED CODE ###

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

def gcd(m, n):
  while n:
    m, n = n, m%n
  return m

L = [0]
R = [0]
for i in range(N):
  L.append(gcd(L[i], A[i]))
  R.append(gcd(R[i], A[-(i+1)]))
R = R[::-1]
ans = 0
for i in range(N):
  ans = max(ans, gcd(L[i], R[i+1]))
print(ans)
### BUGGY CODE ###

from fractions import gcd
def main():
    N=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    c=A[0]
    for a in A:
        c=c*a//gcd(c,a)
    b=0
    for a in A:
        b+=c//a
        b%=mod
    print(b)
main()

### FIXED CODE ###

from fractions import gcd
def main():
    N=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    b=0
    c=1
    for a in A:
        c=c*a//gcd(c,a)
    c%=mod
    for a in A:
        b+=c*pow(a,mod-2,mod)
    print(b%mod)
if __name__=="__main__":
    main()
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
      for z in range(k+1):
          if s == x + y + z:
              ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z and z <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

import math

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

mod = 10**9+7

def lcm(x, y):
  return (x*y) // math.gcd(x, y)

LCM = A[0]
for i in range(N-1):
  LCM = lcm(LCM, A[i+1])

ans = 0
for a in A:
  ans += LCM // a
  ans %= mod

print(ans)

### FIXED CODE ###

import math

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

mod = 10**9+7

def lcm(x, y):
  return (x // math.gcd(x, y)) * y

LCM = A[0]
for i in range(N-1):
  LCM = lcm(LCM, A[i+1])

LCM %= mod

ans = 0
for a in A:
  ans += LCM * pow(a, mod-2, mod) % mod
  ans %= mod

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

# Beginner 50 C
import copy

N, x = map(int, input().split())
A = list(map(int, input().split()))
B = copy.deepcopy(A)

for i in range(N-1):
    while A[i] + A[i+1] > x:
        if A[i+1] != 0:
        	  A[i+1] -= 1
        else:
            A[i] -= 1

cnt = sum(B) - sum(A)
print(cnt)


### FIXED CODE ###

# Beginner 50 C
N, x = map(int, input().split())
A = list(map(int, input().split()))
sum_s = sum(A)

for i in range(N-1):
    s = A[i] + A[i+1] - x
    if s > 0:
        A[i+1] = x - A[i]
        if A[i+1] >= 0:
            pass
        else:
            A[i] = A[i] + A[i+1]
            A[i+1] = 0
    else:
        pass

sum_e = sum(A)
print(sum_s - sum_e)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from operator import itemgetter

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

LRi = []
for i in range(M):
    L, R = map(int, input().split())
    LRi.append((L,R))


LRi.sort(key=itemgetter(1))

pqi = []
for i in range(Q):
    p, q = map(int, input().split())
    pqi.append((p,q))


for (p, q) in pqi:
    cnt = 0
    for (L,R) in LRi:
        if p <= L and R <= q:
            cnt += 1
        elif q < R:
            break
        elif L < p:
            continue
    print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# import numpy as np

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

# Xi = np.zeros((N+1,N+1),dtype=np.int32)
Xi = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    Xi[L][R] += 1

# Ci = np.zeros((N+1,N+1),dtype=np.int32)
Ci = [[0]*(N+1) for i in range(N+1)]
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for r in range(N+1):
    tmp = 0
    for l in range(N+1):
        tmp += Ci[l][r]
        Ci[l][r] = tmp

# print(Ci)

pqi = []
for i in range(Q):
    p, q = map(int, input().split())
    pqi.append((p,q))

for (p, q) in pqi:
    tmp = Ci[q][q] - Ci[q][p-1]  - Ci[p-1][q] + Ci[p-1][p-1]
    print(tmp)
### BUGGY CODE ###

import math
import itertools
import sys
input = sys.stdin.readline


# 素数判定
def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return P

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(10**5)
w=[0]*(10**5+1)
for i in range(len(v)):
    w[v[i]]+=1

for i in range(10**5,0,-1):
    if w[i]==1:
        if w[(i+1)//2]==1:
            continue
        else:
            w[i]=0
w=list(itertools.accumulate(w))

for i,j in s:
    print(w[j+1] -w[i-1])

### FIXED CODE ###

import itertools
from itertools import accumulate

q=int(input())
x=[list(map(int, input().split())) for i in range(q)]
s=[0]*(1+10**5)
#素数のリスト
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

primes.sort()
for i in range(len(primes)):
    if primes[i]>5*10**4:
        break
    primes.append(2*primes[i])

primes.sort()
count=0
for i in range(len(primes)-1):
    if primes[i+1]-primes[i]==1 and primes[i+1]%2==0:
        s[primes[i]]=1
s=itertools.accumulate(s)
s=list(s)
a=0
b=0
for i in range(q):
    print(s[x[i][1]]-s[x[i][0]-1])
### BUGGY CODE ###


def main(N, M, a):
    dp = [0] * (N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in a else 0
    for i in range(2, len(dp)):
        dp[i] = dp[i-1] + dp[i-2] if i not in a else 0
    return dp[-1] % (10**9+7)

N, M = map(int, input().split())
a = list(int(input()) for _ in range(M))
print(main(N,M,a))

### FIXED CODE ###


def main(N, M, a):
    dp = [-1] * (N+1)
    dp[0] = 1
    dp[1] = 1
    for i in a :
        dp[i] = 0
    for i in range(2, len(dp)):
        dp[i] = dp[i-1] + dp[i-2] if dp[i] != 0 else 0
    return dp[-1] % (10**9+7)

N, M = map(int, input().split())
a = list(int(input()) for _ in range(M))
print(main(N,M,a))