In Ann's favorite book shop are as many as n books on math and economics. Books are numbered from 1 to n. Each of them contains non-negative number of problems.

Today there is a sale: any subsegment of a segment from l to r can be bought at a fixed price. 

Ann decided that she wants to buy such non-empty subsegment that the sale operates on it and the number of math problems is greater than the number of economics problems exactly by k. Note that k may be positive, negative or zero.

Unfortunately, Ann is not sure on which segment the sale operates, but she has q assumptions. For each of them she wants to know the number of options to buy a subsegment satisfying the condition (because the time she spends on choosing depends on that).

Currently Ann is too busy solving other problems, she asks you for help. For each her assumption determine the number of subsegments of the given segment such that the number of math problems is greaten than the number of economics problems on that subsegment exactly by k.

Input

The first line contains two integers n and k (1 ≤ n ≤ 100 000,  - 109 ≤ k ≤ 109) — the number of books and the needed difference between the number of math problems and the number of economics problems.

The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 2), where ti is 1 if the i-th book is on math or 2 if the i-th is on economics.

The third line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109), where ai is the number of problems in the i-th book.

The fourth line contains a single integer q (1 ≤ q ≤ 100 000) — the number of assumptions.

Each of the next q lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n) describing the i-th Ann's assumption.

Output

Print q lines, in the i-th of them print the number of subsegments for the i-th Ann's assumption.

Examples

Input

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


Output

2
3
4
1


Input

4 0
1 2 1 2
0 0 0 0
1
1 4


Output

10

Note

In the first sample Ann can buy subsegments [1;1], [2;2], [3;3], [2;4] if they fall into the sales segment, because the number of math problems is greater by 1 on them that the number of economics problems. So we should count for each assumption the number of these subsegments that are subsegments of the given segment.

Segments [1;1] and [2;2] are subsegments of [1;2].

Segments [1;1], [2;2] and [3;3] are subsegments of [1;3].

Segments [1;1], [2;2], [3;3], [2;4] are subsegments of [1;4].

Segment [3;3] is subsegment of [3;4].
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        D solver = new D();
        solver.solve(1, in, out);
        out.close();
    }

    static class D {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int k = in.readInt();
            int[] t = IOUtils.readIntArray(in, n);
            int[] a = IOUtils.readIntArray(in, n);
            for (int i = 0; i < a.length; i++) {
                if (t[i] == 2) {
                    a[i] = -a[i];
                }
            }
            long[] balance = new long[a.length + 1];
            for (int i = 0; i < a.length; i++) {
                balance[i + 1] = a[i];
                balance[i + 1] += balance[i];
            }
            HashMap<Long, Integer> allValues = new HashMap<>();
            for (long bal : balance) {
                for (long value : new long[]{bal, bal - k, bal + k}) {
                    if (!allValues.containsKey(value)) allValues.put(value, allValues.size());
                }
            }
            int[][] toIndex = new int[balance.length][];
            for (int idx = 0; idx < toIndex.length; idx++) {
                toIndex[idx] = new int[]{allValues.get(balance[idx]), allValues.get(balance[idx] - k), allValues.get(balance[idx] + k)};
            }
            int numQueries = in.readInt();
            Query[] queries = new Query[numQueries];
            for (int i = 0; i < queries.length; i++) {
                queries[i] = new Query(in.readInt() - 1, in.readInt(), i);
            }
            int blockSize = (int) Math.sqrt(n); // TODO confirm optimality
            for (Query query : queries) {
                query.block = query.left / blockSize;
            }
            Arrays.sort(queries, new Comparator<Query>() {

                public int compare(Query o1, Query o2) {
                    if (o1.block != o2.block) {
                        return Integer.compare(o1.block, o2.block);
                    }
                    return o1.block % 2 == 0 ? Integer.compare(o1.right, o2.right) : -Integer.compare(o1.right, o2.right);
                }
            });
            int left = 0, right = -1;
            long currentCount = 0;
            int[] counts = new int[allValues.size()];
            for (Query query : queries) {
                while (right < query.right) {
                    // need to add the element at right + 1
                    currentCount += counts[toIndex[right + 1][1]];
                    counts[toIndex[right + 1][0]]++;
                    right++;
                }
                while (right > query.right) {
                    // need to remove the element at right
                    counts[toIndex[right][0]]--;
                    currentCount -= counts[toIndex[right][1]];
                    right--;
                }
                while (left < query.left) {
                    // need to remove element at left
                    counts[toIndex[left][0]]--;
                    currentCount -= counts[toIndex[left][2]];
                    left++;
                }
                while (left > query.left) {
                    // need to add left - 1
                    currentCount += counts[toIndex[left - 1][2]];
                    counts[toIndex[left - 1][0]]++;
                    left--;
                }
                query.ans = currentCount;
            }
            Arrays.sort(queries, new Comparator<Query>() {

                public int compare(Query o1, Query o2) {
                    return Integer.compare(o1.idx, o2.idx);
                }
            });
            for (Query query : queries) {
                out.printLine(query.ans);
            }
        }

        class Query {
            int left;
            int right;
            int idx;
            int block;
            long ans;

            public Query(int left, int right, int idx) {
                this.left = left;
                this.right = right;
                this.idx = idx;
            }

        }

    }

    static class IOUtils {
        public static int[] readIntArray(InputReader in, int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++) {
                array[i] = in.readInt();
            }
            return array;
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(long i) {
            writer.println(i);
        }

    }
}

