XẾP DIÊM – SỐ LỚN NHẤT CHIA HẾT CHO 3

Bờm là một người rất thích chơi trò xếp diêm.

Từ các que diêm, Bờm có thể xếp được các chữ số từ 0 đến 9. Số que diêm cần dùng để xếp mỗi chữ số được cho trong bảng sau:

Cho trước n que diêm. Hãy sử dụng đúng n que diêm để xếp thành một số nguyên dương lớn nhất chia hết cho 3.

Nếu không thể xếp được số thỏa mãn, hãy in ra -1.

Dữ liệu vào

Gồm một dòng duy nhất chứa số nguyên n — số que diêm Bờm có.

Kết quả

In ra số nguyên dương lớn nhất chia hết cho 3 có thể xếp được bằng đúng n que diêm.

Nếu không thể xếp được số thỏa mãn, in ra -1.

Giới hạn

1 ≤ n ≤ 10^5

Ví dụ 1

Dữ liệu vào

5

Kết quả

3

Ví dụ 2

Dữ liệu vào

6

Kết quả

111

Giải thích

• Với n = 5, có thể xếp chữ số 3 bằng đúng 5 que diêm. Số 3 chia hết cho 3.
• Với n = 6, có thể xếp số 111 bằng đúng 6 que diêm. Ta có 111 > 9, vì vậy đáp án là 111.