Mua chuối

Đề bài : https://drive.google.com/drive/u/0/folders/1Kv0RDJiibCQ0803c6lLIrQyRnDZVEzht

Marvel có vũ trụ Avengers, Warner Bros có vũ trụ DC, HOU cũng có 1 vũ trụ riêng, đó là vũ trụ của Cà và Khịa. Sau khi bị phạt bật cóc, đùi của Cà và Khịa bắt đầu có hiện tượng đau cơ. Theo tìm hiểu Cà biết được ăn chuối rất tốt cho cơ bắp, vì thế Cà đã rủ khịa cùng đi mua chuối.

Khi đến cửa hàng chủ cửa hàng đưa ra một loạt các nải chuối, nhưng các nải chuối này rất buồn cười, Cà bảo với Khịa: "Năm nay tôi gần 20 tuổi rồi mà tôi chưa gặp cái trường hợp nào mà nó như thế này cả". Các nải chuối buồn cười ở chỗ, mỗi nải chuối có số lượng quả chuối dạng ~3^k~, ~VD: 1,3,9, 27,…~ và mỗi quả lại nặng tới 1 ~kg~, không có 2 nải chuối cùng số lượng quả. Hiện tại trong balo của Cà đang có sẵn một vật nặng ~N ~ ~ kg~, Cà và Khịa muốn mua các nải chuối sao cho khối lượng 2 người phải mang là như nhau và nhỏ nhất. Hãy giúp Cà và Khịa tính toán các nải chuối cần mua, giả định cửa hàng có tất cả các nải chuối có số lượng quả dạng ~3^k~.

Input

Một dòng duy nhất chứa số nguyên ~N~, là khối lượng vật năng sẵn có trong balo của Cà ~(0 \leq N \leq 10^8)~

Output

Gồm 3 dòng

Dòng đầu chứa số nguyên ~M~, là khối lượng nhỏ nhất Cà và Khịa phải mang về

Dòng thứ 2 chứa ~P~, theo sau là ~P~ số nguyên theo thứ tự tăng dần, số thứ ~i~ là số lượng chuối của nải thứ ~i~ mà Cà mua

Dòng thứ 3 chứa ~Q~, theo sau là ~Q~ số nguyên theo thứ tự tăng dần, số thứ ~i~ là số lượng chuối của nải thứ ~i~ mà Khịa mua

Nếu có nhiều kết quả hợp lệ, in ra quả bất kì

Sample Input

42

Sample Output

81
3 3 9 27
1 81

Giải thích:

Ban đầu trong ba lô của Cà sẵn có 1 vật năng 42kg, Cà mua 3 nải chuối với số lượng chuối của từng nải lần lượt là 3,9, 27. Khịa mua 1 nải chuối với số lượng là 81. Vì thế thế khối lượng mà Cà và Khịa phải mang là 81kg

Xoắn là một cậu bé rất thích những bài tập về chuỗi, cậu cảm thấy thoải mái khi loại bỏ những kí tự ở đầu chuỗi, hoặc cuối chuỗi, nhưng lại rất ghét khi phải loại bỏ các kí tự ở giữa chuỗi, tức là những kí tự không phải ở đầu hoặc cuối chuỗi.

Một hôm Trâu có cho cậu một chuỗi toàn kí tự 'D', 'H' và 'A', Trâu đố Xoắn tìm được chuỗi con ngắn nhất của chuỗi vừa cho, sao cho chuỗi con đó có ít nhất k kí tự 'D', k kí tự 'H' và k kí tự 'A . Xoắn thừa sức làm bài ez như vậy, xoắn thêm yêu cầu cho bản thân là chuỗi con đó có thể chuyển thành chuỗi có đúng k kí tự 'D', k kí tự 'H' và k kí tự 'A' bằng cách chỉ sử dụng ba loại thao tác xóa kí tự ở đầu/cuối/giữa chuỗi và số lần phải xóa kí tự ở giữa là ít nhất.

X là chuỗi con của Y là một chuỗi gồm các kí tự liên tiếp của Y

Input

Dòng đầu tiên chứa số k ~(1 \le k \le n/3) ~.

Dòng thứ 2 chuỗi s chỉ gồm các kí tự thuộc tập {'D', 'H', 'A'} có độ dài là n ~(1 \le n \le 2.10^5 )~

Output

In ra số lần phải xóa kí tự ở giữa, nếu k có chuỗi con nào thỏa mãn in ra -1.

Sample Input 1

2
DHHDHADHHAAAHD

Sample Output 1

1

Giải thích IN/OUTPUT 1 :

Chuỗi con Xoắn sẽ tìm được là "DHADHHA" chỉ phải loại thực hiện 1 thao tác xóa ở giữa là tại vị trí 2 thành chuỗi "DADHHA" có đúng 2 kí tự 'D', 2 kí tự 'H' và 2 kí tự 'A'