from sortedcontainers import*
n,a=map(int,input().split())
*x,=map(int,input().split())
xs=sorted((-x[i],i)for i in range(n))
t=int(input())
d=[[]for _ in range(a+2)]
e=[[]for _ in range(a+2)]
for i in range(t):
  l,r=map(int,input().split())
  d[l]+=i+1,
  e[r+1]+=i+1,
s=SortedSet([-1])
ans=[-1]*n
for i in range(a+1):
  b=[]
  while xs and xs[-1][0]==-i:
    b+=xs.pop()[1],
  for j in d[i]:
    s.add(j)
  for j in e[i]:
    s.discard(j)
  for j in b:
    ans[j]=s[-1]
print(*ans,sep='\n')