Chúng ta đã quá rõ việc một số nguyên tố (prime) là số nguyên dương lớn hơn ~1~ có duy nhất hai ước là ~1~ và chính nó. Để làm mới bài toán, hôm nay, ta sẽ định nghĩa một số TPrime là một số nguyên dương lớn hơn ~1~ gồm đúng ~3~ ước.

Cho ~n~ truy vấn, mỗi truy vấn là một số ~a~, hãy kiểm tra xem số này có phải là số TPrime hay không.

Input

• Dòng ~1~ ghi số nguyên dương ~n~ ~(1 \le n \le 3*10^5)~
• ~n~ dòng sau, mỗi dòng gồm một số nguyên dương ~a~ ~(1 \le a \le 10^{12})~ miêu tả truy vấn.

Output

• In ra ~n~ dòng, với mỗi truy vấn, nếu ~a~ là số TPrime thì in ra "YES", ngược lại in ra "NO".

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100, 1 \le a \le 10^4~
• Có ~30\%~ số test ứng với ~1 \le n,a \le 10^5~
• Có ~50\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

3
4
6
7

Sample Output 1

YES
NO
NO

Nông dân John (FJ) có ~N~ con bò đang đứng trên một hàng, mỗi con đứng ở một vị trí khác nhau trên trục số. Chúng đang luyện tập ném trái bóng chày vòng vòng để chuẩn bị cho một trận thi đấu quan trọng với những con bò láng giềng. Khi FJ theo dõi, ông ta nhận ra một nhóm có ba con bò ~(X,Y,Z)~ hoàn thành hai cú ném. Con bò ~X~ ném trái bóng cho con bò ~Y~ ở bên phải cô ta, và con bò ~Y~ ném trái bóng cho con bò ~Z~ ở bên phải cô ta. FJ để ý rằng lần ném thứ hai có độ dài không quá hai lần so với lần ném đầu tiên. Hãy giúp FJ đếm xem có bao nhiêu bộ ba các con bò ~(X,Y,Z)~ mà FJ có thể theo dõi.

Input

• Dòng ~1~: Số lượng các con bò là ~N~ ~(3 <= N <=1000)~.
• Dòng ~2..1+N~: Mỗi dòng chứ một số tự nhiên là vị trí của một con bò (các số tự nhiên nằm trong khoảng ~0..10^8~).

Output

In ra Số lượng bộ ba con bò ~(X,Y,Z)~, trong đó con bò ~Y~ nằm bên phải con bò ~X~, con bò ~Z~ nằm bên phải con bò ~Y~, và khoảng cách giữa ~Y~ và ~Z~ nằm giữa ~XY~ và ~2XY~ (bao gồm cả giá trị này), trong đó ~XY~ là khoảng cách của ~X~ đến ~Y~.

Sample Test

Input:

5 
3 
1 
10 
7 
4 

Output

4

hoangduong có ~n~ cuốn sách (~1 \le n \le 2000~), và hoangduong muốn xây một kệ sách gồm nhiều tầng để chứa tất cả các cuốn sách này.

Mỗi cuốn sách có chiều rộng ~w_i~ và chiều cao ~h_i~. Các cuốn sách cần được bỏ vào các tầng kệ sách theo thứ tự. Ví dụ như tầng thứ nhất cần bỏ các cuốn sách từ ~1~ đến ~k~, tầng thứ ~2~ sẽ bắt đầu từ cuốn sách thứ ~k + 1~, và cứ thế tiếp tục. Mỗi tầng kệ sách có chiều rộng tối đa là ~L~ (~1 \le L \le 10^9~). Chiều cao của mỗi tầng kệ sách bằng với chiều cao của cuốn sách có chiều cao lớn nhất, và chiều cao của cả kệ sách bằng với tổng chiều cao của mỗi tầng kệ sách khi xếp dọc lên (bỏ qua tấm gỗ ngăn cách giữa các tầng kệ sách).

Hãy giúp hoangduong tính chiều cao thấp nhất có thể của cả kệ sách khi xếp chồng lên nhau.

INPUT

Dòng 1: Gồm hai số tự nhiên cách nhau là ~n~ và ~L~.

~n~ dòng tiếp theo mỗi dòng chứa hai số tự nhiên cách nhau là ~h_i~ và ~w_i~. (~1 \le h_i \le 10^9~, ~1 \le w_i \le L~).

OUTPUT

Một dòng duy nhất chứa chiều cao nhỏ nhất của cả kệ sách.

SAMPLE INPUT

5 10
5 7
9 2
8 5
13 2
3 8

SAMPLE OUTPUT

21

Giải thích: Có ba tầng, tầng đầu tiên chứa cuốn sách thứ nhất (chiều cao là ~5~ và chiều rộng là ~7~), tầng thứ hai chứa cuốn thứ ~2~ đến cuốn thứ ~4~ (chiều cao là ~13~, chiều rộng là ~9~), và tầng chứa cuốn sách thứ ~5~ (chiều cao là ~3~, chiều rộng là ~8~).

Xâu đẹp là xâu có nhiều nhất một ký tự có số lần xuất hiện là lẻ. Cho xâu ~S~ có độ dài ~n~ chỉ gồm các chữ cái thường ~S_0S_1 \dots S_{n-1}~. Một đoạn ~(i,j)~ của xâu ~S~ là xâu: ~S_iS_{i+1} \dots S_j~.

Yêu cầu: Với mỗi đoạn ~(i,j)~, hãy xác định số ký tự ít nhất cần thay đổi để đoạn ~(i,j)~ thành xâu đẹp.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~Q~ (~n,Q \leq 10^6~) - lần lượt là độ dài xâu và số lượng truy vấn.
• Dòng thứ hai chứa xâu ~S~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số ~i~ và ~j~ (~0 \leq i \leq j \leq n - 1~) - xác định một đoạn trong xâu ~S~ cần biến đổi.

Output

Gồm ~Q~ dòng lần lượt là kết quả của ~Q~ truy vấn.

Sample Test

Note

• Đoạn [~1,3~] của xâu ~S~ là "bca". Có thể thay đổi kí tự 'c' thành kí tự 'b', ta được xâu "bba" thỏa mãn.
• Đoạn [~2,7~] của xâu ~S~ là "caacba". Có thể thay đổi kí tự 'b' thành kí tự 'a', ta được xâu "caacaa" thỏa mãn.
• Đoạn [~1,6~] của xâu ~S~ là "bcaacb". Đây là xâu đẹp rồi nên không cần biến đổi.

Marisa có ~n~ tấm gỗ và sẽ sửa lại chúng để sử dụng, tấm gỗ thứ ~i~ sẽ có độ đẹp là ~A_i~ hoặc ~B_i~ (tuỳ vào mục đích sử dụng mà Marisa sẽ sửa chúng khác nhau).

Marisa dự định chọn ra ~k~ tấm gỗ để làm hàng rào bao quanh nhà. Trong đó, cô sẽ chọn ra ~k-1~ tấm để dựng hàng rào và ~1~ tấm để làm cửa. Khi đó, những tấm để làm hàng rào sẽ có độ đẹp là ~A_i~ và tấm để làm cửa sẽ có độ đẹp là ~B_i~.

Marisa đang cân nhắc số lượng tấm gỗ sử dụng để làm hàng rào, nên cô sẽ hỏi bạn ~q~ câu hỏi, mỗi câu hỏi là một số nguyên ~k~, hãy giúp cô tính độ đẹp lớn nhất có thể khi sử dụng ~k~ tấm gỗ.

Dữ liệu vào từ tệp văn bản: xayhangrao.inp

• Dòng đầu tiên gồm hai số nguyên ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.
• Dòng thứ ba gồm ~n~ số nguyên ~B_i~.
• Dòng thứ tư gồm ~q~ số nguyên ~k~ theo thứ tự, mô tả các truy vấn.

Kết quả ghi ra tệp văn bản: xayhangrao.out

• In ra ~q~ số nguyên, số nguyên thứ ~i~ là đáp án truy vấn thứ ~i~.

Ví dụ

Input 1:

3 1
3 5 4
5 8 5
3

Output 1:

15

Input 2:

3 2
3 5 4
5 8 5
3 2

Output 1:

15 12

Giới hạn: Trong mọi test: ~1 \le n,q \le 10^5, 1 \le A_i, B_i \le 10^9~.

• Subtask 1 (25% số điểm): Marisa chỉ hỏi bạn một câu hỏi duy nhất với ~k = n~.
• Subtask 2 (25% số điểm): ~1 \le n,q \le 10~.
• Subtask 3 (25% số điểm): ~1 \le n,q \le 1000~.
• Subtask 4 (25% số điểm): Không có giới hạn gì thêm.