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

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
import copy

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


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

A.sort()
rA.sort(reverse=True)
ans = 0
for i in range(len(rA)):
    if rA.count(rA[i]) >= 2:
        continue
    flag = 1
    for j in range(len(A)):
        if rA[i] < A[j] * 2:
            break
        if rA[i] % A[j] == 0:
            flag = -1
            break
    if flag == 1:
       ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce


n = int(input())
A = list(map(int, input().split()))
cnt_a = Counter(A)
memo = [1] * 1000001
for a in A:
    memo[a] = 1
A.sort()
a_max = max(A)
for a in A:
    if not memo[a]:
        continue
    for i in range(a * 2, a_max + 1, a):
        memo[i] = -1
for l in cnt_a.keys():
    if cnt_a[l] >= 2:
        memo[l] = "daburi"
ans = 0
for a in A:
    if memo[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
from heapq import heappop,heappush
import math
 
xs,ys,xt,yt = map(int,input().split())
n = int(input())
 
v = [[xs,ys,0]]
for _ in range(n):
    x,y,r = map(int,input().split())
    v.append([x,y,r])
v.append([xt,yt,0])
 
def dd(a,b):
    return max(0,math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) - a[2] - b[2])

m = dd(v[0],v[n+1])

edges=[[] for i in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        if i != j and dd(v[i],v[j]) <= m:
            edges[i].append((dd(v[i],v[j]),j))
            edges[j].append((dd(v[i],v[j]),i))
 
def dijkstra(s,n,edges):
    #edges[source] = [(cost_1,target_1),(cost_2,target_2),...]
    #import 'heap'
    d = [float('inf')] * n
    d[s] = 0
    q = [[d[s],s]]
    while q:
        dist_u, u = heappop(q)
        for c, v in edges[u]:
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q,[d[v],v])
    return d
 
ans = dijkstra(0,n+2,edges)
print(ans[n+1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
from heapq import heappop,heappush
import math
 
xs,ys,xt,yt = map(int,input().split())
n = int(input())
 
v = [[xs,ys,0]]
for _ in range(n):
    x,y,r = map(int,input().split())
    v.append([x,y,r])
v.append([xt,yt,0])
 
def dd(a,b):
    return max(0,math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) - a[2] - b[2])

edges=[[0]*(n+2) for _ in range(n+2)]
for i in range(n+2):
    for j in range(i+1,n+2):
        edges[i][j] = dd(v[i],v[j])
        edges[j][i] = dd(v[i],v[j])

def dijkstra(s,n,edges):
    #edges[i][j] : the cost of i→j
    #import 'heap'
    d = [float('inf') for _ in range(n)]
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d

ans = dijkstra(0,n+2,edges)
print(ans[n+1])
### BUGGY CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			new=True
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while new:
	black_new=[]
	new=False
	for i in range(h):
		for j in range(w):
			if [i,j] in black:
				if i!=0 and field[i-1][j]==False:
					field[i-1][j]=True
					black_new.append([i-1,j])
					new=True
				if i!=h-1 and field[i+1][j]==False:
					field[i+1][j]=True
					black_new.append([i+1,j])
					new=True
				if j!=0 and field[i][j-1]==False:
					field[i][j-1]=True
					black_new.append([i,j-1])
					new=True
				if j!=w-1 and field[i][j+1]==False:
					field[i][j+1]=True
					black_new.append([i,j+1])
					new=True
	black=black_new
	ans+=1
print(ans-1)




### FIXED CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while len(black):
	black_new=[]
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if i!=0 and field[i-1][j]==False:
			field[i-1][j]=True
			black_new.append([i-1,j])
		if i!=h-1 and field[i+1][j]==False:
			field[i+1][j]=True
			black_new.append([i+1,j])
		if j!=0 and field[i][j-1]==False:
			field[i][j-1]=True
			black_new.append([i,j-1])
		if j!=w-1 and field[i][j+1]==False:
			field[i][j+1]=True
			black_new.append([i,j+1])
	black=black_new
	ans+=1
print(ans-1)
### BUGGY CODE ###

def can_load(baggages, trucks, max_load):
    truck_list = [max_load for x in range(trucks)]

    for truck in truck_list:
        while truck > 0:
            if len(baggages) == 0:
                #print(max_load,"True")
                return True
            if truck >= baggages[0]:
                truck -= baggages[0]
                baggages.pop(0)
            else:
                break
    #print(max_load, len(baggages) == 0)
    return len(baggages) == 0

def main():
    num_baggages, num_trucks = map(int, input().split())
    baggages = [int(input()) for x in range(num_baggages)]

    start = max(sum(baggages) // num_trucks, min(baggages))
    end = sum(baggages)

    while start < end:
        mid = (start + end) // 2
        if can_load(baggages[:], num_trucks, mid):
            end = mid
        else:
            start = mid + 1

    print(start)
    return


main()


### FIXED CODE ###

import sys
def can_load(num_baggages, baggages, num_truck, max_load):
    bag_no = 0

    for i in range(num_truck):
        load_cap = max_load
        while load_cap > 0:
            if bag_no >= num_baggages:
                #print(max_load, "True")
                return True
            if load_cap >= baggages[bag_no]:
                load_cap -= baggages[bag_no]
                bag_no += 1
            else:
                break
    #print(max_load, bag_no >= num_baggages)
    return bag_no >= num_baggages

def main():
    num_baggages, num_trucks = map(int, input().split())
    baggages = tuple(map(int, sys.stdin.read().splitlines()))

    start = max(sum(baggages) // num_trucks, min(baggages))
    end = sum(baggages)

    while start < end:
        mid = (start + end) // 2
        if can_load(num_baggages, baggages, num_trucks, mid):
            end = mid
        else:
            start = mid + 1

    print(start)
    return


main()
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a,b,c = (list(map(int, input().split())) for _ in range(3))
bc = sorted(i+j for i in b for j in c)[::-1][:k]
abc = sorted(i+j for i in sorted(a) for j in bc)[::-1][:k]
for i in abc:
    print(i)

### FIXED CODE ###

from heapq import *
x,y,z,K = map(int, input().split())
m = [sorted(map(int, input().split()))[::-1] for _ in range(3)]
q = [(-sum(i[0] for i in m),(0,0,0))]
r = 0
s = set()
for _ in range(K):
    v,a = heappop(q)
    v = -v
    print(v)
    for p in ((0,0,1),(0,1,0),(1,0,0)):
        p = tuple(i+j for i,j in zip(p,a))
        if not p in s and all(i<j for i,j in zip(p,(x,y,z))):
            s.add(p)
            heappush(q, (-sum(i[j] for i,j in zip(m,p)), p))
### BUGGY CODE ###

import itertools

n=int(input())
a=list(map(int,input().split()))
#n=6
#a=[1,2,3,4,5,6]

if n==2:
    print(abs(a[1]-a[0]))
else:
#    for i in range(n):
#        if a[i]<0:
#            a[i]=-a[i]
#        else:
#            break
#    a.sort(reverse=True)
    asum=sum(a)
#    print("asum:",asum)
# itertools 使用 bit全探索
    xmin=asum
    for ip in itertools.product([0,1], repeat=n):
        xsum=sum([a[i] for i in range(len(ip)) if ip[i]==1])
#        xsum=0
#        for i in range(len(ip)):
#            if ip[i]==1:
#                xsum=xsum+a[i]
#        print("xsum:",xsum,ip)
        xmin=min(xmin,abs(asum-2*xsum)) 
    print(xmin)


### FIXED CODE ###

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

if n==2:
    print(abs(a[1]-a[0]))
else:
    asum=sum(a)
    xsum=0
    xmin=n*(10**9)+1
    for i in range(n-1):
        xsum=xsum+a[i]
        xmin=min(xmin,abs(asum-2*xsum))
    print(xmin)
### BUGGY CODE ###

N,M = map(int,input().split())
count = 0
while(1):
    if N>=1:
        if M>=2:
            N -= 1
            M -= 2
            count += 1
        else:
            break
    else:
        while(1):
            if M >= 4 :
                M -= 4
                count += 1
            else:
                break
        break
        
print(count)


### FIXED CODE ###

import math
N,M = map(int,input().split())
count = 0
if N*2>M:
    count = math.floor(M/2)
else:
    temp=M-2*N
    count = N+math.floor(temp/4)

print(count)
### BUGGY CODE ###

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

dp = [10**10]*n
dp[0] = 0

for i in range(n-1):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))
print(dp[-1])


### FIXED CODE ###

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

dp = [10**10] * n
dp[0] = 0

for i in range(n-1):
    for j in range(1, k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))
print(dp[-1])
### BUGGY CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
if n == 2:
    print(A[1])
    print(A[0])    
else:
    for i in range(n):
        if i == 0:
            print(max(A[1 : ]))
        elif i == n - 1:
            print(max(A[ : n]))
        else:
            a = max(A[ : i])
            b = max(A[i + 1 : ])
            print(max(a, b))

### FIXED CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
semi_max_num, max_num = sorted(A)[-2:]
for a in A:
    if a != max_num:
        print(max_num)
    else:
        print(semi_max_num)
### BUGGY CODE ###

import collections

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

new_S = S.replace("AC", "12")
new_S_list = list(new_S)

for i in range(Q):
    left, right = map(int, input().split())
    count_one = collections.Counter(new_S_list[left-1:right-1])['1']
    print(count_one)

### FIXED CODE ###

import collections

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

new_S = S.replace("AC", "12")


count_one_list = [0] * len(S)
for i in range(len(S)-1):
    if new_S[i] == '1' and i == 0:
        count_one_list[i+1] += 1
    elif new_S[i] == '1':
        count_one_list[i+1] = count_one_list[i] + 1
    else:
        count_one_list[i+1] = count_one_list[i]
# count_one_list = [new_S[:i].count('1') for i in range(len(S))]
# print(count_one_list)

for i in range(Q):
    left, right = map(int, input().split())
    count_one = count_one_list[right-1] - count_one_list[left-1]
    print(count_one)
### BUGGY CODE ###

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

div = 1e9 + 7
step = [0] * (N+1)
step[0] = 1

for n in range(1, N+1):
  if n in A:
    continue

  if n == 1:
    step[n] = 1
  else:
    step[n] = int((step[n-2] + step[n-1]) % div)

ans = step[N]
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
skip = [False] * (N+1)
for _ in range(M):
  skip[int(input())] = True

div = 1e9 + 7
path = 0
prev1 = 1
prev2 = 0

for n in range(1, N+1):
  if skip[n]:
    path = 0
  else:
    path = int((prev1 + prev2) % div)

  prev1, prev2 = path, prev1

print(path)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def dfs(v,p=-1):
  for u in graph[v]:
    if u == p: continue
    ans[u] += ans[v]
    dfs(u,v)

N,Q = map(int,input().split())
graph = {i:[] for i in range(1,N+1)}
ans = [0 for i in range(N+1)]
for _ in range(N-1):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

for _ in range(Q):
  p, x = map(int,input().split())
  ans[p] += x

dfs(1)
print(' '.join([str(a) for a in ans[1:]]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input=lambda :sys.stdin.readline()

def sol():

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

  for _ in range(Q):
    p, x = map(int,input().split())
    ans[p-1] += x 
 
  def dfs(v,p=-1):
    for u in graph[v]:
      if u == p: continue
      ans[u] += ans[v]
      dfs(u,v)
  dfs(0)
  print(*ans)

sol()
### BUGGY CODE ###

n,m = map(int,input().split())
l = [0] * m
r = [0] * m
for i in range(0,m):
	l[i], r[i] = map(int, input().split())

count = 0
for i in range(1,n+1):
	
	if max(l) <= i <= min(r):
		count += 1
			
print(count)
		

### FIXED CODE ###

n,m = map(int,input().split())
l = [0] * m
r = [0] * m
for i in range(0,m):
	l[i], r[i] = map(int, input().split())

count = 0

max_l = max(l)
min_r = min(r)

for i in range(1,n+1):
	
	if max_l <= i <= min_r:
		count += 1
			
print(count)
### BUGGY CODE ###

s = str(input())
k = int(input())
s = list(s)

n = len(s)

import copy
l = copy.copy(s)
l = set(l)
l = list(l)
l.sort()
#print(l)

ans = set()
for i in range(len(l)):
    for j in range(n):
        if s[j] == l[i]:
            p = j
            temp = []
            while p < n:
                temp.append(s[p])
                ans.add(''.join(temp))
                p += 1
    if len(ans) >= k:
        break
#print(ans)
ans = list(ans)
ans.sort()
print(ans[k-1])


### FIXED CODE ###

s = str(input())
k = int(input())
s = list(s)

n = len(s)

import copy
l = copy.copy(s)
l = set(l)
l = list(l)
l.sort()
#print(l)

ans = set()
for i in range(len(l)):
    for j in range(n):
        if s[j] == l[i]:
            p = j
            temp = []
            while p < n and p-j+1 <= k:
                temp.append(s[p])
                ans.add(''.join(temp))
                p += 1
    if len(ans) >= k:
        break
#print(ans)
ans = list(ans)
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     lr = list(map(int, input().split()))
     for d in range(lr[0], lr[1]+1):
         s.append(d)

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[i] = 1
for i in range(n+1):
    if dp[i] == 0:
        continue
    for d in s:
        if i+d <= n:
            dp[i+d] = (dp[i+d] + dp[i]) % mod

print(dp[n] % mod)


### FIXED CODE ###

# DP, 累積和
n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     l, r = list(map(int, input().split()))
     s.append((l, r))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[1] = 1
dpsum = [0] * (n+1)
dpsum[1] = 1
for i in range(2, n+1):
    for l, r in s:
        li = i-r
        ri = i-l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] = (dp[i] + dpsum[ri] - dpsum[li-1]) % mod
    dpsum[i] = (dpsum[i-1] + dp[i]) % mod
    
print(dp[n])
### BUGGY CODE ###

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

t = n**0.5

cnt = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        for k in range(n//b+1):
            if i*r + j*g + k*b == n:
                cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
for i in range(3001):
    for j in range(3001):
        k = i*r + j*g
        if n >= k and (n-k) % b == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r%2==1:
                r-=1
                data[r-1]=x
            if l%2==1:
                data[l-1]=x
                l+=1
            l//=2
            r//=2
    a=[]
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        a.append(-(s==I)or s)
    print('\n'.join(map(str,a)))
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

from scipy.sparse import*
i=lambda:tuple(map(int,input().split()))
f=csgraph.floyd_warshall
n,m,l=i()
d=eval('[0]*-~n,'*-~n)
exec('a,b,c=i();d[a][b]=c;'*m)
d=f(f(d,0)<=l)
d[d>9e9]=0
exec('print(int(d[i()])-1);'*i()[0])

### FIXED CODE ###

from scipy.sparse import*
s=csgraph.floyd_warshall
n,m,l,*t=map(int,open(0).read().split())
d=eval('[9e9]*-~n,'*-~n)
for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=d[b][a]=c
d=s(d)
d[d>l]=9e9
d[d<=l]=1
d=s(d)
d[d>9e9]=9e9
for s,t in zip(*[iter(t[m*3+1:])]*2):print(int(d[s,t]%9e9-1))
### BUGGY CODE ###

N, Y = map(int, input().split())
count = 0

for i in range(N+1):# 1000円札
  for j in range(N+1):# 5000円札
    if count == 0:
      Z1 = Y - 1000*i - 5000*j
      Z = Z1//10000
      if (Z1 % 10000 == 0) & (Z == N-i-j) & (Z>=0):
        print(Z, j, i)
        count += 1
      
if count == 0:
  print('-1 -1 -1')

### FIXED CODE ###

N, Y = map(int, input().split())
count = 0
Y = Y//1000

for i in range(N+1):# 10000円札
  for j in range(N+1):# 5000円札
    if count == 0:
      X = Y - 10*i - 5*j
      if (X == N-i-j) & (X>=0):
        print(i, j, X)
        count += 1
    else:
      break

if count == 0:
  print('-1 -1 -1')
### BUGGY CODE ###

import collections
a=int(input())
ai = list(map(int, input().split()))
c = collections.Counter(ai)
val=0
for i in c.values():
    val+=i*(i-1)//2
for i in ai:
    b=ai.count(i)
    print(val-b+1)

### FIXED CODE ###

import collections
a=int(input())
ai = list(map(int, input().split()))
c = collections.Counter(ai)
val=0
for i in c.values():
    val+=i*(i-1)//2
for i in range(len(ai)):
    b=c[ai[i]]
    print(val-b+1)
### BUGGY CODE ###

n,x,y = map(int,input().split())

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数, w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

dis = [[float('inf')] * n for _ in range(n)]
ans = [0] * (n-1)
for i in range(n):
    for j in range(n):
        if abs(i - j) == 1:
            dis[i][j] = 1
dis[x-1][y-1] = 1
dis[y-1][x-1] = 1

for i in range(n):
    d = dijkstra(i, n, n, dis)
    for j in d:
        if j > 0:
            ans[j-1] += 1

for i in ans:
    print(i//2)


### FIXED CODE ###

import heapq
n,x,y = map(int,input().split())

roots = [[] for _ in range(n)]

for i in range(n):
    if i == 0:
        roots[i].append(1)
    elif i == n - 1:
        roots[i].append(n-2)
    else:
        roots[i].append(i-1)
        roots[i].append(i+1)

roots[x-1].append(y-1)
roots[y-1].append(x-1)
ans = [0] * (n-1)

for i in range(n):
    hq = []
    dis = [-1]* n
    dis[i] = 0
    heapq.heappush(hq, (0,i))
    while hq:
        dis1, place = heapq.heappop(hq)
        for j in roots[place]:
            if dis[j] == -1 or dis[j] > dis1 + 1:
                dis[j] = dis1 + 1
                heapq.heappush(hq, (dis1+1, j))
    for j in dis:
        if j > 0:
            ans[j-1] += 1

for i in ans:
    print(i//2)
### BUGGY CODE ###

from operator import itemgetter
import bisect

n, m, Q = map(int, input().split())
train = [list(map(int, input().split())) + [i] for i in range(m)]
train_L = []
train_R = []
L_n = []
R_n = []
for i in sorted(train, key=itemgetter(0)):
    train_L.append(i[0])
    L_n.append(i[2])
for i in sorted(train, key=itemgetter(1)):
    train_R.append(i[1])
    R_n.append(i[2])
for i in range(Q):
    p, q = map(int, input().split())
    p_set = set(L_n[bisect.bisect_left(train_L, p):])
    q_set = set(R_n[:bisect.bisect_right(train_R, q)])
    print(len(p_set & q_set))

### FIXED CODE ###

def getSumRange(L, R):
    ans = sum[R][R] - sum[R][L - 1] - sum[L - 1][R] + sum[L - 1][L - 1]
    return ans

n, m, Q = map(int, input().split())
L = [0] * m
R = [0] * m
for i in range(m):
    L[i], R[i] = map(int, input().split())
p = [0] * Q
q = [0] * Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())

sum = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
    sum[L[i]][R[i]] += 1
for i in range(n + 1):
    for j in range(n + 1):
        sum[i][j] += sum[i - 1][j]
        sum[i][j] += sum[i][j - 1]
        sum[i][j] -= sum[i - 1][j - 1]

for i in range(Q):
    ans = getSumRange(p[i], q[i])
    print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(str, input().split()))
#print(A)
import collections as cl

def count_f(B:list):
	c = cl.Counter(B)
	c_sum = 0
	#print(c.keys())
	for i in c.keys():
		if c[i]>1:
			c_sum += c[i]*(c[i]-1)/2
	return print(int(c_sum))
	
B = []
for i in range(1,len(A)+1):
	B = A[:i-1]+A[i:]
	#print(B)
	#print(list_B)
	count_f(B)
	B = []

### FIXED CODE ###

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

import collections as cl
c_A = cl.Counter(A)
sum_c_A=0
for i in c_A.keys():
	if c_A[i]>1:
		sum_c_A += c_A[i]*(c_A[i]-1)/2

for j in A:
	print(int(sum_c_A-c_A[j]+1))
### BUGGY CODE ###


from operator import itemgetter

n,m=map(int,input().split())
s = [ list(map(int,input().split())) for _ in range(m)]
l = sorted(s,key=itemgetter(0,1))
j=1
for i in range(0,len(l)):
    if i !=0 and l[i][0] != l[i-1][0]:
        j = 1
    l[i].append(('%06d' % l[i][0]) + ('%06d' % j))
    j = j + 1
for i in range(0,len(s)):
    for j in range(0,len(l)):
        if s[i][0] == l[j][0] and s[i][1] == l[j][1]:
            print(l[j][2])
            break

### FIXED CODE ###

from operator import itemgetter

n,m=map(int,input().split())
s = [ list(map(int,input().split())) for _ in range(m)]
l = sorted(s,key=itemgetter(0,1))
j=1
res = {}
for i in range(0,len(l)):
    if i !=0 and l[i][0] != l[i-1][0]:
        j = 1
    res[l[i][1]] = ('%06d' % l[i][0]) + ('%06d' % j)
    j = j + 1
for i in range(0,len(s)):
    print(res[s[i][1]])
### BUGGY CODE ###


from bisect import bisect_left

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

d = {"R": [], "G": [], "B": []}
for i in range(N):
    d[S[i]].append(i)

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] == S[j]:
            continue

        # j > k
        res = (set("RGB") - set([S[i], S[j]])).pop()
        k = bisect_left(d[res], j)

        # Find k == 2*j - i
        k0 = bisect_left(d[res], 2 * j - i)
        if k0 < len(d[res]):
            flag = int(d[res][k0] + 1 == 2 * (j + 1) - i - 1)
        else:
            flag = 0

        # Add
        ans += len(d[res]) - k - flag

print(ans)


### FIXED CODE ###

from bisect import bisect_right

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

d = [[0] * N for _ in range(3)]
for i in range(3):
    for j in range(N):
        d[i][j] = int(S[j] == "RGB"[i])
        
cumsum = [[0] * (N + 1) for _ in range(3)]
for i in range(3):
    for j in range(N):
        cumsum[i][j + 1] = cumsum[i][j] + d[i][j]

cnt = [len(v) for v in d]
ans = 0
for i in range(1, N - 1):
    for j in range(i + 1, N):
        
        if S[i - 1] == S[j - 1]:
            continue

        # Find `k` string and index
        s = (set("RGB") - set([S[i - 1], S[j - 1]])).pop()
        idx = "RGB".find(s)
        ans += cumsum[idx][-1] - cumsum[idx][j]
        
        k = 2 * j - i
        if k <= N and d[idx][k - 1]:
            ans -= 1
        
print(ans)