#include <bits/stdc++.h>
using namespace std;
int main() {
  vector<int> v;
  int count = 0;
  while (count <= 1000) {
    for (int i = 1; i < 10; i++) {
      int x = 10 * i + (10 - i);
      v.push_back(x);
      count++;
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; (i + j <= 10); j++) {
        int x = (100) * i + (10 * j) + ((10 - i - j));
        v.push_back(x);
        count++;
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; i + j + k <= 10; k++) {
          int x = (1000 * i) + (100 * j) + (10 * k) + (10 - i - j - k);
          v.push_back(x);
          count++;
        }
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          for (int l = 0; i + j + k + l <= 10; l++) {
            int x = (10000 * i) + (1000 * j) + (100 * k) + (10 * l) +
                    (10 - i - j - k - l);
            v.push_back(x);
            count++;
          }
        }
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          for (int l = 0; l < 10; l++) {
            for (int m = 0; i + j + k + l + m <= 10; m++) {
              int x = (100000 * i) + (10000 * j) + (1000 * k) + (100 * l) +
                      (10 * m) + (10 - i - j - k - l - m);
              v.push_back(x);
              count++;
            }
          }
        }
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          for (int l = 0; l < 10; l++) {
            for (int m = 0; m < 10; m++) {
              for (int n = 0; i + j + k + l + m + n <= 10; n++) {
                int x = (1000000 * i) + (100000 * j) + (10000 * k) +
                        (1000 * l) + (100 * m) + (10 * n) +
                        (10 - i - j - k - l - m - n);
                v.push_back(x);
                count++;
              }
            }
          }
        }
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          for (int l = 0; l < 10; l++) {
            for (int m = 0; m < 10; m++) {
              for (int n = 0; n < 10; n++) {
                for (int o = 0; i + j + k + l + m + n + o <= 10; o++) {
                  int x = (10000000 * i) + (1000000 * j) + (100000 * k) +
                          (10000 * l) + (1000 * m) + (100 * n) + (10 * o) +
                          (10 - i - j - k - l - m - n - o);
                  v.push_back(x);
                  count++;
                }
              }
            }
          }
        }
      }
    }
  }
  int n;
  cin >> n;
  cout << v[n - 1];
}

### Prompt

Please provide a Cpp coded solution 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;
int main() {
  vector<int> v;
  int count = 0;
  while (count <= 1000) {
    for (int i = 1; i < 10; i++) {
      int x = 10 * i + (10 - i);
      v.push_back(x);
      count++;
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; (i + j <= 10); j++) {
        int x = (100) * i + (10 * j) + ((10 - i - j));
        v.push_back(x);
        count++;
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; i + j + k <= 10; k++) {
          int x = (1000 * i) + (100 * j) + (10 * k) + (10 - i - j - k);
          v.push_back(x);
          count++;
        }
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          for (int l = 0; i + j + k + l <= 10; l++) {
            int x = (10000 * i) + (1000 * j) + (100 * k) + (10 * l) +
                    (10 - i - j - k - l);
            v.push_back(x);
            count++;
          }
        }
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          for (int l = 0; l < 10; l++) {
            for (int m = 0; i + j + k + l + m <= 10; m++) {
              int x = (100000 * i) + (10000 * j) + (1000 * k) + (100 * l) +
                      (10 * m) + (10 - i - j - k - l - m);
              v.push_back(x);
              count++;
            }
          }
        }
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          for (int l = 0; l < 10; l++) {
            for (int m = 0; m < 10; m++) {
              for (int n = 0; i + j + k + l + m + n <= 10; n++) {
                int x = (1000000 * i) + (100000 * j) + (10000 * k) +
                        (1000 * l) + (100 * m) + (10 * n) +
                        (10 - i - j - k - l - m - n);
                v.push_back(x);
                count++;
              }
            }
          }
        }
      }
    }
    for (int i = 1; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          for (int l = 0; l < 10; l++) {
            for (int m = 0; m < 10; m++) {
              for (int n = 0; n < 10; n++) {
                for (int o = 0; i + j + k + l + m + n + o <= 10; o++) {
                  int x = (10000000 * i) + (1000000 * j) + (100000 * k) +
                          (10000 * l) + (1000 * m) + (100 * n) + (10 * o) +
                          (10 - i - j - k - l - m - n - o);
                  v.push_back(x);
                  count++;
                }
              }
            }
          }
        }
      }
    }
  }
  int n;
  cin >> n;
  cout << v[n - 1];
}

```