#include <random>
#include <vector>
#include <unordered_map>
 
template<class Int, class Generator>
std::vector<Int> randomSample(Int amt, Int lim, Generator& g) {
  std::unordered_map<Int, Int> shuffle;  // Note: there are much better hash table implementations than std's
  for (Int i=1; i<=amt; ++i) {
    Int c = std::uniform_int_distribution<Int>(i, lim)(g);
    if (!shuffle.count(c))
      shuffle[c] = c;
    if (!shuffle.count(i))
      shuffle[i] = i;
    std::swap(shuffle[i], shuffle[c]);
  }
  std::vector<Int> ans;
  for (Int i=1; i<=amt; ++i)
    ans.push_back(shuffle[i]);
  return ans;
}
 
#include <iostream>
#include <algorithm>
 
int main() {
  std::random_device rd;
  std::mt19937 gen(rd());
  std::vector<int> sample = randomSample(100, 3000, gen);
  for (int i=0; i<sample.size(); ++i)
    std::cout << sample[i] << ' ';
  std::cout << std::endl;
  std::sort(sample.begin(), sample.end());
  for (int i=0; i<sample.size(); ++i)
    std::cout << sample[i] << ' ';
  std::cout << std::endl;
}

I2luY2x1ZGUgPHJhbmRvbT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHVub3JkZXJlZF9tYXA+Cgp0ZW1wbGF0ZTxjbGFzcyBJbnQsIGNsYXNzIEdlbmVyYXRvcj4Kc3RkOjp2ZWN0b3I8SW50PiByYW5kb21TYW1wbGUoSW50IGFtdCwgSW50IGxpbSwgR2VuZXJhdG9yJiBnKSB7CiAgc3RkOjp1bm9yZGVyZWRfbWFwPEludCwgSW50PiBzaHVmZmxlOyAgLy8gTm90ZTogdGhlcmUgYXJlIG11Y2ggYmV0dGVyIGhhc2ggdGFibGUgaW1wbGVtZW50YXRpb25zIHRoYW4gc3RkJ3MKICBmb3IgKEludCBpPTE7IGk8PWFtdDsgKytpKSB7CiAgICBJbnQgYyA9IHN0ZDo6dW5pZm9ybV9pbnRfZGlzdHJpYnV0aW9uPEludD4oaSwgbGltKShnKTsKICAgIGlmICghc2h1ZmZsZS5jb3VudChjKSkKICAgICAgc2h1ZmZsZVtjXSA9IGM7CiAgICBpZiAoIXNodWZmbGUuY291bnQoaSkpCiAgICAgIHNodWZmbGVbaV0gPSBpOwogICAgc3RkOjpzd2FwKHNodWZmbGVbaV0sIHNodWZmbGVbY10pOwogIH0KICBzdGQ6OnZlY3RvcjxJbnQ+IGFuczsKICBmb3IgKEludCBpPTE7IGk8PWFtdDsgKytpKQogICAgYW5zLnB1c2hfYmFjayhzaHVmZmxlW2ldKTsKICByZXR1cm4gYW5zOwp9CgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxhbGdvcml0aG0+CgppbnQgbWFpbigpIHsKICBzdGQ6OnJhbmRvbV9kZXZpY2UgcmQ7CiAgc3RkOjptdDE5OTM3IGdlbihyZCgpKTsKICBzdGQ6OnZlY3RvcjxpbnQ+IHNhbXBsZSA9IHJhbmRvbVNhbXBsZSgxMDAsIDMwMDAsIGdlbik7CiAgZm9yIChpbnQgaT0wOyBpPHNhbXBsZS5zaXplKCk7ICsraSkKICAgIHN0ZDo6Y291dCA8PCBzYW1wbGVbaV0gPDwgJyAnOwogIHN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CiAgc3RkOjpzb3J0KHNhbXBsZS5iZWdpbigpLCBzYW1wbGUuZW5kKCkpOwogIGZvciAoaW50IGk9MDsgaTxzYW1wbGUuc2l6ZSgpOyArK2kpCiAgICBzdGQ6OmNvdXQgPDwgc2FtcGxlW2ldIDw8ICcgJzsKICBzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwp9