#include <bits/stdc++.h>
using namespace std;
double tick() {
  static clock_t oldt, newt = clock();
  double diff = 1.0 * (newt - oldt) / CLOCKS_PER_SEC;
  oldt = newt;
  return diff;
}
long long mod(long long n, long long m = 1000000007) {
  if (n < 0) {
    return (m - abs(n) % m) % m;
  } else
    return n % m;
}
long long power(long long a, long long n) {
  if (n == 0) return 1;
  if (n == 1) return a;
  if (n == 2) return a * a;
  if (n & 1) {
    n--;
    return a * power(power(a, 2), n / 2);
  } else
    return power(power(a, 2), n / 2);
}
vector<long long> isPrime(1000001, true), prime, spf(1000001);
void sieve(long long n) {
  isPrime[0] = isPrime[1] = false;
  for (long long i = 2; i < n; i++) {
    if (isPrime[i]) {
      prime.push_back(i);
      spf[i] = i;
    }
    for (long long j = 0;
         j < prime.size() && i * prime[j] < n && prime[j] <= spf[i]; j++) {
      isPrime[i * prime[j]] = false;
      spf[i * prime[j]] = prime[j];
    }
  }
}
bool check(long long n) {
  string s = to_string(n);
  long long count = 0;
  for (auto& i : s) {
    long long x = i - '0';
    count += x;
  }
  if (count == 10) return true;
  return false;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t = 1;
  while (t--) {
    long long k;
    cin >> k;
    long long start = 19, cnt = 0;
    while (cnt < k) {
      if (check(start)) cnt++;
      if (cnt == k) break;
      start += 9;
    }
    cout << start << '\n';
  }
  cerr << "\nExecution time: " << tick() * 1000 << " ms" << '\n';
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

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;
double tick() {
  static clock_t oldt, newt = clock();
  double diff = 1.0 * (newt - oldt) / CLOCKS_PER_SEC;
  oldt = newt;
  return diff;
}
long long mod(long long n, long long m = 1000000007) {
  if (n < 0) {
    return (m - abs(n) % m) % m;
  } else
    return n % m;
}
long long power(long long a, long long n) {
  if (n == 0) return 1;
  if (n == 1) return a;
  if (n == 2) return a * a;
  if (n & 1) {
    n--;
    return a * power(power(a, 2), n / 2);
  } else
    return power(power(a, 2), n / 2);
}
vector<long long> isPrime(1000001, true), prime, spf(1000001);
void sieve(long long n) {
  isPrime[0] = isPrime[1] = false;
  for (long long i = 2; i < n; i++) {
    if (isPrime[i]) {
      prime.push_back(i);
      spf[i] = i;
    }
    for (long long j = 0;
         j < prime.size() && i * prime[j] < n && prime[j] <= spf[i]; j++) {
      isPrime[i * prime[j]] = false;
      spf[i * prime[j]] = prime[j];
    }
  }
}
bool check(long long n) {
  string s = to_string(n);
  long long count = 0;
  for (auto& i : s) {
    long long x = i - '0';
    count += x;
  }
  if (count == 10) return true;
  return false;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t = 1;
  while (t--) {
    long long k;
    cin >> k;
    long long start = 19, cnt = 0;
    while (cnt < k) {
      if (check(start)) cnt++;
      if (cnt == k) break;
      start += 9;
    }
    cout << start << '\n';
  }
  cerr << "\nExecution time: " << tick() * 1000 << " ms" << '\n';
  return 0;
}

```