Cho một dãy ~a~ gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~.

Yêu cầu: Viết chương trình đếm số lượng cách chọn ra trong dãy ~a~ hai phần tử sao cho tích của hai phần tử đó là một số chẵn.

Input

• Dòng 1: Chứa một số nguyên ~n~ (~2 \le n \le 10^6~);
• Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~0 \le a_i \le 10^{18}~ với ~1 \le i \le n~), các số cách nhau bởi một dấu cách trống.

Output

Ghi ra một số nguyên duy nhất là số lượng cặp số thỏa mãn yêu cầu đề bài.

Sample Input 1

5
1 6 6 13 8

Sample Output 1

9

Subtasks

• Có 40% số test ứng 40% số điểm của bài với ~n \le 10^3~;
• Có 30% số test ứng 30% số điểm của bài với ~a_i~ chẵn (~1 \le i \le n~);
• 30% số test còn lại ứng 30% số điểm của bài không có thêm ràng buộc.

Cho dãy số ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Viết chương trình tính tổng các ước dương của mỗi phần tử trong dãy ~a~.

Input

• Dòng 1: Chứa số nguyên dương ~n~ (~n \le 10^6~);
• Dòng 2: Chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^6~; ~1 \le i \le n~).

Output

Ghi ra gồm một dòng chứa ~n~ số nguyên, số thứ ~i~ là tổng các ước dương của phần tử ~a_i~.

Sample Input 1

4
2 4 10 9

Sample Output 1

3 7 18 13

Subtasks

• Có 40% số test ứng với 40% số điểm của bài có ~n = 1~;
• Có 30% số test ứng với 30% số điểm của bài có ~1 < n \le 10^3~;
• 30% số test còn lại ứng với 30% số điểm của bài không có thêm ràng buộc.

Trong tiết học Mỹ thuật, Zin được cô giáo giao cho bài tập phối màu cho các đỉnh của ~p~ hình tam giác như sau: Zin được cung cấp ~n~ hình tròn được đánh số lần lượt từ 1 đến ~n~.

Hình tròn thứ ~i~ có màu sắc được mã hóa thành một số nguyên ~a_i~.

Đầu tiên Zin chọn ra 3 hình tròn để dán lên 3 đỉnh của tam giác thứ nhất, giả sử chọn các hình tròn có số thứ tự ~i, j, k~ (~i < j < k~) khi đó độ tương phản của tam giác thứ nhất bằng ~\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)~.

Sau đó, Zin chọn 3 hình tròn tiếp theo (từ hình tròn có số thứ tự lớn hơn ~k~) để trang trí cho tam giác thứ 2.

Lặp đi lặp lại các thao tác trên cho đến khi trang trí đủ ~p~ hình tam giác. Độ tương phản của ~p~ hình tam giác là độ tương phản của hình tam giác có độ tương phản lớn nhất.

Yêu cầu: Hãy giúp Zin trang trí cho ~p~ hình tam giác để có độ tương phản là nhỏ nhất có thể.

Input

• Dòng 1: Chứa hai số nguyên ~n, p~ (~3 \le n \le 500~; ~3 \times p \le n~);
• Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~; ~1 \le i \le n~).

Output

Ghi ra một số nguyên duy nhất là độ tương phản nhỏ nhất có thể tìm được.

Sample Input 1

10 2
3 9 4 4 -7 13 -6 4 -5 1

Sample Output 1

2

Subtasks

• Có 40% số test ứng với 40% số điểm của bài có ~3 \times p = n~;
• Có 30% số test ứng với 30% số điểm của bài có ~p = 1~;
• 30% số test còn lại ứng với 30% số điểm của bài không có thêm ràng buộc.

Sau trận mưa lũ lớn, trung tâm cứu trợ đặt tại địa điểm số 1 cần vận chuyển hàng hóa đến khu vực bị cô lập nghiêm trọng nhất tại địa điểm số ~N~.

Hệ thống giao thông gồm ~N~ địa điểm được đánh số từ 1 đến ~N~ và ~M~ con đường hai chiều nối các địa điểm. Mỗi con đường nối hai địa điểm ~u, v~ có chi phí vận chuyển là ~c~ và giới hạn tải trọng tối đa là ~w~ (tấn).

Do điều kiện cầu đường không đồng đều, nếu một con đường trong hành trình chỉ chịu được ~w~ (tấn) thì xe chỉ có thể vận chuyển tối đa ~w~ (tấn) theo hành trình đó. Vì vậy, tải trọng của một hành trình được xác định bằng giá trị nhỏ nhất trong các giới hạn tải trọng của các con đường thuộc hành trình.

Xe cứu trợ chỉ chọn một hành trình duy nhất từ địa điểm 1 đến địa điểm ~N~. Hiệu quả của hành trình được xác định bởi: Hiệu quả = ~\frac{\text{Tải trọng của hành trình}}{\text{Tổng chi phí của hành trình}}~

Yêu cầu: Hãy xác định hiệu quả lớn nhất có thể đạt được.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, M~ (~2 \le N \le 1000~; ~1 \le M \le 1000~);
• ~M~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương ~u, v, c, w~ (~u, v \le N~; ~u \ne v~; ~c, w \le 1000~). Dữ liệu đảm bảo tồn tại ít nhất một đường đi từ 1 đến ~N~.

Output

Ghi ra một số là ~10^6~ lần giá trị hiệu quả lớn nhất, lấy phần nguyên (tức là làm tròn xuống nếu giá trị này không phải số nguyên).

Sample Input 1

3 3
1 2 2 4
2 3 5 3
1 3 15 2

Sample Output 1

428571

• Nếu đi theo tuyến đường ~1 \rightarrow 2 \rightarrow 3~ thì tải trọng tối đa bằng ~\min(4, 3) = 3~ và tổng chi phí là ~2 + 5 = 7~, hiệu quả đạt được là ~\frac{3}{7}~.
• Nếu đi theo tuyến đường ~1 \rightarrow 3~ thì tải trọng tối đa bằng 2 và tổng chi phí bằng 15, hiệu quả đạt được là ~\frac{2}{15}~. Vậy hiệu quả lớn nhất là ~\frac{3}{7}~. Theo yêu cầu đề bài, kết quả là ~\lfloor 10^6 \times \frac{3}{7} \rfloor = 428571~.

Subtasks

• Có 30% số test ứng 30% số điểm của bài có ~2 \le N, M \le 100~ và mọi con đường có ~w~ bằng nhau;
• Có 30% số test ứng 30% số điểm của bài có ~2 \le N, M \le 100~;
• 40% số test còn lại ứng 40% số điểm của bài không có thêm ràng buộc.