Một dãy gồm \(n\) số nguyên \(a_1, a_2,..., a_n\) được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả \((n-1)\) khoảng trắng. Người ta muốn đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ, với dãy gồm 5 số nguyên \(28, 9, 5, 1, 69\) và \(k = 2\) thì cách đặt \(28+9-5-1+69\) là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm n số nguyên \(a_1, a_2,..., a_n\) và số nguyên dương \(k\), hãy tìm cách đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(n, k (k < n)\);
• Dòng thứ hai chứa n số nguyên \(a_1, a_2,..., a_n\) (\(a_n ≤ 10^6\))

Output

• Một số nguyên là giá trị của biểu thức đạt được.

Ví dụ

Input:

5 2
28 9 5 1 69

Output:

100

Ghi chú:

• Có 50% số test ứng với 50% số điểm có \(n ≤ 10^5\) và \(k = 1\);
• Có 50% số test còn lại ứng với 50% số điểm có \(n ≤ 10^5\);

Bạn được một mảng \(A\) gồm \(N\) số nguyên dương.

Bạn sẽ chọn một số phần tử từ mảng \(A\) sao cho giá trị trung bình của các phần tử đã chọn nhỏ hơn \(K\).

Nhiệm vụ của bạn là xác định xem có thể chọn nhiều nhất bao nhiêu phần tử với \(K\) cho trước.

Input

• Dòng đâu tiên chứa số nguyên dương \(N\) \((N \leq 5*10^5)\).
• Dòng 2 chứa \(N\) số nguyên dương \(A_i\) \((A_i \leq 10^9)\).
• Dòng thứ 3 chứa số nguyên \(Q\) \((Q \leq 5\times 10^5)\) - là số câu hỏi.
• \(Q\) dòng tiếp theo, mỗi dòng chứa \(1\) giá tri \(K\) \((K \leq 10^9)\).

Output

• Gồm \(Q\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

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

0
2
4
5
5

Số nguyên dương \(x\) được gọi là một ước nguyên tố của số nguyên \(k\) nếu \(k\) chia hết cho \(x\) và \(x\) là số nguyên tố.

Yêu cầu: Nhập từ bàn phím một số nguyên dương \(k\). Hãy in ra màn hình tổng các ước nguyên tố của số \(k\).

Dữ liệu

• Số nguyên dương \(k\)

Kết quả

• Tổng các ước nguyên tố của số \(k\)

Input

21

Output

10

Ràng buộc

• Sub1: 70% test: \(k\le 10^{10}\) theo đề chuẩn
• Sub2: 30% test: \(k\le 10^{16}\) mở rộng

Nguồn: Bài 1 TS10 LQĐ TPĐN '2014

In ra tất cả cặp số nguyên tố \(A,B(A\le B)\) thỏa mãn \(A+B\) cũng là số nguyên tố và \(A+B\le N\).

Input

• Dòng thứ nhất chứa số nguyên dương \(N(1\le N\le 10^6)\)

Output

• Dòng thứ nhất in ra số \(k\) - số lượng cặp \((A,B)\) thỏa mãn yêu cầu bài toán

• In ra \(k\) cặp \((A,B)\) thỏa mãn yêu cầu bài toán (theo thứ tự từ điển từ bé đến lớn).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0<N\le 10\)

• Subtask \(2\) (\(20\%\) số điểm): \(0<N\le 10^4\)

• Subtask \(3\) (\(60\%\) số điểm): Không có yêu cầu gì thêm.

Example

7

2
2 3
2 5

Bạn được cho 2 số nguyên dương \(a, b\) \((a<b)\). Hãy tính số các số x thỏa mãn \(0\leq x <b\) và \(\gcd(a,b)=\gcd(a+x,b)\).

\(\gcd(x,y)\): Ước chung lớn nhất của \(x\) và \(y\).

Input

• Dòng đầu tiên chứa \(t\) \((1 \leq t \leq 50)\) - số câu hỏi.
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a\) và \(b\) \((1 \leq a, b \leq 10^{10})\).

Output

• Ứng với mỗi câu hỏi in ra số \(x\) cần tìm.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \((1 \leq a, b \leq 1000)\);
• Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm.

Example

3
4 9
5 10
42 9999999967 

6
1
9999999966

Cho số nguyên dương \(N\).

Tính giá trị biểu thức:

Nói cách khác, bạn hãy tính giá trị của biểu thức \(GCD(N,1^2) + GCD(N, 2^2) + .... + GCD(N,N^2)\).

Trong đó, \(GCD(a,b)\) chính là ước chung lớn nhất của \(a\) và \(b\).

Định nghĩa: Ước chung lớn nhất của hai số \(a\) và \(b\) là số nguyên
dương lớn nhất mà cả \(a\) và \(b\) đều chia hết.

Input

• Dòng đầu ghi \(q\) \((q \le 75)\) - số câu hỏi.
• \(q\) dòng tiếp theo, mỗi dòng ghi số nguyên dương \(N\) \((N \le 10^5)\).

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

2
1
2

1
3