Cho xâu s chỉ chứa 3 kí tự 'A', 'M', 'N'.

Đếm số xâu con không rỗng của s mà chứa số kí tự mỗi loại là bằng nhau.

VD:

Input

NNAANNMMAN

Output:

3

Có 1 cân đĩa và các quả cân có khối lượng 1, 3, 3^2, 3^3, 3^4, 3^5, 3^6,... (Mỗi mức khối lượng chỉ có 1 quả)

Tìm cách cân vật có khối lượng n.

Input

• Số nguyên dương n (n ≤ ${10}^{18}$).

Output

• Dòng đầu ghi ra các quả cân để bên đĩa không có vật cần cân;
• Dòng thứ hai ghi các quả cân để bên đĩa cùng với vật cần cân (nếu có)

Các số trên một dòng ghi theo thứ tự từ nhỏ đến lớn.

Ví dụ:

Input

11

Output

3 9
1

Giải thích:

11 + 1 = 3 + 9

Ví dụ 2:

Input

10

Output

1 9

Cho xâu s gồm các chữ số và số T. Chèn các dấu + hoặc - vào giữa xâu s (không để 2 dấu liên tiếp) để được biểu thức có giá trị bằng T. (xâu s có không quá 18 kí tự)

Chỉ ghi ra có bao nhiêu cách điền.

INPUT

2321
2

OUTPUT

3

Giải thích:

Có 3 cách điền dấu:

2+3-2-1

23-21

2-3+2+1

Một chuỗi đá quý kết nối thành vòng tròn. Bạn hãy tìm cách bỏ đi một số viên đá để vòng đá còn lại, theo chiều kim đồng hồ, có giá trị tăng dần (tính từ một vị trí nào đó).

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương n ≤ 10^4;
• Dòng tiếp theo chứa n số nguyên dương a1, a2,…, an là giá trị lần lượt của các viên đá (theo chiều kim đồng hồ). (ai ≤ 10^9)

Kết quả: ghi ra số viên đá ít nhất phải loại bỏ để thỏa mãn yêu cầu.

Ví dụ

Input

6
2 6 1 7 3 4

Output

2

Giải thích ví dụ:

Loại bỏ 2 viên có giá trị 2 và 7. Vòng còn lại là 1, 3, 4, 6.

Cũng có cách khác là bỏ 2 viên giá trị 1 và 2. Khi đó, vòng còn lại là 3, 4, 6, 7.

Nguồn