Bài tập

Hai số nguyên tố \(p\) và \(q\) được gọi là một cặp nguyên tố sexy nếu \(q - p = 6\) (chữ "sexy" đến từ "sex" trong tiếng Latin nghĩa là sáu). Các cặp được liệt kê theo thứ tự tăng dần của số nhỏ \(p\): \((5,11), (7,13), (11,17), (13,19), (17,23), \dots\) Lưu ý một số có thể thuộc hai cặp khác nhau, ví dụ \(11\) thuộc \((5,11)\) và \((11,17)\).

Cho \(T\) câu hỏi, mỗi câu hỏi là một số \(N\). Hãy tìm cặp nguyên tố sexy thứ \(N\).

Input

• Dòng đầu: số nguyên \(T\).
• \(T\) dòng tiếp theo, mỗi dòng một số nguyên \(N\).

Output

In ra \(T\) dòng; dòng thứ \(i\) gồm hai số \(p\) và \(p+6\) của cặp thứ \(N\) tương ứng, cách nhau một dấu cách.

Constraints

• \(1 \le T \le 10^3\).
• \(1 \le N \le 10^4\).

Sample Input

3
4
1
12

Sample Output

13 19
5 11
61 67

Cho xâu \(S\) gồm \(n\) chữ cái Latin in hoa. Xét mọi cặp hai ký tự đứng liền nhau trong \(S\) (vị trí \(i\) và \(i+1\)) và tìm cặp xuất hiện nhiều nhất; các lần xuất hiện được phép chồng lấn. Nếu nhiều cặp cùng đạt số lần lớn nhất, chọn cặp có thứ tự từ điển nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng hai chứa xâu \(S\) gồm \(n\) chữ cái Latin in hoa.

Output

In ra cặp chữ cái được chọn.

Constraints

• \(2 \le n \le 10^5\)

Sample Input

8
XYXYXXYZ

Sample Output

XY

Explanation

Các cặp liền kề: \(XY, YX, XY, YX, XX, XY, YZ\). Cặp \(XY\) xuất hiện \(3\) lần, nhiều nhất.

Vương quốc Berland có \(n\) công dân, công dân thứ \(i\) đang nhận phúc lợi \(a_i\) đồng burle. Nhà vua muốn mọi người có phúc lợi bằng nhau, và chỉ được tăng phúc lợi của ai đó (lấy từ ngân khố), không được lấy bớt của ai.

Hãy tính tổng số burle ít nhất mà ngân khố phải chi để tất cả công dân có phúc lợi bằng nhau.

Input

• Dòng đầu: số nguyên \(n\).
• Dòng thứ hai: \(n\) số nguyên \(a_1, \dots, a_n\).

Output

Một số nguyên: tổng chi phí nhỏ nhất.

Constraints

• \(1 \le n < 100\)
• \(|a_i| < 10^6\)

Sample Input

5
3 9 1 9 4

Sample Output

19

Explanation

Nâng mọi người lên mức \(9\): \(6 + 0 + 8 + 0 + 5 = 19\).

Một lưới điện có \(N\) trạm phát, công suất hiện tại của trạm thứ \(i\) là số nguyên \(A_i\) (có thể âm). Mỗi thao tác chọn hai trạm khác nhau \(i \neq j\), rồi tăng \(A_i\) lên \(1\) và giảm \(A_j\) đi \(1\) (tổng công suất không đổi).

Có \(T\) ngưỡng \(D_1, D_2, \dots, D_T\). Các ngưỡng được xét độc lập: với mỗi \(D\), ta xuất phát từ dãy \(A\) ban đầu và cần thực hiện ít thao tác nhất sao cho hiệu giữa công suất lớn nhất và nhỏ nhất trong dãy không vượt quá \(D\), tức \(|A_x - A_y| \le D\) với mọi cặp \(x, y\). Hãy tính số thao tác tối thiểu đó cho từng ngưỡng.

Input

• Dòng đầu: hai số nguyên \(N\) và \(T\).
• Dòng thứ hai: \(N\) số nguyên \(A_1, \dots, A_N\).
• Dòng thứ ba: \(T\) số nguyên \(D_1, \dots, D_T\).

Output

In ra \(T\) dòng; dòng thứ \(k\) là số thao tác tối thiểu ứng với ngưỡng \(D_k\).

Constraints

• \(1 \le N, T \le 10^6\)
• \(|A_i| \le 10^6\)
• \(1 \le D_k \le 10^6\)

Chấm điểm theo subtask:

• Subtask 1 (20%): \(N, T \le 10\), \(|A_i| \le 1000\).
• Subtask 2 (40%): \(N, T \le 1000\).
• Subtask 3 (40%): không có ràng buộc thêm.

Sample Input

4 2
1 7 3 5
3 1

Sample Output

2
4

Explanation

Với \(D=3\): thao tác \((i=1,j=2)\) rồi \((i=3,j=2)\) cho dãy \([2,5,4,5]\) có chênh lệch \(3\); một thao tác thì chưa đủ nên đáp án là \(2\). Với \(D=1\): bắt buộc đưa về \([4,4,4,4]\), cần \(4\) thao tác.