Distinct Digits

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Let’s call a pair of numbers \((x, y)\) good if they do not share any common digit. For example, the pairs (47, 1093) or (4444, 7777) are good, while the pairs (10, 231) or (47, 74) are not.

Let \(f(l, r)\) be the number of good pairs such that \(l \le x < y \le r\).

Zenyk has a number \(n\). He is interested in whether there exist such \(l\) and \(r\) that \(f(l, r) = n\) and \(1 \le l \le r \le 10^{18}\). Help him find the answer to this question.

Input

The single line contains a single integer \(n\).

Output

If there is no pair \(l, r\) that satisfies the condition, output -1. Otherwise, output two numbers \(l\) and \(r\). If there are multiple pairs that satisfy the conditions — output any.

Constraints

\(1 \le n \le 10^{16}\).

Samples