Amazing Four-Digit Numbers

Time limit1sMemory limit128 MB

Summary

Print every four-digit number whose digit sum is the same when written in base 10, base 12, and base 16.

Level: Medium4 of 10
Topics: Implementation, Number theory, Brute force
Solved: No attempts yet

Problem

Write a four-digit number $n$ ( $1000 \le n \le 9999$ ) in base 10, base 12, and base 16. If the sum of its digits is the same in all three bases, then $n$ is called an amazing four-digit number.

Find every amazing four-digit number and print them in ascending order.

Input

There is no input.

Output

Print every amazing four-digit number in ascending order, one per line.

Hint

The smallest amazing four-digit number is $2992$ .

Examples6

Example 1

Input

Expected output

Example 2

Input

Expected output

Example 3

Input

Expected output

Example 4

Input

Expected output

Example 5

Input

Expected output

Example 6

Input

Expected output