#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

template <typename RandomIt>
pair<RandomIt, RandomIt> FindStartsWith(RandomIt range_begin, RandomIt range_end,
                                        const string& prefix){
    // на случай пустого вектора
    if (range_begin == range_end) return make_pair(range_begin, range_end);

    auto itBegin = lower_bound(range_begin, range_end, prefix);
    // далее манипуляции с prefix
    string temp = (*itBegin).substr(0, prefix.length());
    // если слово с префиксом есть...
    if (temp == prefix) {
        string postprefix = prefix;
        ++postprefix[postprefix.length() - 1];

        auto itEnd = upper_bound(range_begin, range_end, postprefix);

        return make_pair(itBegin, itEnd);
    // если слова с таким префиксом нет, то надо вставить перед
    // ближайшим к префиксу
    } else return make_pair(itBegin, itBegin);

}