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

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9

    bit = dict()
    pow_list = dict()
    for j in range(60): 
        bit[j] = 0
        pow_list[j] = pow(2, j, mod)

    first = A[0]
    for j in range(60):
        bit[j] = first % 2
        first //= 2
    
    ans = 0
    for i in range(1, N):
        num = A[i]
        for j in range(60):
            if num % 2 == 1:
                ans += (i - bit[j]) * pow_list[j]
                ans %= mod
            else:
                ans += bit[j] * pow_list[j]
                ans %= mod
            bit[j] += (num % 2)
            num //=2
            
    print(ans)

    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9

    bit = dict()
    pow_list = dict()
    for j in range(60): 
        bit[j] = 0
        pow_list[j] = pow(2, j, mod)

    first = A[0]
    for j in range(60):
        bit[j] = first % 2
        first //= 2
    
    ans = 0
    for i in range(1, N):
        num = A[i]
        for j in range(60):
            if num % 2 == 1:
                ans += (i - bit[j]) * pow_list[j]
                ans %= mod
            else:
                ans += bit[j] * pow_list[j]
                ans %= mod
            bit[j] += (num % 2)
            num //=2
            
    print(ans)

    return 0

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

n=int(input())
s=list(input())
ans=s.count('R')*s.count('G')*s.count('B')
for i in range(n):
  if s[i] =="R":
    s[i]=1
  elif s[i] =="G":
    s[i]=2
  elif s[i] =="B":
    s[i]=4
for i in range(n):
  for j in range(i+1,n):

    k=2*j-i
    if k>= n:
      continue
    if int(s[i])+int(s[j])+int(s[k])==7:
      ans -=1
print (ans)

### FIXED CODE ###

n=int(input())
s=list(input())
ans=s.count('R')*s.count('G')*s.count('B')
for i in range(n):
  if s[i] =="R":
    s[i]=1
  elif s[i] =="G":
    s[i]=2
  elif s[i] =="B":
    s[i]=4
for i in range(n):
  for j in range(i+1,n):

    k=2*j-i
    if k>= n:
      continue
    if s[i]+s[j]+s[k]==7:
      ans -=1
print (ans)
### BUGGY CODE ###

n = int(input())
v = list(map(int, input().split()))
ev = []
od = []
for i in range(n):
    if i % 2 == 0:
        ev.append(v[i])
    else:
        od.append(v[i])
ev.sort()
od.sort()
m = 0
oo = [[0, 0]]
ii = [[0, 0]]
while True:
    oo.append([ev[m], ev.count(ev[m])])
    m += ev.count(ev[m])
    if m >= n//2:
        break
m = 0
while True:
    ii.append([od[m], od.count(od[m])])
    m += od.count(od[m])
    if m >= n//2:
        break
ii.sort(key=lambda x: x[1], reverse=True)
oo.sort(key=lambda x: x[1], reverse=True)
if ii[0][0] != oo[0][0]:
    print(n - oo[0][1] - ii[0][1])
else:
    print(min(n - oo[1][1] - ii[0][1], n - oo[0][1] - ii[1][1]))

### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
ev = [0]*(max(v)+1)
od = [0]*(max(v)+1)
for i in range(n):
    if i % 2 == 0:
        ev[v[i]-1] += 1
    else:
        od[v[i] - 1] += 1
e = sorted(ev)
o = sorted(od)
if ev.index(e[-1]) == od.index(o[-1]) and e[-2] != e[-1] and o[-2] != o[-1]:
    print(n-max(e[-1]+o[-2], e[-2]+o[-1]))
else:
    print(n-e[-1]-o[-1])
### BUGGY CODE ###

s = input()

n = int(input())
l = []

base = 1

for i in range(n):
  l=list(input().split())
  if l[0] == '1':
    base = base *-1
  else:
    if l[1] =='1' and base == 1 :
      s = l[2]+s
    elif l[1] =='2' and base == 1 :
      s = s+l[2]
    elif l[1] =='1' and base == -1 :
      s = s+l[2]
    elif l[1] =='2' and base == -1 :
      s = l[2]+s

if base ==-1:
  s=''.join(list(reversed(s)))
      
print(s)  

### FIXED CODE ###

from collections import deque
s = deque(input())

n = int(input())
l = []

base = 1

for i in range(n):
  l=list(input().split())
  if l[0] == '1':
    base = base *-1
  else:
    if l[1] =='1' and base == 1 :
      s.appendleft(l[2])
    elif l[1] =='2' and base == 1 :
      s.append(l[2])
    elif l[1] =='1' and base == -1 :
      s.append(l[2])
    elif l[1] =='2' and base == -1 :
      s.appendleft(l[2])

if base ==-1:
  s=''.join(list(reversed(s)))
      
print("".join(s))
### BUGGY CODE ###

p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    tmp = pow(b[-1], p - 2, p)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * tmp % p
        res[i] = t
        for j in range(m):
            a[i + j] = (a[i + j] - t * b[j]) % p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] = -f[j - 1] * i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for j in range(len(fm)):
            r += fm[j] * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t % p
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))


### FIXED CODE ###

p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    tmp = pow(b[-1], p - 2, p)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * tmp % p
        res[i] = t
        for j in range(m):
            a[i + j] = (a[i + j] - t * b[j]) % p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] = -f[j - 1] * i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for v in fm:
            r += v * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))
### BUGGY CODE ###

# -*- coding:utf-8 -*-
# /usr/bin/python3


def main():
  n, m = map(int, input().strip().split(' '))
  liAB = sorted([tuple(map(int, input().strip().split(' '))) for _ in range(n)], key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      top.sort()
      if len(top) > a-k:
        s += sum(top[-(a-k):])
        del top[-(a-k):]
      else:
        s += sum(top)
        top = []
      k = a

    top.append(b)


  top.sort()
  s += sum(top[-(m-k+1):])
  print(s)

if __name__=='__main__':
  main()


### FIXED CODE ###

# -*- coding:utf-8 -*-
# /usr/bin/python3

from heapq import heappush, heappop

def main():
  n, m = map(int, input().strip().split(' '))
  liAB = [tuple(map(int, input().strip().split(' '))) for _ in range(n)]
  liAB.sort(key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      s += (-sum([heappop(top) for _ in range(a-k) if len(top) != 0]))
      k = a
    heappush(top, -b)

  s += (-sum([heappop(top) for _ in range(m-k+1) if len(top) != 0]))
  print(s)

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

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

ans = 1


if all([i > 0 for i in a]):
  for i in range(n):
    ans *= a[i]

  if ans > 10 ** 18:
    print(-1)
  else:
    print(ans)

else:
  print(0)



### FIXED CODE ###

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

ans = 1

if all([i > 0 for i in a]):
  for i in range(n):
    ans *= a[i]
    if ans > 10 ** 18:
      ans = -1
      break

  print(ans)

else:
  print(0)
### BUGGY CODE ###

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

while (len(a)>1):
    b=fractions.gcd(a[0],a[1])
    del a[1]
    del a[0]
    a.append(b)
print(a[0])

### FIXED CODE ###

import fractions
n=int(input())
a=list(map(int,input().split()))
tmp=a[0]
for i in range(1,n):
    tmp=fractions.gcd(a[i],tmp)
print(tmp)
### BUGGY CODE ###

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

for i in range(M, 0, -1):
  if M % i == 0 and M >= i * N:
    print(i)
    exit()

### FIXED CODE ###

N, M = list(map(int, input().split()))
# 範囲を絞る時は，反対の値も見るべき(M/iのこと)
print(max([j for i in range(int(M**0.5), 0, -1) for j in [i, int(M/i)] if M % j == 0 and M / N >= j]))
### BUGGY CODE ###

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

x = int(input())
num = [i for i in range(2, 100010)]
#print(num)

np_x = np.array(num)

for i in range(2, 100010):
    b = np.logical_or(np_x == i, np_x%i != 0)
    np_x = np_x[b]
#print(np_x)

ans = np_x[np_x >= x]
#print(ans)
print(ans[0])




### FIXED CODE ###

# -*- coding:utf-8 -*-
import math

def is_prime(N):
    if N == 1:
        return False
    for k in range(2, int(math.sqrt(N))+1):
        if N%k == 0:
            return False
    return True

X = int(input())

while True:
    if is_prime(X):
        print(X)
        exit()
    X += 1
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if (z>=0)&(z<=K):
            count += 1
print(count)
### BUGGY CODE ###

# /usr/bin/python3
# -*- coding: utf-8 -*-


if __name__ == '__main__':
    input()
    S = input()
    cnt = 0
    last = len(S)
    # tmp = [num for num in set(S)]
    # ans_set = [t1+t2+t3 for t1 in tmp for t2 in tmp for t3 in tmp]
    for num in range(1000):
        # f = str(num // 100)
        # s = str((num % 100) // 10)
        # t = str(num % 10)
        f = str(num // 100)
        s = str((num-int(f)*100) // 10)
        t = str((num-int(f)*100-int(s)*10))
        # ans = [str(num // 100), str((num % 100) // 10), str(num % 10)]
    # for ans in ans_set:
        fidx = -1
        sidx = -1
        tidx = -1
        idx = 0
        for i in range(last):
            # if idx >= 3:
            #     cnt += 1
            #     break
            # if S[i] == ans[idx]:
            #     idx += 1

            # if fidx < 0:
            #     if S[i] == ans[0]:
            #         fidx = i
            #     continue
            # if sidx < 0:
            #     if S[i] == ans[1]:
            #         sidx = i
            #     continue
            # if tidx < 0:
            #     if S[i] == ans[2]:
            #         cnt += 1
            #         break

            if fidx < 0:
                if S[i] == f:
                    fidx = i
                continue
            if sidx < 0:
                if S[i] == s:
                    sidx = i
                continue
            if tidx < 0:
                if S[i] == t:
                    cnt += 1
                    break
    # 出力
    print(cnt)


### FIXED CODE ###

import copy
import math
import time
 
# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():
 
    idx += 1
'''
 
def main():
    start = time.time()
 
    n = get_int()
    s_list = get_string_char_list()
    s_list = [int(x) for x in s_list]
 
    #n = 30000
    #s_list = [1] * 30000
 
    #ans_set = set([])
 
    #for i in range(0,n):
    #    for ii in range(i+1, n):
    #        for iii in range(ii+1, n):
    #            ans_set.add(int(s_list[i]) * 100 + int(s_list[ii]) * 10 + int(s_list[iii]) * 1)
 
    #print(len(ans_set))
 
    ans = 0
 
    for i in range(0, 1000):
        a = i // 100
        b = (i % 100) // 10
        c = i % 10
 
        find_a = False
        find_b = False
        for ii in s_list:
 
            if (find_a == False) and (ii == a):
                find_a = True
            elif (find_a == True) and (find_b == False) and (ii == b):
                find_b = True
            elif (find_b == True) and (ii == c):
 
                ans += 1
                break
    print(ans)
 
    #print(time.time() - start)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

H,W,M=map(int,input().split())
mine=[list(map(int,input().split()))for i in range(M)]
mine_h=[0]*H
mine_w=[0]*W
ans=0
val=-1
for i in range(M):
    mine_h[mine[i][0]-1]+=1
    mine_w[mine[i][1]-1]+=1
max_h=max(mine_h)
max_w=max(mine_w)
h_index=[i+1 for i, x in enumerate(mine_h)if x == max_h]
w_index=[i+1 for i, x in enumerate(mine_w)if x == max_w]
for i in h_index:
    for j in w_index:
        if [i,j] in mine:
            continue
        else:
            val=0
            break
print(max_h+max_w+val)

### FIXED CODE ###

H,W,M=map(int,input().split())
mine_h=[0]*H
mine_w=[0]*W
val=-1
mine=set()
for i in range(M):
    a,b=map(int,input().split())
    mine_h[a-1]+=1
    mine_w[b-1]+=1
    mine.add((a,b))
max_h=max(mine_h)
max_w=max(mine_w)
h_index=[i+1 for i, x in enumerate(mine_h)if x == max_h]
w_index=[i+1 for i, x in enumerate(mine_w)if x == max_w]
for i in h_index:
    for j in w_index:
        if (i,j) in mine:
            continue
        else:
            val=0
            break
print(max_h+max_w+val)
### BUGGY CODE ###

t=c=0
for _ in[0]*input():
 i=input()
 if i:t+=i 
 else:c+=t/2;t=0
print c+t/2

### FIXED CODE ###

t=c=0
for _ in[0]*input():i=input();c+=(i+t)/2;t=(i+t)%2&(i>0)
print c
### BUGGY CODE ###

n = int(input())
a_l = [ int(input()) for _ in range(n)]

for i in range(n):
    if i == 0:
        l = 0
    else:
        l = max(a_l[:i])

    if i == n-1:
        r = 0
    else:
        r = max(a_l[i+1:])
    print(max([l,r]))

### FIXED CODE ###

n = int(input())
a_l = [ int(input()) for _ in range(n)]

l = []
r = []
l_max = 0
r_max = 0
for i in range(n):
    l_max = max(l_max, a_l[i])
    r_max = max(r_max, a_l[-i-1])
    l.append(l_max)
    r.append(r_max)
for i in range(n):
    if i == 0:
        t_l = 0
    else:
        t_l = l[i-1]
    if i == n-1:
        t_r = 0
    else:
        t_r = r[-i-2]
    print(max([t_l,t_r]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush

def main():
    n,k = map(int, input().split())
    A = list(map(int, input().split()))

    array = [0]*n
    for i in range(k-1,n):
        tmp = 1
        for j in range(k):
            tmp *= A[i-j]
        array[i] = tmp

    for i in range(k-1, n-1):
        if array[i] < array[i+1]:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush

def main():
    n,k = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(k,n):
        if A[i-k]<A[i]:
            print('Yes')
        else:
            print('No')


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 x+y+z==s:
        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):
      if s-x-y <= k and s-x-y>=0:
        ans += 1
        
print(ans)
### BUGGY CODE ###

import itertools

n, m = map(int, input().split())
pair = []
for i in range(m):
	pair.append(list(map(int, input().split())))
ans = []

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(n)
l = []
for i in range(1, n + 1):
	l.append(i)
c = list(itertools.combinations(l, 2))
for i in range(1, m + 1):
	count = 0
	for j in range(len(c)):
		if u.same_check(int(c[j][0]), int(c[j][1])) == False:
			count += 1
	ans.append(count)
	u.union(pair[-i][0], pair[-i][1])

ans.sort()
for i in range(m):
	print(ans[i])

### FIXED CODE ###

n, m = map(int, input().split())
pair = []
for i in range(m):
	pair.append(list(map(int, input().split())))
pair = pair[::-1]
ans = []
ans.append(int(n*(n-1)/2))

class UnionFind:
    def __init__(self, n):
        self.par = [-1] * (n+1)
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def size(self, x):
        return -self.par[self.find(x)]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.size(x) < self.size(y):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        return

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(n)
for i in range(len(pair) - 1):
    if u.find(pair[i][0]) != u.find(pair[i][1]):
        ans.append(max(0, int(ans[i] - u.size(pair[i][0]) * u.size(pair[i][1]))))
    else:
        ans.append(ans[i])
    u.union(pair[i][0], pair[i][1])
ans = ans[::-1]
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

ans = 0
for x in range(1, int(input())):
    ans += x

print(ans)


### FIXED CODE ###

n = int(input())

print(n * (n - 1) // 2)
### BUGGY CODE ###

def gcd(a,b):
    c = a//b
    d = a%b
    if d==0:
        return b
    else:
        return gcd(b,d)


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



max_saidaikouyakusu = 0
for i in range(n):#nums[i]がない時の最大公約数を求める
    saidaikouyakusu = None
    for j in range(n):
        if j== i:continue
        else:
            if saidaikouyakusu==None:
                saidaikouyakusu = nums[j]
            else:
                saidaikouyakusu = gcd(saidaikouyakusu,nums[j])
    if max_saidaikouyakusu < saidaikouyakusu:
        max_saidaikouyakusu=saidaikouyakusu


print(max_saidaikouyakusu)


### FIXED CODE ###

def gcd(a,b):
    a,b=max(a,b),min(a,b)
    if b==0:
        return a
    c = a//b
    d = a%b
    if d==0:
        return b
    else:
        return gcd(b,d)


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


l = [0 for _ in range(n)]
l[0]=0
for i in range(1,n):#nums[i]左側の最大公約数を求める
    l[i]=gcd(l[i-1],nums[i-1])

r=[0 for _ in range(n)]
r[-1]=0
for i in reversed(range(0,n-1)):#nums[i]の右側の最大公約数を求める
    r[i]=(gcd(nums[i+1],r[i+1]))

ans=0
for i in range(n):
    saidaikouyakusu_except_for_ni=gcd(l[i],r[i])
    if ans < saidaikouyakusu_except_for_ni:
        ans = saidaikouyakusu_except_for_ni
    else:pass

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

from collections import defaultdict
    
n, m = map(int, input().split())
adj = defaultdict(list)
radj = defaultdict(list)

for i in range(m):
    s, e = map(int, input().split())
    adj[s].append(e)
    radj[e].append(s)
    
mp = [0]*(n+1)
v = [0]*(n+1)
    
for i in range(1, 1+n):
    if len(adj[i]) == 0:
        q = [i]
        while q:
            e = q.pop()
            for j in radj[e]:
                mp[j] = max(mp[j], 1+mp[e])
                q.append(j)

print(max(mp))

### FIXED CODE ###

import sys
from collections import defaultdict
    
sys.setrecursionlimit(10**9)
    
n, m = map(int, input().split())
adj = defaultdict(list)
radj = defaultdict(list)

for i in range(m):
    s, e = map(int, input().split())
    adj[s].append(e)
    
dp = [-1]*(n+1)

def dfs(e):
    if dp[e] != -1:
        return dp[e]
    
    temp = 0
    for i in adj[e]:
        temp = max(temp, 1+dfs(i))
        
    dp[e] = temp
    return temp
    
    
for i in range(1, n+1):
    dfs(i)
    
print(max(dp))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bit_count(i):

    return bin(i).count('1')

N, M, Q = MAP()

# 出発前の列車の集合
S1 = [(1<<M)-1] * (N+1)
# 終着後の列車の集合
S2 = [0] * (N+1)
for i in range(M):
    l, r = MAP()
    l -= 1; r -= 1
    S1[l+1] ^= 1<<i
    S2[r] |= 1<<i
for i in range(1, N+1):
    S1[i] &= S1[i-1]
    S2[i] ^= S2[i-1]

for i in range(Q):
    p, q = MAP()
    p -= 1; q -= 1
    pq = S1[p] & S2[q]
    print(bit_count(pq))


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc106/editorial.pdf
　　　https://www.hamayanhamayan.com/entry/2018/08/18/234325
・累積和
"""

N, M, Q = map(int, input().split())
lM, rM = [0] * M, [0] * M
pQ, qQ = [0] * Q, [0] * Q
LR = [[0] * N for i in range(N)]
# 都市番号を0-indexed
for i in range(M):
    l, r = map(int, input().split())
    lM[i], rM[i] = l-1, r-1
    LR[l-1][r-1] += 1
for i in range(Q):
    p, q = map(int, input().split())
    pQ[i], qQ[i] = p-1, q-1

# 始点固定で終点を動かした累積和を出す
cnt = [[0] * N for i in range(N)]
for i in range(N):
    cnt[i][i] = LR[i][i]
    for j in range(1, N):
        cnt[i][j] = cnt[i][j-1] + LR[i][j]

for i in range(Q):
    ans = 0
    for j in range(pQ[i], qQ[i]+1):
        # ある終点についてもう和が出てるので、
        # ここでは始点を動かして最終的な合計にする
        ans += cnt[j][qQ[i]]
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 1
for j in range(a[1],1,-1):
  c = list(map(lambda x: x % j,a))
  c_ng = [i for i in c if i > 0]
  #print("j=",j,"c=",c,"c_ng=",c_ng)
  if len(c_ng) <= 1:
    ans = j
    break
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 1
if n == 2:
  print(max(a))
else:
  a0 = a[0]
  a1 = a[1]
  r = 0
  while True:
    r = a1 % a0
    if r == 0:
      b0 = a0
      break
    elif r > a0:
      a1, a0 = r, a0
    else:
      a1, a0 = a0, r
  a1 = a[1]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a1
    if r == 0:
      b1 = a1
      break
    elif r > a1:
      a2, a1 = r, a1
    else:
      a2, a1 = a1, r
  a0 = a[0]
  a2 = a[2]
  r = 0
  while True:
    r = a2 % a0
    if r == 0:
      b2 = a0
      break
    elif r > a0:
      a2, a0 = r, a0
    else:
      a2, a0 = a0, r
  max_a = max(b0,b1,b2)
  kouho = []
  for j in range(max_a,1,-1):
    if max_a % j == 0:
      c = list(map(lambda x: x % j,a))
      c_ng = [i for i in c if i > 0]
    #print("j=",j,"c=",c,"c_ng=",c_ng)
      if len(c_ng) <= 1:
        ans = j
        break
  print(ans)