bouquets

A flower shop has an unlimited quantity of flowers of $N$ types, each having respectively $a_1, a_2, .., a_N$ petals. A corporate client has made $M$ orders at the shop. Each order has the following requirements:

• $K$ different bouquets must be made, each containing the same number of flowers (two bouquets are considered different if there is a difference in the types of flowers used);
• Only flowers having at least $L$ and at most $R$ petals may be used;
• Each bouquet may contain at most one flower of each type.

The florists want to use as few flowers as possible. Help them by writing the program bouquets that determines the minimum number of flowers each bouquet can contain for every order so that the given requirements are satisfied.

Input data

The first line of the standard input contains the positive integers $N$ and $M$, representing respectively the number of different types of flowers and the number of orders. The next line contains $N$ positive integers $a_1,a_2,...,a_N$, indicating the number of petals for each type of flower. Each of the following $M$ lines contains three positive integers $L$, $R$, and $K$, describing each order.

Output data

For each order, print the requested number of flowers on a separate line. If a given order cannot be fulfilled, output $-1$ for it.

Restrictions

• $1 \leq N \leq 3 \ 000$
• $1 \leq M \leq 10^5$
• $1 \leq a_i \leq 10^5$
• $1 \leq L \leq R \leq 10^5$
• $1 \leq K \leq 10^{900}$

Example

stdin

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

stdout

1
-1
2

Explanation

For the first order, the flowers of type $1$, $2$ and $7$ can be used (with $3$, $4$ and $2$ petals accordingly). If each bouquet contains one flower, exactly $3$ different bouquets can be made.
For the second order, the flowers of type $2$ and $5$ can be used (with $4$ and $6$ petals accordingly). Thus, it is not possible to make $3$ different bouquets. For the third order, a total of $4$ types of flowers can be used. If each bouquet contains $2$ flowers, at least $5$ different bouquets can be made.