#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;
int main() {
vector<string> data = {"quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"};
vector<string> s;
for (int i = 0 ; i != data.size() ; i++) {
s.insert(upper_bound(s.begin(), s.end(), data[i]), data[i]);
}
for (int i = 0 ; i != s.size() ; i++) {
cout << s[i] << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8aXRlcmF0b3I+CiNpbmNsdWRlIDxzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCXZlY3RvcjxzdHJpbmc+IGRhdGEgPSB7InF1aWNrIiwgImJyb3duIiwgImZveCIsICJqdW1wcyIsICJvdmVyIiwgInRoZSIsICJsYXp5IiwgImRvZyJ9OwoJdmVjdG9yPHN0cmluZz4gczsKCWZvciAoaW50IGkgPSAwIDsgaSAhPSBkYXRhLnNpemUoKSA7IGkrKykgewoJCXMuaW5zZXJ0KHVwcGVyX2JvdW5kKHMuYmVnaW4oKSwgcy5lbmQoKSwgZGF0YVtpXSksIGRhdGFbaV0pOwoJfQogICAgZm9yIChpbnQgaSA9IDAgOyBpICE9IHMuc2l6ZSgpIDsgaSsrKSB7CiAgICAJY291dCA8PCBzW2ldIDw8IGVuZGw7CiAgICB9CglyZXR1cm4gMDsKfQ==