Một cuộc đua dành cho máy bay không người lái thông minh (UAV cỡ nhỏ) được tổ chức trên một đường băng dài gồm N vạch cách đều nhau, vách cách vạch ~10~ mét. Các vạch được đánh số từ ~1~ đến ~N~. Trên mỗi vạch đều có đặt một bộ cảm biến có nhiệm vụ gửi về trung tâm điều khiển (TTDK) của Ban tổ chức (BTC) cuộc thi số hiệu của vạch khi UAV đứng hay hạ cánh tại vạch này. Cuộc đua cho mỗi UAV được tiến hành như sau: UAV vào đứng tại vạch ~1~, có thời gian ~1~ giây để nạp dữ liệu mà BTC cung cấp, dữ liệu gồm một số nguyên dương ~L~ và ~N~ số nguyên ~X_i~ ~(i=1,\cdots ,n)~ với ý nghĩa ~X_i~ là giá trị của vạch ~i~. Ngay sau đó, UAV phải được thực hiện hành trình bằng cách di chuyển liên tục như sau:

• Trong hành trình lượt đi, UAV (đứng tại vạch ~1~) cần bay đến vạch ~N~ theo quy tắc: Nếu đang đứng ở vạch ~i~ ~(1 \le i \le N)~ thì nó sẽ chỉ được phép hạ cánh tại vạch ~j~ ~(j>i)~ mà ~X_j~ lẻ (ấn định rằng ~X_N=1001~) đồng thời vạch ~j~ cách vạch ~i~ không quá ~L~ vạch (tức là ~1\le j-i \le L)~. Tổng số lần UAV đứng hay hạ cánh trong hành trình lượt đi, bao gồm tại cả vạch ~1~ và vạch ~N~, được ký hiệu bởi ~U~.

• Trong hành trình lượt về, bắt đầu với số điểm được BTC cung cấp bằng ~X_N=1001~, UAV từ vạch ~N~ bay tiếp về vạch ~1~ theo quy tắc: Nếu đang đứng ở vạch ~i~ ~(1<i\le n)~ thì nó sẽ chỉ được phép hạ cánh tại vạch ~k~ ~(k<i)~ mà ~X_K~ chẵn (ấn định rằng ~X_1=1000~). UAV sẽ nhận được thêm ~X_k~ điểm nếu vạch ~k~ cách vạch ~i~ đúng ~L~ vạch (tức ~i-k=L~) và bị trừ ~X_k~ điểm trong trường hợp trái lại. Tổng số điểm mà UAV thu được trong hành trình lượt về, được ký hiệu là ~V~.</p>

Lưu ý:

• Các UAV được lập trình sẵn để tiếp nhận và xử lý dữ liệu của BTC rồi tự động thực hiện toàn bộ hành trình (lượt đi và về).

• Dữ liệu mà BTC đưa ra luôn đảm bảo để các UAV có thể thực hiện được cuộc đua.

Yêu cầu: Hãy lập trình cho UAV để nó đạt được giá trị nhỏ nhất của ~U~ và lớn nhất của ~V~.

Input

Cho trong file văn bản UAV.INP có cấu trúc như sau:

• Dòng đầu ghi số nguyên ~L~ ~(10\le L\le 100)~.

• Dòng thứ ~2~ ghi số nguyên ~N~ ~(L<N\le 500000)~.</p>

• Dòng thứ ~3~ ghi lần lượt các số nguyên ~X_2,\ X_3,\cdots ,\ X_{n-1}~ ~(0\le X_i \le 10^6; i=2,\cdots ,N-1)~.

  Các số trên cùng dòng viết cách nhau bởi ít nhất một dấu cách.

Output

Ghi ra tệp văn bản UAV.OUT ~2~ số nguyên trên ~2~ dòng: Dòng đầu là ~U~ và dòng sau là ~V~.

Scoring

~50\%~ số test ứng với ~50\%~ số điểm của bài có ~N\le 1000~

Sample Input 1

10
19
6 3 15 2 30 7 8 6 10 2 4 9 9 15 0 18 10

Sample Output 1

4
1999