812_D. Sagheer and Kindergarten_17253
Sagheer is working at a kindergarten. There are n children and m different toys. These children use well-defined protocols for playing with the toys:

  * Each child has a lovely set of toys that he loves to play with. He requests the toys one after another at distinct moments of time. A child starts playing if and only if he is granted all the toys in his lovely set.
  * If a child starts playing, then sooner or later he gives the toys back. No child keeps the toys forever.
  * Children request toys at distinct moments of time. No two children request a toy at the same time.
  * If a child is granted a toy, he never gives it back until he finishes playing with his lovely set.
  * If a child is not granted a toy, he waits until he is granted this toy. He can't request another toy while waiting.
  * If two children are waiting for the same toy, then the child who requested it first will take the toy first.



Children don't like to play with each other. That's why they never share toys. When a child requests a toy, then granting the toy to this child depends on whether the toy is free or not. If the toy is free, Sagheer will give it to the child. Otherwise, the child has to wait for it and can't request another toy.

Children are smart and can detect if they have to wait forever before they get the toys they want. In such case they start crying. In other words, a crying set is a set of children in which each child is waiting for a toy that is kept by another child in the set.

Now, we have reached a scenario where all the children made all the requests for their lovely sets, except for one child x that still has one last request for his lovely set. Some children are playing while others are waiting for a toy, but no child is crying, and no one has yet finished playing. If the child x is currently waiting for some toy, he makes his last request just after getting that toy. Otherwise, he makes the request right away. When child x will make his last request, how many children will start crying?

You will be given the scenario and q independent queries. Each query will be of the form x y meaning that the last request of the child x is for the toy y. Your task is to help Sagheer find the size of the maximal crying set when child x makes his last request.

Input

The first line contains four integers n, m, k, q (1 ≤ n, m, k, q ≤ 105) — the number of children, toys, scenario requests and queries.

Each of the next k lines contains two integers a, b (1 ≤ a ≤ n and 1 ≤ b ≤ m) — a scenario request meaning child a requests toy b. The requests are given in the order they are made by children.

Each of the next q lines contains two integers x, y (1 ≤ x ≤ n and 1 ≤ y ≤ m) — the request to be added to the scenario meaning child x will request toy y just after getting the toy he is waiting for (if any).

It is guaranteed that the scenario requests are consistent and no child is initially crying. All the scenario requests are distinct and no query coincides with a scenario request.

Output

For each query, print on a single line the number of children who will start crying when child x makes his last request for toy y. Please answer all queries independent of each other.

Examples

Input

3 3 5 1
1 1
2 2
3 3
1 2
2 3
3 1


Output

3


Input

5 4 7 2
1 1
2 2
2 1
5 1
3 3
4 4
4 1
5 3
5 4


Output

0
2

Note

In the first example, child 1 is waiting for toy 2, which child 2 has, while child 2 is waiting for top 3, which child 3 has. When child 3 makes his last request, the toy he requests is held by child 1. Each of the three children is waiting for a toy held by another child and no one is playing, so all the three will start crying.

In the second example, at the beginning, child i is holding toy i for 1 ≤ i ≤ 4. Children 1 and 3 have completed their lovely sets. After they finish playing, toy 3 will be free while toy 1 will be taken by child 2 who has just completed his lovely set. After he finishes, toys 1 and 2 will be free and child 5 will take toy 1. Now:

  * In the first query, child 5 will take toy 3 and after he finishes playing, child 4 can play.
  * In the second query, child 5 will request toy 4 which is held by child 4. At the same time, child 4 is waiting for toy 1 which is now held by child 5. None of them can play and they will start crying. 
	// Code Author: Rutul Patel
import java.io.*;
	import java.math.BigInteger;
	import java.math.RoundingMode;
	import java.text.DecimalFormat;
	import java.util.*;
	
public class Main {
	
		static double eps=(double)1e-6;
		static long mod=(int)1e9+6;
		static ArrayList<Integer>[] list;
		static int[] size;
		static boolean[] vis;
		static int[] in;
		static int[] outtime;
		static int t=1;
		public static void main(String args[]) throws IOException{
			InputReader sc = new InputReader(System.in);
			OutputStream outputStream = System.out;
			PrintWriter out = new PrintWriter(outputStream);
			//-------------------------------------
			
			int n=sc.nextInt();
			int m=sc.nextInt();
			int k=sc.nextInt();
			int q=sc.nextInt();
			
			int[] last=new int[m+1];
			Arrays.fill(last, -1);
			in=new int[n+1];
			outtime=new int[n+1];
			list=new ArrayList[n+1];
			size=new int[n+1];
			for(int i=0;i<=n;i++)
				list[i]=new ArrayList<>();
			
			boolean[] root=new boolean[n+1];
			Arrays.fill(root,true);
			for(int i=0;i<k;i++)
			{
				int u=sc.nextInt();
				int v=sc.nextInt();
				
				if(last[v]==-1)
				{
					last[v]=u;
				}
				else
				{
					list[last[v]].add(u);
					last[v]=u;
					root[u]=false;
				}
			}
			
			vis=new boolean[n+1];
			
			for(int i=1;i<=n;i++)
			{
				if(root[i])
				{
					dfs(i);
				}
			}
			
			for(int i=0;i<q;i++)
			{
				int x=sc.nextInt();
				int y=sc.nextInt();
						
				if(last[y]==-1)
					out.println(0);
				else
				{
					int z=last[y];
					if(in[x]<=in[z] && outtime[x]>=outtime[z])
					{
						out.println(size[x]);
					}
					else
						out.println(0);
				}
			}
			//-------------------------------------
			out.close();
		}
		
		static void dfs(int curr)
		{
			in[curr]=t++;
			size[curr]=1;
			for(int i=0;i<list[curr].size();i++)
			{
				dfs(list[curr].get(i));
				size[curr]+=size[list[curr].get(i)];
			}
			
			outtime[curr]=t++;
		}
		static class Pair implements Comparable<Pair> {
			int a, b;

			Pair(int a, int b) {
				this.a = a;
				this.b = b;
			}

			public int compareTo(Pair o) {
				// TODO Auto-generated method stub
				if (this.a != o.a)
					return Integer.compare(this.a, o.a);
				else
					return Integer.compare(this.b, o.b);
				//return 0;
			}

			public boolean equals(Object o) {
				if (o instanceof Pair) {
					Pair p = (Pair) o;
					return p.a == a && p.b == b;
				}
				return false;
			}

			public int hashCode() {
				return new Integer(a).hashCode() * 31 + new Integer(b).hashCode();
			}

			public String toString() {
				return a + " " + b;
			}
		}
		
		static int[] sieve(int n,int[] arr)
		{
			for(int i=2;i*i<=n;i++)
			{
				if(arr[i]==0)
				{
					for(int j=i*2;j<=n;j+=i)
						arr[j]=1;
				}
			}
			return arr;
		}
		
		static boolean isPal(String s)
		{
			for(int i=0, j=s.length()-1;i<=j;i++,j--)
			{
				if(s.charAt(i)!=s.charAt(j)) return false;
			}
			return true;
		}
		public static String rev(String s)
		{
			StringBuilder sb=new StringBuilder(s);
			sb.reverse();
			return sb.toString();
		}
		    
		static long lcm(long a, long b)
		{
		    return a * (b / gcd(a, b));
		}
		
		static long gcd(long a, long b)
		{
		    while (b > 0)
		    {
		        long temp = b;
		        b = a % b; // % is remainder
		        a = temp;
		    }
		    return a;
		}
		static long modulo(long a,long b,long c) {
			long x=1;
			long y=a;
			while(b > 0){
				if(b%2 == 1){
					x=(x*y)%c;
				}
				y = (y*y)%c; // squaring the base
				b /= 2;
			}
			return  x%c;
		}
		public static void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
		
		static long sort(int a[]) {
			int n = a.length;
			int b[] = new int[n];
			return mergeSort(a, b, 0, n - 1);
		}

		static long mergeSort(int a[], int b[], long left, long right) {
			long c = 0;
			if (left < right) {
				long mid = left + (right - left) / 2;
				c = mergeSort(a, b, left, mid);
				c += mergeSort(a, b, mid + 1, right);
				c += merge(a, b, left, mid + 1, right);
			}
			return c;
		}

		static long merge(int a[], int b[], long left, long mid, long right) {
			long c = 0;
			int i = (int) left;
			int j = (int) mid;
			int k = (int) left;
			while (i <= (int) mid - 1 && j <= (int) right) {
				if (a[i] <= a[j]) {
					b[k++] = a[i++];
				} else {
					b[k++] = a[j++];
					c += mid - i;
				}
			}
			while (i <= (int) mid - 1)
				b[k++] = a[i++];
			while (j <= (int) right)
				b[k++] = a[j++];
			for (i = (int) left; i <= (int) right; i++)
				a[i] = b[i];
			return c;
		}  
		
	
		static class InputReader {
    		public BufferedReader reader;
    		public StringTokenizer tokenizer;
     
    		public InputReader(InputStream inputstream) {
    			reader = new BufferedReader(new InputStreamReader(inputstream));
    			tokenizer = null;
    		}
     
    		public String nextLine(){
    			String fullLine=null;
    			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
    				try {
    					fullLine=reader.readLine();
    				} catch (IOException e) {
    					throw new RuntimeException(e);
    				}
    				return fullLine;
    			}
    			return fullLine;
    		}
    		public String next() {
    			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
    				try {
    					tokenizer = new StringTokenizer(reader.readLine());
    				} catch (IOException e) {
    					throw new RuntimeException(e);
    				}
    			}
    			return tokenizer.nextToken();
    		}
    		public long nextLong() {
    			return Long.parseLong(next());
    		}
    		public int nextInt() {
    			return Integer.parseInt(next());
    		}
    	}
    	
    }