Dãy Fibonacci là dãy gồm các số: 1, 1, 2, 3, 5, 8, … được xác định bởi công thức sau: ~F_1 = 1, F_2 = 1~; ~F_i = F_{i-1} + F_{i-2}~, với ~i > 2~.

Hãy biểu diễn một số tự nhiên ~N~ thành tổng ít nhất các số Fibonacci khác nhau.

Input

• Đọc từ file văn bản chứa số ~N~ (~1 \le N \le 10^9~).

Output

• Ghi ra biểu diễn số ~N~ thành tổng ít nhất các số Fibonacci khác nhau. Các số ghi trên cùng một dòng theo thứ tự từ lớn đến bé và cách nhau một dấu cách.

Sample Input 1

29

Sample Output 1

21 8

Nhằm chuẩn bị tốt cho kỳ thi tuyển sinh vào lớp 10 chuyên, thầy Cường yêu cầu học trò của mình phải nắm chắc kiến thức đã học. Để khảo sát chất lượng học sinh về nội dung xâu kí tự, thầy đưa ra bài toán cụ thể như sau: Cho trước một xâu kí tự ~S~, có thể chứa các chữ cái, chữ số và dấu cách.

Hãy loại bỏ một số kí tự ra khỏi xâu sao cho 6 kí tự còn lại theo đúng thứ tự đó tạo thành số lớn nhất.

Input

• Đọc từ file văn bản gồm một dòng chứa xâu ~S~ cho trước (~S~ không quá 300 ký tự).

Output

• Dòng thứ nhất chứa 6 kí tự số cần tìm theo yêu cầu;
• Dòng thứ hai là một số nguyên thể hiện tổng của 6 kí tự số trên.
• Trong trường hợp xâu cho trước hoặc các kí tự số còn lại không đủ 6 kí tự thì ghi -1.

Sample Input 1

23459225

Sample Output 1

459225
27

Nhân ngày Quốc tế thiếu nhi, trường THCS ABC tổ chức trao quà cho các lớp. Phần quà thứ ~i~ có giá trị ~a_i~, mỗi lớp có thể nhận tối đa là ~N~ phần quà. Các phần quà được xếp ngẫu nhiên theo thứ tự: ~a_1, a_2, \dots, a_N~ (~1 \le a_i \le 10^6~).

Theo quy định của nhà trường, quà được nhận là một dãy liên tiếp các phần quà mà trong đó tồn tại ít nhất một phần quà có giá trị lớn hơn hoặc bằng ~M~.

Hãy đếm xem có bao nhiêu cách chọn quà theo yêu cầu của nhà trường.

Input

• Dòng thứ nhất ghi 2 số nguyên ~N, M~. Các số cách nhau bởi một dấu cách (~1 \le N, M \le 10^6~);
• Dòng thứ hai ghi ~N~ số nguyên là các giá trị của phần quà thứ ~i~. Các số cách nhau bởi một dấu cách.

Output

• Ghi ra một số duy nhất là kết quả cần tìm.

Sample Input 1

3 4
2 3 5

Sample Output 1

3

Để quảng bá cho sản phẩm mới, cửa hàng trưng bày quần áo Fashion trang trí áo vào ~n~ con ma-nơ-canh khác nhau. Hiện tại, cửa hàng có ~m~ chiếc áo và được xếp trên ~m~ hàng. Với mỗi chiếc áo thứ ~i~ ta biết giá trị thẩm mĩ khi mặc áo vào con ma-nơ-canh thứ ~j~ là ~V_{ij}~. Các giá trị thẩm mĩ được bố trí trên ~m~ hàng và ~n~ cột.

Hãy xác định phương án mặc hết áo vào các con ma-nơ-canh để tổng giá trị thẩm mĩ là cao nhất.

Input

• Dòng đầu tiên ghi 2 số ~m, n~ (~i = 1, 2, \dots, m~; ~j = 1, 2, \dots, n~; ~1 \le m, n \le 10^3~);
• ~m~ dòng tiếp theo, mỗi dòng ghi ~n~ số nguyên là các giá trị thẩm mĩ ~V_{ij}~ (~1 \le V_{ij} \le 10^4~).

Output

• Dòng thứ nhất ghi tổng giá trị thẩm mĩ của phương án mặc áo cho ma-nơ-canh;
• Dòng thứ 2 là dãy ~m~ số hiệu con ma-nơ-canh được chọn cho mỗi chiếc áo đã mặc. Các số hiệu được ghi cách nhau bởi dấu cách.

Sample Input 1

1 8
16 37 12 39 41 31 45 16

Sample Output 1

45
7