Ilya is sitting in a waiting area of Metropolis airport and is bored of looking at time table that shows again and again that his plane is delayed. So he took out a sheet of paper and decided to solve some problems.

First Ilya has drawn a grid of size n × n and marked n squares on it, such that no two marked squares share the same row or the same column. He calls a rectangle on a grid with sides parallel to grid sides beautiful if exactly two of its corner squares are marked. There are exactly n·(n - 1) / 2 beautiful rectangles.

Ilya has chosen q query rectangles on a grid with sides parallel to grid sides (not necessarily beautiful ones), and for each of those rectangles he wants to find its beauty degree. Beauty degree of a rectangle is the number of beautiful rectangles that share at least one square with the given one.

Now Ilya thinks that he might not have enough time to solve the problem till the departure of his flight. You are given the description of marked cells and the query rectangles, help Ilya find the beauty degree of each of the query rectangles.

Input

The first line of input contains two integers n and q (2 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the size of the grid and the number of query rectangles.

The second line contains n integers p1, p2, ..., pn, separated by spaces (1 ≤ pi ≤ n, all pi are different), they specify grid squares marked by Ilya: in column i he has marked a square at row pi, rows are numbered from 1 to n, bottom to top, columns are numbered from 1 to n, left to right.

The following q lines describe query rectangles. Each rectangle is described by four integers: l, d, r, u (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ u ≤ n), here l and r are the leftmost and the rightmost columns of the rectangle, d and u the bottommost and the topmost rows of the rectangle.

Output

For each query rectangle output its beauty degree on a separate line.

Examples

Input

2 3
1 2
1 1 1 1
1 1 1 2
1 1 2 2


Output

1
1
1


Input

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


Output

3
5

Note

The first sample test has one beautiful rectangle that occupies the whole grid, therefore the answer to any query is 1.

In the second sample test the first query rectangle intersects 3 beautiful rectangles, as shown on the picture below:

<image> <image> <image>

There are 5 beautiful rectangles that intersect the second query rectangle, as shown on the following picture:

<image> <image> <image> <image> <image>
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.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Egor Kulikov (egor@egork.net)
 */
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);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int q = in.readInt();
            int[] p = IOUtils.readIntArray(in, n);
            int[] l = new int[q];
            int[] d = new int[q];
            int[] r = new int[q];
            int[] u = new int[q];
            IOUtils.readIntArrays(in, l, d, r, u);
            MiscUtils.decreaseByOne(l, d);
            int[] firstL = ArrayUtils.createArray(n + 1, -1);
            int[] nextL = new int[q];
            int[] firstR = ArrayUtils.createArray(n + 1, -1);
            int[] nextR = new int[q];
            for (int i = 0; i < q; i++) {
                nextL[i] = firstL[l[i]];
                firstL[l[i]] = i;
                nextR[i] = firstR[r[i]];
                firstR[r[i]] = i;
            }
            FenwickTree tree = new FenwickTree(n + 1);
            long[][] values = new long[q][9];
            for (int i = 0; i <= n; i++) {
                for (int j = firstL[i]; j != -1; j = nextL[j]) {
                    values[j][0] = tree.get(1, d[j]);
                    values[j][3] = tree.get(d[j] + 1, u[j]);
                    values[j][6] = tree.get(u[j] + 1, n);
                }
                for (int j = firstR[i]; j != -1; j = nextR[j]) {
                    values[j][1] = tree.get(1, d[j]) - values[j][0];
                    values[j][4] = tree.get(d[j] + 1, u[j]) - values[j][3];
                    values[j][7] = tree.get(u[j] + 1, n) - values[j][6];
                }
                if (i < n) {
                    tree.add(p[i], 1);
                }
            }
            for (int i = 0; i < q; i++) {
                values[i][2] = tree.get(1, d[i]) - values[i][0] - values[i][1];
                values[i][5] = tree.get(d[i] + 1, u[i]) - values[i][3] - values[i][4];
                values[i][8] = tree.get(u[i] + 1, n) - values[i][6] - values[i][7];
                long aa = values[i][0];
                long bb = values[i][1];
                long cc = values[i][2];
                long dd = values[i][3];
                long ee = values[i][4];
                long ff = values[i][5];
                long gg = values[i][6];
                long hh = values[i][7];
                long ii = values[i][8];
                out.printLine(aa * (ee + ff + hh + ii) + bb * (dd + ee + ff + gg + hh + ii) + cc * (dd + ee + gg + hh) +
                        dd * (ee + ff + hh + ii) + ee * (ff + gg + hh + ii) + ff * (gg + hh) + ee * (ee - 1) / 2);
            }
        }

    }

    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 FenwickTree {
        private final long[] value;

        public FenwickTree(int size) {
            value = new long[size];
        }

        public long get(int from, int to) {
            if (from > to) {
                return 0;
            }
            return get(to) - get(from - 1);
        }

        private long get(int to) {
            to = Math.min(to, value.length - 1);
            long result = 0;
            while (to >= 0) {
                result += value[to];
                to = (to & (to + 1)) - 1;
            }
            return result;
        }

        public void add(int at, long value) {
            while (at < this.value.length) {
                this.value[at] += value;
                at = at | (at + 1);
            }
        }

    }

    static class MiscUtils {
        public static void decreaseByOne(int[]... arrays) {
            for (int[] array : arrays) {
                for (int i = 0; i < array.length; i++) {
                    array[i]--;
                }
            }
        }

    }

    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;
        }

        public static void readIntArrays(InputReader in, int[]... arrays) {
            for (int i = 0; i < arrays[0].length; i++) {
                for (int j = 0; j < arrays.length; j++) {
                    arrays[j][i] = in.readInt();
                }
            }
        }

    }

    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);
        }

    }

    static class ArrayUtils {
        public static int[] createArray(int count, int value) {
            int[] array = new int[count];
            Arrays.fill(array, value);
            return array;
        }

    }
}

