Bài tập

Cho một từ \(W\) gồm các chữ cái Latinh. Bằng cách xáo trộn (hoán đổi vị trí) các chữ cái của \(W\) ta thu được các từ mới có cùng độ dài. Hãy liệt kê tất cả các từ khác nhau có thể tạo ra theo cách đó (bao gồm cả chính từ ban đầu).

Chẳng hạn từ pqp chỉ tạo được ba từ khác nhau là ppq, pqp và qpp, dù có ba chữ cái.

Input

Một dòng chứa từ \(W\) gồm các chữ cái Latinh (chữ hoa và chữ thường là hai ký tự khác nhau), độ dài từ \(1\) đến \(9\).

Output

• Dòng đầu tiên: số lượng từ khác nhau tạo được.
• Mỗi dòng tiếp theo: một từ. Các từ in theo thứ tự từ điển tăng dần (theo mã ASCII của ký tự).

Constraints

• \(1 \le |W| \le 9\)

Sample Input

pqp

Sample Output

3
ppq
pqp
qpp

Trong buổi vũ hội mùa xuân của trang trại có \(N\) chú bò đực và \(M\) cô bò cái với \(N < M\). Bác nông dân John muốn xếp mỗi chú bò đực nhảy cùng đúng một cô bò cái, mỗi cô bò cái nhảy với nhiều nhất một chú bò đực (vì \(N < M\) nên sẽ có \(M - N\) cô bò cái không có bạn nhảy).

Chú bò đực thứ \(i\) cao \(B_i\) và cô bò cái thứ \(j\) cao \(C_j\). Để buổi biểu diễn trông cân đối nhất, bác John muốn tổng độ lệch chiều cao \(\sum |B_i - C_{\pi(i)}|\) của tất cả các cặp là nhỏ nhất, trong đó \(\pi(i)\) là cô bò cái được ghép với chú bò đực \(i\).

Hãy tính tổng độ lệch nhỏ nhất đó.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\).
• Dòng thứ hai chứa \(N\) số nguyên \(B_1, \dots, B_N\).
• Dòng thứ ba chứa \(M\) số nguyên \(C_1, \dots, C_M\).

Output

In ra một số nguyên là tổng độ lệch chiều cao nhỏ nhất.

Constraints

• \(1 \le N < M \le 5000\)
• \(1 \le B_i, C_j \le 10^6\)

Sample Input

4 6
8 3 15 9
14 2 9 20 4 7

Sample Output

3

Explanation

Ghép \(3 \to 2\) (lệch 1), \(8 \to 7\) (lệch 1), \(9 \to 9\) (lệch 0), \(15 \to 14\) (lệch 1): tổng \(3\).

Trên một vòng tròn có \(2n\) ô, các ô được đánh số từ \(1\) đến \(2n\) theo chiều kim đồng hồ (ô \(2n\) nằm cạnh ô \(1\)). Ta cần điền vào mỗi ô một số nguyên từ \(1\) đến \(2n\), mỗi số dùng đúng một lần, sao cho tổng hai số ở hai ô kề nhau luôn là số nguyên tố (kể cả cặp ô \(2n\) và ô \(1\)). Ngoài ra ô số \(1\) luôn phải chứa số \(1\).

Cho \(n\), hãy liệt kê tất cả các cách điền thỏa mãn.

Input

Một số nguyên dương \(n\).

Output

Mỗi dòng in một cách điền: \(2n\) số theo thứ tự từ ô \(1\) đến ô \(2n\), cách nhau một dấu cách. Các cách điền được in theo thứ tự từ điển tăng dần.

Constraints

• \(1 \le n \le 8\) (với \(n\) lớn hơn, số cách điền quá nhiều nên bị loại khỏi giới hạn).

Sample Input

3

Sample Output

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

Explanation

Với cách đầu tiên: \(1+4=5\), \(4+3=7\), \(3+2=5\), \(2+5=7\), \(5+6=11\), \(6+1=7\), tất cả đều là số nguyên tố.

Cho hai số nguyên dương \(a\) và \(b\). Hãy tìm ước chung lớn nhất của chúng bằng thuật toán Euclid.

Input

Một dòng chứa hai số nguyên dương \(a\) và \(b\).

Output

In ra ước chung lớn nhất của \(a\) và \(b\).

Constraints

• \(1 \le a, b \le 10^{18}\)

Sample Input 1

12 18

Sample Output 1

6

Sample Input 2

7 7

Sample Output 2

7

Sample Input 3

100 25

Sample Output 3

25