A club wants to take its members camping. In order to organize the event better the club directors decided to partition the members into several groups. 

Club member i has a responsibility value ri and an age value ai. A group is a non-empty subset of club members with one member known as group leader. A group leader should be one of the most responsible members of the group (his responsibility value is not less than responsibility of any other group member) and his age absolute difference with any other group member should not exceed k. 

Some club members are friends and want to be in the same group. They also like their group to be as large as possible. Now you should write a program that answers a series of questions like "What's the largest size of a group containing club member x and club member y?". It's possible for x or y to be the group leader.

Input

The first line contains two integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ 109) — the number of club members and the age restriction for one group. 

The next line contains integer numbers r1, r2, ..., rn (1 ≤ ri ≤ 109) separated by space: ri denotes the i-th club member's responsibility. In the same way there are integers a1, a2, ..., an (1 ≤ ai ≤ 109) in the third line: ai denotes the i-th club member's age.

The next line contains an integer q denoting the number of questions that you should answer (1 ≤ q ≤ 105). The next q lines describe the questions. Each line contains two space-separated integers xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi) — the indices of the club members that should end up in the same group. 

Output

For each question print the maximum size of the group in a line. If making such a group is impossible print -1 instead.

Examples

Input

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


Output

4
3
-1
4

Note

In the first query the largest group with members 3 and 5 is {1, 3, 4, 5} where member 3 is the leader.

In the second query member 2 should be the leader so the group will be {1, 2, 3}.

In the third query the leader of the group should have age 3 so the only leader can be member 3, who is less responsible than member 2. So making a group is impossible.

The group for the fourth query is the same as first query.
import java.util.*;
import java.io.*;

public class CampingGroups {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out, false);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        final int[] resp = new int[n];
        TreeSet<Integer> set = new TreeSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i <n; i++) {
            resp[i] = scanner.nextInt();
            set.add(resp[i]);
        }
        int cnt = 0;
        for(int vv: set) {
            map.put(vv, cnt++);
        }
        int[] age = new int[n];
        int[] ageind = new int[n];
        for(int i = 0; i < n; i++) {
            resp[i] = map.get(resp[i]);
        }
        map.clear();
        set.clear();
        cnt = 0;
        for(int i = 0; i < n; i++) {
            age[i] = scanner.nextInt();
            set.add(age[i]);
            set.add(age[i] + k);
            set.add(age[i] - k);
        }
        for(int vv: set) {
            map.put(vv, cnt++);
        }
        for(int i = 0; i < n; i++) {
            ageind[i] = map.get(age[i]);
        }
        Tuple[] tups = new Tuple[n];
        for(int i = 0; i <n; i++) {
            tups[i] = new Tuple(ageind[i], resp[i], i);
        }
        Arrays.sort(tups);
        BIT bit = new BIT(cnt + 1);
        int[] grpsz = new int[n];
        int index = 0;
        for(Tuple tup: tups) {
            while(index < n && tups[index].resp <= tup.resp) {
                bit.update(tups[index].age + 1, 1);
                index++;
            }
            grpsz[tup.ind] = bit.range(map.get(age[tup.ind]-k) + 1,map.get(age[tup.ind] + k) + 1);
        }
        bit = null;
        int q = scanner.nextInt();
        Pair[] qq = new Pair[q];
        for(int i = 0; i < q; i++) {
            int x = scanner.nextInt()-1;
            int y = scanner.nextInt()-1;
            if (resp[x] < resp[y]) {
                int t = x;
                x = y;
                y = t;
            }
            qq[i] = new Pair(x,y,i);
        }
        //want to sort by the larger of the two go in decreasing order
        //we can then query the range of permissable ages
        int size = map.size();
        Arrays.sort(qq, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return resp[o1.a] - resp[o2.a];
            }
        });
        SegTree sg = new SegTree(size, 0, size-1);
        sg.update(1,0,size-1,-1);
        //each need to update all with resp >= current one
        int curtuple = n-1;
        int[] ans = new int[q];
        for(int i = q-1; i>= 0; i--) {
            //update the segment tree
            while(curtuple >= 0 && tups[curtuple].resp >= resp[qq[i].a]) {
                int cur = sg.max(1, tups[curtuple].age, tups[curtuple].age);
                if (grpsz[tups[curtuple].ind] > cur) sg.update(1, tups[curtuple].age, tups[curtuple].age, grpsz[tups[curtuple].ind]-cur);
                curtuple--;
            }
            //figure out the working age range
            int lower = Math.min(age[qq[i].a], age[qq[i].b]);
            int upper = Math.max(age[qq[i].a], age[qq[i].b]);
            lower += k;
            upper -= k;
            if (lower < upper) {
                ans[qq[i].ind] = -1;
            }
            else {
                ans[qq[i].ind] = sg.max(1, map.get(upper), map.get(lower));
            }
        }
        for(int aa: ans) {
            out.println(aa);
        }
        out.flush();
    }
    static class SegTree {
        int[] hi, lo, max, delta;
        public SegTree(int ss, int l, int r) {
            hi = new int[4 * ss + 1];
            lo = new int[4 * ss + 1];
            max = new int[4 * ss + 1];
            delta = new int[4 * ss + 1];
            init(1, l, r);
        }
        public void init(int cur, int l, int r) {
            hi[cur] = r;
            lo[cur] = l;
            if (r == l) return;
            int mid = (l + r)/2;
            init(cur*2, l, mid);
            init(cur*2+1, mid + 1, r);
        }
        void prop(int cur) {
            delta[cur*2] += delta[cur];
            delta[cur*2+1] += delta[cur];
            delta[cur] = 0;
        }
        void update(int cur) {
            max[cur] = Math.max(max[cur*2] + delta[cur*2], max[cur*2+1] + delta[cur*2+1]);
        }
        void update(int cur, int l, int r, int amt) {
            if (l > hi[cur] || lo[cur] > r) { return; }
            if (l <= lo[cur] && r>=hi[cur]){
                delta[cur] += amt;
                return;
            }
            prop(cur);
            update(cur*2, l, r, amt);
            update(cur*2 + 1, l, r, amt);
            update(cur);
        }
        int max(int cur, int l, int r) {
            if (l > hi[cur] || lo[cur] > r) { return -1; }
            if (l <= lo[cur] && r>=hi[cur]){
                return max[cur] + delta[cur];
            }
            prop(cur);
            int left = max(cur*2, l, r);
            int right = max(cur*2 + 1, l, r);
            update(cur);
            return Math.max(right, left);
        }
    }
    static class Pair {
        int a, b,ind;
        public Pair(int aa, int bb,int ii) {
            a = aa; b = bb;ind = ii;
        }
    }
    static class Tuple implements Comparable<Tuple> {
        int age, resp, ind;
        public Tuple(int aa, int rr, int ii) {
            age = aa; resp = rr; ind = ii;
        }
        public int compareTo(Tuple o) {
            return resp - o.resp;
        }
    }
    static class BIT {
        int[] table;
        int sz;
        public BIT(int ss) {
            sz = ss;
            table = new int[ss];
        }
        void update(int loc, int amt) {
            while(loc < sz) {
                table[loc] += amt;
                loc += loc & - loc;
            }
        }
        int pref(int loc) {
            int ret = 0;
            while(loc > 0) {
                ret += table[loc];
                loc -= loc & - loc;
            }
            return ret;
        }
        int range(int l, int r) {
            return pref(r) - pref(l-1);
        }
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
