Bài tập

Một xâu là đối xứng (palindrome) nếu đọc từ trái sang phải hay từ phải sang trái đều cho cùng một kết quả, ví dụ madam, civic, a.

Cho xâu \(S\). Ta có thể cắt \(S\) tại một số vị trí (có thể không cắt) để chia thành các đoạn liên tiếp. Hãy liệt kê mọi cách cắt sao cho mọi đoạn thu được đều là xâu đối xứng.

Input

Một dòng duy nhất chứa xâu \(S\) gồm các chữ cái Latinh thường.

Output

In mỗi cách cắt trên một dòng: các đoạn theo thứ tự từ trái sang phải, cách nhau đúng một dấu cách. Các cách cắt được in theo thứ tự sau: so sánh hai cách cắt từ trái sang phải, đoạn đầu tiên nào ngắn hơn thì cách cắt đó đứng trước (nếu hai đoạn đầu bằng nhau thì so sánh tiếp đoạn thứ hai, v.v.).

Constraints

• \(1 \le |S| \le 30\), \(S\) gồm chữ cái thường a-z.
• Để kết quả không quá lớn, đảm bảo số cách cắt hợp lệ không vượt quá \(10^5\).

Sample Input 1

civicab

Sample Output 1

c i v i c a b
c ivi c a b
civic a b

Sample Input 2

aabaa

Sample Output 2

a a b a a
a a b aa
a aba a
aa b a a
aa b aa
aabaa

Cho một tờ giấy hình chữ nhật kích thước \(A \times B\) (đơn vị nguyên). Người ta muốn cắt hết tờ giấy thành các hình vuông bằng nhau, không được thừa mảnh nào và không được ghép lại. Hãy tìm số hình vuông ít nhất có thể cắt được.

Input

• Một dòng chứa hai số nguyên dương \(A, B\).

Output

• In ra một số nguyên duy nhất: số hình vuông ít nhất.

Constraints

• \(1 \le A, B \le 4 \cdot 10^9\)

Sample Input 1

6 9

Sample Output 1

6

Sample Input 2

5 5

Sample Output 2

1

Explanation

Ví dụ 1: cạnh hình vuông lớn nhất có thể là \(\gcd(6,9)=3\), khi đó số hình vuông là \((6/3)\cdot(9/3)=6\).

Ba số nguyên \(p, q, r\) được viết theo đúng thứ tự cho trước. Ba số này được gọi là lập thành cấp số nhân nếu số ở giữa có bình phương bằng tích của hai số còn lại, tức là \(q^2 = p \cdot r\).

Cho ba số nguyên \(p, q, r\) thỏa mãn \(p < q < r\) và cả ba đều khác \(0\). Hãy cho biết ba số đó, theo thứ tự đã cho, có lập thành cấp số nhân hay không.

Input

• Một dòng chứa ba số nguyên \(p, q, r\) cách nhau bởi dấu cách.

Output

• In ra YES nếu ba số lập thành cấp số nhân, ngược lại in ra NO.

Constraints

• \(p < q < r\)
• \(p, q, r \ne 0\)
• \(|p|, |q|, |r| \le 10^9\)

Sample Input 1

3 6 12

Sample Output 1

YES

Sample Input 2

-9 -6 -5

Sample Output 2

NO

Explanation

Ở ví dụ 1: \(6^2 = 36 = 3 \cdot 12\). Ở ví dụ 2: \((-6)^2 = 36\) nhưng \((-9)\cdot(-5) = 45\).

Cho dãy số nguyên không âm \(A_1, A_2, \ldots, A_n\). Một cặp chỉ số \((i, j)\) được gọi là cặp gấp năm nếu thỏa mãn đồng thời:

• \(i < j\);
• \(A_i = 5 \cdot A_j\).

Hãy đếm số cặp gấp năm trong dãy.

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \ldots, A_n\).

Output

• In ra một số nguyên duy nhất là số cặp gấp năm.

Constraints

• Subtask 1 (60% số điểm): \(n \le 10^3\), \(0 \le A_i \le 10^9\).
• Subtask 2 (40% số điểm): \(n \le 3 \cdot 10^5\), \(0 \le A_i \le 10^{18}\).

Sample Input 1

6
10 2 50 2 10 10

Sample Output 1

4

Explanation

Các cặp thỏa mãn: \((1,2)\), \((1,4)\) (cùng có \(10 = 5 \cdot 2\)) và \((3,5)\), \((3,6)\) (cùng có \(50 = 5 \cdot 10\)).