Harryxun/stf_run huggingface dataset:
import math
from functools import reduce


def spaceinput():
    return list(map(int,input().split(" ")))


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

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



N,X=spaceinput()

x=spaceinput()

x.append(X)
x=sorted(x)
d=[]
for i,xx in enumerate(x[:-1]):
    d.append(x[i+1]-x[i])

#print(d)

print(gcd(d))


### FIXED CODE ###

import math
import numpy as np
from functools import reduce


def spaceinput():
    return list(map(int,input().split(" ")))


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

#def gcd(numbers):
#    return reduce(np.gcd, numbers)

def gcd(a, b):
    if not b:
        return a
    else:
        return gcd(b, a % b)


def gcd_n(numbers):
  '''Returns GCD of given n numbers.
  Argument: numbers - List of given numbers
  '''
  return reduce(lambda x, y: gcd(x, y), numbers)



N,X=spaceinput()

x=spaceinput()

x.append(X)
x=sorted(x)
d=[]
for i,xx in enumerate(x[:-1]):
    d.append(x[i+1]-x[i])

#print(d)

#print( np.gcd(12, 20))
print(gcd_n(d))
import math

A,B,C,D = (int(i) for i in input().split())

E =C*D//math.gcd(C,D)

if A%C == 0:
    C_div = B//C - A//C + 1
else:
    C_div = B//C - A//C

if A%D == 0:
    D_div = B//D - A//D + 1
else:
    D_div = B//D- A//D


if A%E == 0:
    CandD_div  = B//E - A//E + 1
else:
    CandD_div  = B//E- A//E


ans = B - A + 1 - (C_div + D_div - CandD_div)
print(ans)


### FIXED CODE ###

import fractions

A,B,C,D = map(int,input().split())

E =C*D//fractions.gcd(C,D)

if A%C == 0:
    C_div = B//C - A//C + 1
else:
    C_div = B//C - A//C

if A%D == 0:
    D_div = B//D - A//D + 1
else:
    D_div = B//D- A//D


if A%E == 0:
    CandD_div  = B//E - A//E + 1
else:
    CandD_div  = B//E- A//E


ans = B - A + 1 - (C_div + D_div - CandD_div)
print(ans)
def binary_search(A,x,flag):
  start = 0
  end = len(A)-1
  
  while start < end:
    middle = (start + end) // 2
    if flag:# Aの時
      if A[middle] < x <= A[middle+1]:
        return middle + 1
      elif x <= A[middle]:
        end = middle
      else:
        start = middle + 1
    else:# Bの時
      if A[middle] <= x < A[middle+1]:
        return middle + 1
      elif x < A[middle]:
        end = middle
      else:
        start = middle + 1
    if end == 0: # 小さい
      return 0
    elif start == len(A)-1:
      return len(A)
        
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0

for i in range(N):
  ans += binary_search(A,B[i],True)*(N-binary_search(C,B[i],False))#B[i]より小さいAの数とB[i]より大きいCの数の積
print(ans)

### FIXED CODE ###

def binary_search(A,x,flag):
  start = 0
  end = len(A)-1
  
  while start < end:
    middle = (start + end) // 2
    if flag:# Aの時
      if A[middle] < x <= A[middle+1]:
        return middle + 1
      elif x <= A[middle]:
        end = middle
      else:
        start = middle + 1
    else:# Bの時
      if A[middle] <= x < A[middle+1]:
        return middle + 1
      elif x < A[middle]:
        end = middle
      else:
        start = middle + 1
  if end == 0: # 小さい
    return 0
  elif start == len(A)-1:
    return len(A)
        
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

# N=1はコーナーケース
if N == 1:
  print(1) if A[0] < B[0] < C[0] else print(0)
else:
  ans = 0
  for i in range(N):
    ans += binary_search(A,B[i],True)*(N-binary_search(C,B[i],False))#B[i]より小さいAの数とB[i]より大きいCの数の積
  print(ans)
a = [int(input()) for i in range(3)]
if a[0] == 2:
  print("Hello World")
else:
  print(a[1]+a[2])

### FIXED CODE ###

a = int(input())
if a == 1:
  print("Hello World")
else:
  b = int(input())
  c = int(input())
  print(b + c)
N = int(input())
strX = input()

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

#(2**i)÷popcountを保存するリストを作成
f_tp = [0] * N  
f_tm = [0] * N  

for i in range(0,N):
  f_tp[i] = (2**(N-1-i)) % (pop_c + 1) 
  f_tm[i] = (2**(N-1-i)) % (pop_c - 1) 

  
for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + f_tp[i]) % (pop_c + 1) 
    Ans = 1
    
  elif strX[i] == '1' and pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - f_tm[i]
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)


### FIXED CODE ###

N = int(input())
strX = input()

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + pow(2,(N-1-i),(pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (pow(2,(N-1-i),(pop_c - 1)))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)
n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

cs = [a,b,c,d,e]

min_idx = cs.index(min(cs))

if min_idx == 0:
    t = int(n / cs[min_idx]) + 1
elif min_idx == 1:
    amari = n % cs[min_idx-1]
    t = int(cs[min_idx-1] / (cs[min_idx-1] - cs[min_idx])) + 1
    if amari <= cs[min_idx]:
        t = t - 1
else:
    amari = cs[min_idx-2] % cs[min_idx-1]
    t = int(cs[min_idx-1] / (cs[min_idx-1] - cs[min_idx])) + 1
    if aamari <= cs[min_idx]:
        t = t - 1

print(4 + t)

### FIXED CODE ###

import math
n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
 
cs = [a,b,c,d,e]
 
min_cs = min(cs)
 
t = math.ceil(n / min_cs)

print(t + 4)
s = input()
if s=="ABC:
print("ARC")
else:
  print("ABC")

### FIXED CODE ###

s = input()
if s=="ABC":
  print("ARC")
else:
  print("ABC")
N = int(input())
S = input()

ans = 0
for p in range(1000):
  s = '{:03}'.format(p)
  i = 0
  for j in range(N):
    if i < 3 and S[j] == s[i]:
      i += 1
  	if i== 3:
      ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for p in range(1000):
  s = '{:03}'.format(p)
  i = 0
  for j in range(N):
    if i < 3 and S[j] == s[i]:
      i += 1
  if i == 3:
    ans += 1
print(ans)
n    = int(input())
li   = [list(map(int,input().split())) for i in range(n-1)]
clr  = [0]*n
done = [0]*n
tmp  = 0

print(li)

for i in li:
  if i[0]>i[1]:
    tmp  = i[0]
    i[0] = i[1]
    i[1] = tmp
  i[2] %= 2

li.sort()

for i in li:
  if done[i[0]-1]==0 and done[i[1]-1]==0:
    if i[2]==1:
      i[1] = i[0]^1
    done[i[0]-1] = 1
    done[i[1]-1] = 1
  elif done[i[0]-1]==1 and done[i[1]-1]==0:
    if i[2]==1:
      i[1] = i[0]^1
    done[i[1]-1] = 1
  elif done[i[0]-1]==0 and done[i[1]-1]==1:
    if i[2]==1:
      i[0] = i[1]^1
    done[i[0]-1] = 1
  else:
    continue

for i in clr:
  print(i)

### FIXED CODE ###

from collections import deque
# from fractions import gcd # >=Python3.5
# from math import gcd # <Python3.5

n  = int(input())
li = [list(map(int,input().split())) for i in range(n-1)]

road = [[] for i in range(n)]
cost = [[] for i in range(n)]

for i in li:
  i[0]-=1
  i[1]-=1
  road[i[0]].append(i[1])
  road[i[1]].append(i[0])
  cost[i[0]].append(i[2]%2)
  cost[i[1]].append(i[2]%2)

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
  # BFS/DFS
  v = que.popleft()
  for i,r in enumerate(road[v]):
    if dist[r]!=-1:
      continue
    dist[r] = (dist[v]+cost[v][i])%2
    que.append(r)

print(*dist,sep='\n')
from collections import Counter

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

c = Counter(a)
m = max(a)

flag = True

for i in range(1, m+1):
    if i<=m//2:
        if c[i]>1:
            flag = False
    else:
        if c[i]<2:
        flag = False
        break
if m%2==0 and c[m//2]!=1:
    flag = False
print('Possible' if flag else 'Impossible')

### FIXED CODE ###

from collections import Counter

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

c = Counter(a)
m = max(a)

flag = True

if m%2 == 0:
    for i in range(1,m+1):
        if i<m//2:
            if c[i]!=0:
                flag = False
                break
        elif i==m//2:
            if c[i]!=1:
                flag = False
                break
        else:
            if c[i]<2:
                flag = False
                break
else:
    for i in range(1,m+1):
        if i<=m//2:
            if c[i]!=0:
                flag = False
                break
        elif i==m//2+1:
            if c[i]!=2:
                flag = False
                break
        else:
            if c[i]<2:
                flag = False
                break

print('Possible' if flag else 'Impossible')
import heapq


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()))

r = []
g = []
nc = []
for p in P:
    heapq.heappush(r, -p)

for q in Q:
    heapq.heappush(g, -q)

for i in R:
    heapq.heappush(nc, -i)

ans = 0
#print(r,g,nc)
while X > 0 or Y > 0:


    if X > 0 and Y > 0:
        if X > 0 and r[0] < nc[0]:
            ans += -1 * r[0]
            heapq.heappop(r)
            X -= 1

        elif Y > 0 and g[0] < nc[0]:
            ans += -1 * g[0]
            heapq.heappop(g)
            Y -= 1
        else:
            if abs(nc[0] - r[0]) >= abs(nc[0] - g[0]):
                ans += -1 * nc[0]
                heapq.heappop(nc)
                X -= 1
            else:
                ans += -1 * nc[0]
                heapq.heappop(nc)
                Y -= 1
        
    elif X > 0:
        if r[0] < nc[0]:
            ans += -1 * r[0]
            heapq.heappop(r)
            X -= 1
        else:
            ans += -1 * nc[0]
            heapq.heappop(nc)
            X -= 1
    else:
        if g[0] < nc[0]:
            ans += -1 * g[0]
            heapq.heappop(g)
            Y -= 1
        else:
            ans += -1 * nc[0]
            heapq.heappop(nc)
            Y -= 1

    #print("--", r,g,nc,X,Y)
            

print(ans)

### FIXED CODE ###

import heapq


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()))


rg = [(p, "r") for p in P] + [(q, "g") for q in Q]
rg.sort()
nc = R
nc.sort()

ans = 0
cnt_r, cnt_g, cnt_nc = 0, 0, 0


while cnt_r + cnt_g + cnt_nc < X + Y:

    if cnt_r == X:
        while rg[-1][1] == "r":
            rg.pop()

    if cnt_g == Y:
        while rg[-1][1] == "g":
            rg.pop()


    if len(nc) > 0 and nc[-1] > rg [-1][0]:
        tmp = nc.pop()
        cnt_nc += 1
    else:
        tmp, c = rg.pop()
        if c == "r":
            cnt_r += 1

        else:
            cnt_g += 1


    ans += tmp

print(ans)
s = input()
k = int(input())
if int(s[0]) != 1:
    print(s[0])
else:
    print(s[1])


### FIXED CODE ###

s = input()
k = int(input())
for i in range(len(s)):
    if s[i] != '1':
        print(s[i])
        exit()
    else:
        if i == len(s) - 1:
            print('1')
            exit()
        if i + 1 == k:
            print('1')
            exit()
from sys import stdin
input = stdin.readline()

n = int(input())
a = [0]*4

for i in range(n):
    s = input().strip()
    if s == "AC":
        a[0] += 1
    elif s == "WA":
        a[1] += 1
    elif s == "TLE":
        a[2] += 1
    else:
        a[3] += 1
        
print("AC x "*a[0])
print("WA x "*a[1])
print("TLE x "*a[2])
print("RE x "*a[3])

### FIXED CODE ###

n = int(input())
a = [0]*4

for i in range(n):
    s = input()
    if s == "AC":
        a[0] += 1
    elif s == "WA":
        a[1] += 1
    elif s == "TLE":
        a[2] += 1
    else:
        a[3] += 1
        
print("AC x",a[0])
print("WA x",a[1])
print("TLE x",a[2])
print("RE x",a[3])
N,C=map(int,input().split())
T=10**5+2
sm=[0]*(T)
l=[]
r=[]
c=[]
for i in range(N):
    s,t,k=map(int,input().split())
    l.append(s)
    r.append(t)
    c.append(k)
for i in range(1,C+1):
    tt=[0]*T
    for j in range(N):
        if c[j]==i:
            tt[l[j]*2]+=1
            tt[r[j]*2+1]-=1
    for j in range(T):
        if tt[j]>0:
            sm[j-1]+=tt[j]
        else:
            sm[j]+=tt[j]
for j in range(T-1):
    sm[j+1]+=sm[j]
print(max(sm))


### FIXED CODE ###

from collections import defaultdict
from copy import deepcopy
from math import log
from itertools import accumulate

N,C=map(int,input().split())
T=10**5+1
programs=defaultdict(list)
for i in range(N):
    s,t,c=map(int,input().split())
    programs[c].append((s,t))
imos=[0]*(T)
for c,p in programs.items():
    p.sort()
    ps,pt=p[0]
    for s,t in p[1:]:
        if pt==s:
            pt=t
            continue
        imos[ps-1]+=1
        imos[pt]-=1
        ps,pt=s,t
    imos[ps-1]+=1
    imos[pt]-=1
print(max(accumulate(imos)))
#!/usr/bin/env python
# -*- coding:utf-8 -*-

K = int(input())

def digit(i):
    if i>0:
        return digit(i//10)+[i%10]
    else:
        return []
F=0
N=0
d=0

def func(F,d,N):
    for i in range(1,10):
        print(N+i*(10**d))
        F=F+1
        if F==K:
            exit()

    N=N+9*(10**d)
    d=d+1
    return F,d,N 


while True:
    F,d,N=func(F,d,N)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*- 
S = list(input())
Ans=0
for i in S:
    if i=="+":
        Ans = Ans+1
    else:
        Ans = Ans-1
print(Ans)
def permutuation(n):
    if n < 2: return 1
    return n * permutuation(n - 1)


def combo(n, r):
    x = permutuation(n)
    y = permutuation(n-r)
    z = permutuation(r)
    return int(x / (y * z))


count = int(input())
li = list(map(int, input().split()))

sli = sorted(li)

pair_a = 0
pair_b = 0
current_max = 0

for i in range(1,len(sli)):
    for j in range(0, i):
        val = combo(sli[i], sli[j])
        # print(str(sli[i]) + ", " + str(sli[j]) + ", " + str(val))
        if val > current_max:
            current_max = val
            pair_a = sli[i]
            pair_b = sli[j]

print(str(pair_a) + " " + str(pair_b))

### FIXED CODE ###

count = int(input())
li = list(map(int, input().split()))

sli = sorted(li)

pair_a = sli[len(sli) - 1]
pair_b = 0
current_max = 0

i = sli[len(sli) - 1]

diff = 10**9
for j in range(0, len(sli) - 1):
    h = pair_a / 2
    if abs(h - sli[j]) < diff:
        diff = abs(h - sli[j])
        pair_b = sli[j]

print(str(pair_a) + " " + str(pair_b))
abc = ['a','b','c','d','e','f','g','h','i','j','k',
'l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

ans = []
def rec(n):
    print(n,n%26,abc[n%26])
    #print(n)
    if n>=26:
        ans.append(abc[int(n%26)])
        return rec(int(n/26))
        #ans.append(abc[int(n%26)])
        #print(n%26)
    else:
       ans.append(abc[int(n)])
       #print(n%26)
N = int(input())
#rec(N)
#i=N
r=1
q=N
while q>0:

    r = q%27
    if q>26:
        ans.append(abc[r])
    else:
        ans.append(abc[r-1])
    q=int(q/27)
for i in range(len(ans)-1,-1,-1):
    print(ans[i],end="")

### FIXED CODE ###

abc = ['a','b','c','d','e','f','g','h','i','j','k',
'l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

ans = []
def rec(n):
    #print(n,int(n/26),n%26,abc[n%26])
    n-=1
    ans.append(abc[n%26])
    #print(n)
    if n>=26:
        #ans.append(abc[int(n%26)-1])
        return rec(int(n/26))
        #ans.append(abc[int(n%26)])
        #print(n%26)
    else:
        pass
       #ans.append(abc[int(n)])
       #print(n%26)
N = int(input())
rec(N)
#i=N

for i in range(len(ans)-1,-1,-1):
    print(ans[i],end="")
import math
def resolve():
    a, b, x = list(map(int, input().split()))
    if (a**2)*b/2 > x:
        print(90-math.degrees(math.atan(2*x/((b**2)*a))))
    else:
        print(90-math.degrees(math.atan(a**3/(2*(a**2)*b-2*x))))
    

if '__main__' == __name__:
    resolve()


### FIXED CODE ###

import math
def resolve():
    a, b, x = list(map(int, input().split()))
    if (a**2)*b/2 > x:
        print(90-math.degrees(math.atan(2*x/((b**2)*a))))
    else:
        if x == (a**2)*b:
            print(0)
        else:
            print(90-math.degrees(math.atan(a**3/(2*(a**2)*b-2*x))))
    

if '__main__' == __name__:
    resolve()
S=input()
print(S.count("+")-S.count("-")

### FIXED CODE ###

s=input()
p=s.count("+")
m=s.count("-")
print(p-m)
a = input()
s = input()

if a < 3200:
    print(s)
elif a >= 3200:
    print('red')

### FIXED CODE ###

a = int(input())
s = input()

if a >= 3200:
    print(s)
else:
    print("red")
n = int(input())
s = input()
if len(s) % 2 != 0:
  print('No')
else:
  l = len(s) // 2
  if s[:l] == s[l:]:
    print('Yes')
  else:
    pring('No')

### FIXED CODE ###

n = int(input())
s = str(input())
if n % 2 == 1:
  print('No')
else:
  numT = n // 2
  if s[0:numT] == s[numT:n]:
    print('Yes')
  else:
    print('No')
n, m = map(int, raw_input().split())
a, b = [], []
for _ in range(n):
	a.append(map(int, raw_input().split()))
for _ in range(m):
	b.append(int(raw_input()))
for i in range(n):
	c[i] = 0
	for j in range(m):
		c[i] += a[i][j]*b[j]
	print c[i]

### FIXED CODE ###

n, m = map(int, raw_input().split())
a, b = [], []
c = [0 for _ in range (n)]
for _ in range(n):
	a.append(map(int, raw_input().split()))
for _ in range(m):
	b.append(int(raw_input()))
for i in range(n):
	for j in range(m):
		c[i] += a[i][j]*b[j]
	print c[i]
N,P=map(int,input().split());S,a,i,j,c=[*map(int,input())],0,0,1,[1]+[0]*P
if 10%P:
	for v in S[::-1]:i=(i+v*j)%P;j=j*10%P;a+=c[i];c[i]+=1
else:
	for i,v in enumerate(S):
		if v%P<1:a+=i+1
print(a)

### FIXED CODE ###

N,P=map(int,input().split());S,a,i,j,c=list(map(int,input())),0,0,1,[1]+[0]*P
if 10%P:
	for v in S[::-1]:i=(i+v*j)%P;j=j*10%P;a+=c[i];c[i]+=1
else:
	for i,v in enumerate(S):
		if v%P<1:a+=i+1
print(a)
N,L=map(int,input().split())
S=[]
S_list=[]
for i in range(N):
    S.append(input())
S.sort()
print(''.join(S))

### FIXED CODE ###

A,B,C=map(int,input().split())
a=str(A)
b=str(B)
c=str(C) 
s=a+b+c
if s.count("5")==2 and s.count("7")==1:
    print("YES")
else:
    print("NO")
S=input()
K=int(input())

end=0
if K!=1:
    S_old = S
    i=-1
    while S_old[0] == S_old[i]:
        S= S + S[0]
        i-=1
ans = 0
i=0
while i<len(S)-1:
    renzoku=1
    x=i
    while S[x] == S[i+1]:
        renzoku+=1
        if i+2 < len(S):
            i=i+1
        else:
            break
    if renzoku >1:
        ans+=renzoku//2
    i+=1
if K== 1:
    pass
else:
    S=S_old
    ans = ans*(K-1)
    i=0
    while S[i] == S[0]:
        i+=1
    S=S[i:]
    i=0
    while i<len(S)-1:
        renzoku=1
        x=i
        while S[x] == S[i+1]:
            renzoku+=1
            if i+2 < len(S):
                i=i+1
            else:
                break
        if renzoku >1:
            ans+=renzoku//2
        i+=1
print(ans)

### FIXED CODE ###

S=input()
K=int(input())
flg=False
for s in S:
    if S[0] != s:
        flg=True
        break
if not flg:
    print(len(S)*K//2)
    exit()
ans = 0
i=0
while i<len(S)-1:
    renzoku=1
    x=i
    while S[x] == S[i+1]:
        renzoku+=1
        if i+2 < len(S):
            i=i+1
        else:
            break

    if renzoku >1:
        ans+=renzoku//2
    i+=1

if S[0] == S[-1]:
    s=S[0]
    top=0
    bottom=0
    i=0
    while S[i] == s:
        top+=1
        i+=1
    i=-1
    while S[i] == s:
        bottom+=1
        i-=1
    if (top%2) + (bottom%2) == 2:
        print((ans+1)*K-1)
        exit()
    
print(ans*K)
from collections import deque
def main():
    n = int(input())
    b = np.array(list(map(int, input().split())))
    s = set()
    q = deque()

    q.append([tuple(b), [0]*n, 0])
    ans = None
    while q:
        now, history, depth = q.popleft()
        if now in s:
            continue
        s.add(now)
        if len(now) == 0:
            ans = history
            break
        for i, j in enumerate(now):
            if i+1 == j:
                tmp = history[::]
                tmp[depth] = i+1
                q.appendleft([tuple(now[:i] + now[i+1:]), tmp, depth+1])
    if ans is None:
        print(-1)
    else:
        for i in ans[::-1]:
            if i == 0:
                break
            print(i)
if __name__ == "__main__":
    main()

### FIXED CODE ###

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

def check(b):
    for i in range(len(b))[::-1]:
        if i+1 == b[i]:
            return i
    return -1

ans = []
for i in range(n):
    ind = check(b)
    if ind >= 0:
        ans.append(ind+1)
        b = b[:ind] + b[ind+1:]
    else:
        print(-1)
        exit()
for i in ans[::-1]:
    print(i)
from bisect import bisect_left
from collections import deque

N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        idx = bisect_left(A, pow2 - A[-1])
        for _ in range(idx):
            A_tmp.append(A.popleft())
        if len(A) < 2: break
        if A[0] + A[-1] == pow2:
            A.popleft()
            ans += 1
        A.pop()
        if len(A) < 2: break
    A = A_tmp + A
                    
print(ans)



### FIXED CODE ###

from bisect import bisect_left, bisect_right
from collections import deque

N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    if len(A) < 2: break
    while len(bin(A[-1])) - 2 > t:
        A.pop()
        if len(A) < 2: break
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        r = A.pop()
        idx = bisect_left(A, pow2 - r)
        for _ in range(idx):
            A_tmp.appendleft(A.popleft())
        if len(A) == 0: break
        if A[0] + r == pow2:
            A.popleft()
            ans += 1
        if len(A) < 2: break
    A.extendleft(A_tmp)
                    
print(ans)
inport sys
str = []
for line in sys.stdin.readlines()
    str.append(line.rstrip())
num = len(str)
for i in range(num)
    s = str.split(" ")
    a = int(s[0])
    b = s[1]
    c = s[2]
    if b =="?":
        break
    if b == "+":
        print(a+c)
    if b == "-":
        print(a-c)
    if b == "*":
        print(a*c)
    if b == "/"
        print(a//c)

### FIXED CODE ###

for i in range(100000):
    s = input().rstrip().split(" ")
    a = int(s[0])
    b = s[1]
    c = int(s[2])
    if b =="?":
        break
    if b == "+":
        print(a+c)
    if b == "-":
        print(a-c)
    if b == "*":
        print(a*c)
    if b == "/":
        print(int(a/c))
N, M , Q = map(int, input().split())

LR = [[0 for _ in range(N+2-i) for _ in range(N+2)]
for i in range(M):
  L, R = map(int, input().split())
  LR[L][R-L+1] += 1

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


### FIXED CODE ###

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

LR = [[0]*(N+2-i) for i in range(N+2)]
for i in range(M):
  L, R = map(int, input().split())
  LR[L][R-L+1] += 1

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