#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const int maxn = 2e5 + 100;
int k;
vector<int> ans;
void dfs(int len, int now, int sum) {
  if (len > 8 || sum > 10) return;
  if (sum == 10) {
    ans.push_back(now);
  }
  for (int i = (len == 0); i < 10; i++) {
    dfs(len + 1, now * 10 + i, sum + i);
  }
}
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> k;
  dfs(0, 0, 0);
  sort(ans.begin(), ans.end());
  cout << ans[k - 1] << endl;
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

We consider a positive integer perfect, if and only if the sum of its digits is exactly 10. Given a positive integer k, your task is to find the k-th smallest perfect positive integer.

Input

A single line with a positive integer k (1 ≤ k ≤ 10 000).

Output

A single number, denoting the k-th smallest perfect integer.

Examples

Input

1


Output

19


Input

2


Output

28

Note

The first perfect integer is 19 and the second one is 28.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const int maxn = 2e5 + 100;
int k;
vector<int> ans;
void dfs(int len, int now, int sum) {
  if (len > 8 || sum > 10) return;
  if (sum == 10) {
    ans.push_back(now);
  }
  for (int i = (len == 0); i < 10; i++) {
    dfs(len + 1, now * 10 + i, sum + i);
  }
}
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> k;
  dfs(0, 0, 0);
  sort(ans.begin(), ans.end());
  cout << ans[k - 1] << endl;
  return 0;
}

```