Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~.

Cho ~q~ truy vấn, mỗi truy vấn gồm ba số nguyên ~x, y, z~, hãy tính giá trị của ~f(x, y, z)~. Biết rằng: $$f(x, y, z) = \displaystyle\max_{1 \le i \lt j \lt k \le n}(x \times a_i + y \times a_j + z \times a_k).$$

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q \ (q \le 100);~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n \ (1 \le a_i \le 10^6; \ 1 \le i \le n);~
• ~q~, dòng sau, dòng thứ ~i~ chứa ba số nguyên dương ~x_i, y_i, z_i \ (|x_i|, |y_i|, |z_i| \le 1000; \ 1 \le i \le q).~

Output

In ra ~q~ dòng, dòng thứ ~i \ (1 \le i \le q)~ là giá trị của ~f(x_i, y_i, z_i)~.

Scoring

• Subtask 1 [20%]: ~3 \le n \le 100;~
• Subtask 2 [20%]: ~3 \le n \le 500; \ 1 \le x, y, z \le 1000;~
• Subtask 3 [20%]: ~3 \le n \le 500;~
• Subtask 4 [20%]: ~3 \le n \le 10^5; \ 1 \le x, y, z \le 1000;~
• Subtask 5 [20%]: ~3 \le n \le 10^5.~

Examples

Input

7 2
3 1 3 4 2 4 12
1 2 3
-1 -2 -3

Output

48
-11

Giải thích

• Truy vấn 1: Chọn bộ ba chỉ số ~(4, 6, 7).~
• Truy vấn 2: Chọn bộ ba chỉ số ~(1, 2, 5).~