581_E. Kojiro and Furrari
Motorist Kojiro spent 10 years saving up for his favorite car brand, Furrari. Finally Kojiro's dream came true! Kojiro now wants to get to his girlfriend Johanna to show off his car to her.

Kojiro wants to get to his girlfriend, so he will go to her along a coordinate line. For simplicity, we can assume that Kojiro is at the point f of a coordinate line, and Johanna is at point e. Some points of the coordinate line have gas stations. Every gas station fills with only one type of fuel: Regular-92, Premium-95 or Super-98. Thus, each gas station is characterized by a pair of integers ti and xi — the number of the gas type and its position.

One liter of fuel is enough to drive for exactly 1 km (this value does not depend on the type of fuel). Fuels of three types differ only in quality, according to the research, that affects the lifetime of the vehicle motor. A Furrari tank holds exactly s liters of fuel (regardless of the type of fuel). At the moment of departure from point f Kojiro's tank is completely filled with fuel Super-98. At each gas station Kojiro can fill the tank with any amount of fuel, but of course, at no point in time, the amount of fuel in the tank can be more than s liters. Note that the tank can simultaneously have different types of fuel. The car can moves both left and right.

To extend the lifetime of the engine Kojiro seeks primarily to minimize the amount of fuel of type Regular-92. If there are several strategies to go from f to e, using the minimum amount of fuel of type Regular-92, it is necessary to travel so as to minimize the amount of used fuel of type Premium-95.

Write a program that can for the m possible positions of the start fi minimize firstly, the amount of used fuel of type Regular-92 and secondly, the amount of used fuel of type Premium-95.

Input

The first line of the input contains four positive integers e, s, n, m (1 ≤ e, s ≤ 109, 1 ≤ n, m ≤ 2·105) — the coordinate of the point where Johanna is, the capacity of a Furrari tank, the number of gas stations and the number of starting points. 

Next n lines contain two integers each ti, xi (1 ≤ ti ≤ 3, - 109 ≤ xi ≤ 109), representing the type of the i-th gas station (1 represents Regular-92, 2 — Premium-95 and 3 — Super-98) and the position on a coordinate line of the i-th gas station. Gas stations don't necessarily follow in order from left to right.

The last line contains m integers fi ( - 109 ≤ fi < e). Start positions don't necessarily follow in order from left to right.

No point of the coordinate line contains more than one gas station. It is possible that some of points fi or point e coincide with a gas station.

Output

Print exactly m lines. The i-th of them should contain two integers — the minimum amount of gas of type Regular-92 and type Premium-95, if Kojiro starts at point fi. First you need to minimize the first value. If there are multiple ways to do it, you need to also minimize the second value.

If there is no way to get to Johanna from point fi, the i-th line should look like that "-1 -1" (two numbers minus one without the quotes).

Examples

Input

8 4 1 1
2 4
0


Output

0 4


Input

9 3 2 3
2 3
1 6
-1 0 1


Output

-1 -1
3 3
3 2


Input

20 9 2 4
1 5
2 10
-1 0 1 2


Output

-1 -1
-1 -1
-1 -1
-1 -1
```python
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
e,s,n,m=map(int,input().split())
fuel1=[]
fuel2=[]
fuel3=[]
keymoments=[]
for i in range(n):
  t,x=map(int,input().split())
  if t==1:
    fuel1.append(x)
  if t==2:
    fuel2.append(x)
  if t==3:
    fuel3.append(x)
  keymoments.append(x)
  keymoments.append(x+s)
fuel1.sort()
fuel2.sort()
fuel3.sort()
keymoments.sort()
pointer1=-1
pointer2=-1
pointer3=-1
last1=-10**9-1
last2=-10**9-1
last3=-10**9-1
keymoments2=[]
lastmoment=-10**9-1
for moment in keymoments:
  if moment==lastmoment:
    continue
  lastmoment=moment
  while pointer1+1<len(fuel1) and fuel1[pointer1+1]<=moment:
    last1=fuel1[pointer1+1]
    pointer1+=1
    
  while pointer2+1<len(fuel2) and fuel2[pointer2+1]<=moment:
    last2=fuel2[pointer2+1]
    pointer2+=1
  while pointer3+1<len(fuel3) and fuel3[pointer3+1]<=moment:
    last3=fuel3[pointer3+1]
    pointer3+=1
  if pointer3!=-1 and moment<s+last3:
    keymoments2.append([moment,3])
  elif pointer2!=-1 and moment<s+last2:
    keymoments2.append([moment,2])
  elif pointer1!=-1 and moment<s+last1:
    keymoments2.append([moment,1])
  else:
    keymoments2.append([moment,-1])
keymoments3=[]
start=10**9
for i in range(len(keymoments2)-1,-1,-1):
  if e>keymoments2[i][0]:
    start=i
    break
if not start==10**9:
  fuel1use=0
  fuel2use=0
  if keymoments2[start][1]==1:
    fuel1use+=e-keymoments2[start][0]
  elif keymoments2[start][1]==2:
    fuel2use+=e-keymoments2[start][0]
  elif keymoments2[start][1]==-1:
    fuel1use=-1
    fuel2use=-1
  moment=keymoments2[start][0]
  keymoments3.append([moment,fuel1use,fuel2use])
  for i in range(start-1,-1,-1):
    moment=keymoments2[i][0]
    if fuel1use==-1:
      keymoments3.append([moment,-1,-1])
      continue
    time=keymoments2[i+1][0]-moment
    if time>s:
      fuel1use=-1
      fuel2use=-1
      keymoments3.append([moment,-1,-1])
      continue
    if keymoments2[i][1]==1:
      fuel1use+=time
    elif keymoments2[i][1]==2:
      fuel2use+=time
    elif keymoments2[i][1]==-1:
      fuel1use=-1
      fuel2use=-1
    keymoments3.append([moment,fuel1use,fuel2use])
  keymoments3.reverse()
f=list(map(int,input().split()))
for i in range(m):
  if f[i]+s>=e:
    print(0,0)
    continue
  if not keymoments3:
    print(-1,-1)
    continue
  if f[i]+s<keymoments3[0][0]:
    print(-1,-1)
    continue
  l=0
  r=len(keymoments3)-1
  while l<r:
    if l+1==r:
      try1=r
    else:
      try1=(l+r)//2
    if f[i]+s>=keymoments2[try1][0]:
      l=try1
    else:
      if l+1==r:
        l=l
        break
      r=try1
  ans1=keymoments3[l][1]
  ans2=keymoments3[l][2]
  if ans1!=-1 and keymoments2[l][1]==1:
    ans1+=keymoments3[l][0]-(f[i]+s)
  elif ans2!=-1 and keymoments2[l][1]==2:
    ans2+=keymoments3[l][0]-(f[i]+s)

  print(ans1,ans2)
  
		  		 				  	 	 	 	 			 	 	  	
```