A. Digits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The magical Andy loves the number $$$9$$$. Because of this, he wants every number he sees to be divisible by $$$9$$$.

Andy possesses a special magical ability: he can rearrange the digits of a number in any order he wants. Note that Andy's number cannot have leading 0's before or after rearrangement.

Andy's friend Bob gives him a number. Andy wants to determine whether it is possible to rearrange its digits so that the resulting number is divisible by $$$9$$$.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 100)$$$ — the number Bob gives him.

—

Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Tests $$$1-20$$$ satisfy no additional constraints.

Output
  • Print a rearranged number divisible by $$$9$$$ if it is possible, or
  • Print $$$-1$$$ if it is impossible.

If multiple answers exist, print any.

Examples
Input
7
Output
-1
Input
81
Output
18
Note

Explanation for the sample cases:

In test case 1, it can be shown it is impossible to rearrange 7 to make a multiple of 9.

In test case 2, 81 can be rearranged to form 18, and 18 is divisible by 9.

—

Problem Idea: culver0412

Problem Preparation: justin_g_20

Occurrences: Novice A, Advanced A