Cho số ~n~. Hãy tìm số ~k \le n~ lớn nhất sao cho ~k~ là tích của 3 số nguyên tố liên tiếp.

Input

• Gồm số tự nhiên ~n \le 10^{18}~.

Output

• Gồm duy nhất một số tự nhiên ~k~. Nếu không có số thỏa mãn in ra -1.

Sample Test

Input:

31

Output

30

Cho dãy số nguyên ~A_1, A_2, \dots, A_N~. Với số nguyên ~x~, ta định nghĩa khoảng cách từ ~x~ tới dãy ~A~ là ~\min_{1 \le i \le n} |x - A_i|~.

Cho hai số nguyên ~L~, ~R~, hãy tìm số nguyên ~x \in [L, R]~ sao cho khoảng cách từ ~x~ đến dãy ~A~ là lớn nhất có thể. Nếu có nhiều giá trị ~x~ thoả mãn, hãy đưa ra giá trị ~x~ lớn nhất.

Input

Dòng đầu chứa ba số nguyên ~N~, ~L~, ~R~ (~1 \le N \le 10^5~; ~-2^{63} \le L \le R < 2^{63}~).

Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~-2^{63} \le A_i < 2^{63}~).

Output

In ra một số nguyên duy nhất là giá trị ~x~ tìm được.

Example

Input

4 3 8
2 4 6 8

Output

7

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).~

Thành phố XYZ bị một dòng sông chia cắt thành hai vùng là A và B. Mỗi vùng bao gồm dòng sông và một dãy toà nhà chạy dọc theo bờ sông, được đánh số từ ~0~ đến ~10^9~. Khoảng cách giữa hai toà nhà kề nhau là ~1~ đơn vị, và bề rộng dòng sông cũng bằng ~1~ đơn vị. Toà nhà ~i~ ở vùng A luôn đối diện với toà nhà ~i~ ở vùng B.

Có ~N~ công dân sinh sống và làm việc trong thành phố. Công dân ~i~ sống ở vùng ~P_i~ tại toà nhà ~S_i~ và làm việc ở vùng ~Q_i~ tại toà nhà ~T_i~. Hiện tại họ phải qua sông bằng thuyền, nên chính phủ quyết định xây dựng ~K~ cây cầu để người dân có thể đi lại bằng xe.

Mỗi cây cầu phải được đặt giữa đúng hai toà nhà đối diện nhau và phải vuông góc với dòng sông. Các cây cầu không được chồng lên nhau.

Ký hiệu ~D_i~ là khoảng cách nhỏ nhất mà công dân ~i~ phải di chuyển từ nhà đến nơi làm việc sau khi xây dựng ~K~ cây cầu.

Yêu cầu: Tìm phương án xây dựng ~K~ cây cầu sao cho tổng ~D_1 + D_2 + \dots + D_N~ là nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên ~K~ và ~N~ (~K \le 2~; ~1 \le N \le 10^5~).
• Mỗi trong ~N~ dòng tiếp theo chứa bốn giá trị ~P_i, S_i, Q_i, T_i~:
  • ~P_i \in \{A, B\}~, ~S_i~ là toà nhà (~0 \le S_i \le 10^9~).
  • ~Q_i \in \{A, B\}~, ~T_i~ là toà nhà (~0 \le T_i \le 10^9~).
• Có thể có nhiều công dân có nhà hoặc nơi làm việc trùng cùng một toà nhà.

Output

• In ra một số nguyên duy nhất — tổng khoảng cách nhỏ nhất.

Subtasks

• 25%: ~K = 1~, ~1 \le N \le 10^3~
• 25%: ~K = 1~, ~1 \le N \le 10^5~
• 25%: ~K = 2~, ~1 \le N \le 10^3~
• 25%: ~K = 2~, ~1 \le N \le 10^5~

Sample Test

Input 1

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

Output 1

24

Input 2

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

Output 2

22