Cho một mảng A các số nguyên gồm N phần tử. Sắp xếp các phần tử trong mảng A theo tổng chữ số trong một phần tử tăng dần. Nếu 2 số có cùng tổng chữ số thì số nào nhỏ hơn in ra trước.

Ràng buộc: ~1 \leq N \leq 2.10^5~; ~1 \leq A[i] \leq 10^9~

input:

7
100 101 1 2 400 4 202

Output:

1 100 2 101 4 202 400

Cho một xâu S gồm các chữ cái in thường, tìm xâu con liên tiếp ngắn nhất chứa đầy đủ các ký tự của S và in ra. Ví dụ xâu S = "abcaaaabcda" thì xâu con "bcda" là xâu con nhỏ nhất chứa đầy đủ các ký tự của S.

Ràng buộc: ~0 < len(S) \leq 10^6~

Input:

abcaaadabcda

Output:

bcda

Giải thích: Xâu con ngắn nhất chứa đầy đủ các ký tự của S là xâu bcda

Hoàng yêu thích các số may mắn. Ta biết rằng một số là số may mắn nếu biểu diễn thập phân của nó chỉ chứa các chữ số may mắn là 4 và 7. Ví dụ, các số 47, 744, 4 là số may mắn và 5, 17, 467 không phải. Hoàng muốn tìm số may mắn bé nhất có tổng các chữ số bằng n. Hãy giúp anh ấy.

Đầu vào: Dòng duy nhất chứa số nguyên dương n

Ràng buộc: 1<=n<=10^6;

Đầu ra: In ra đáp án của bài toán, nếu không tồn tại đáp án thì in ra -1

Input:

16

Output:

4444