#include <set>
#include <vector>
#include <iostream>

using namespace std;

template <typename RandomIt>
pair<RandomIt, RandomIt> FindStartsWith(RandomIt range_begin, RandomIt range_end, char prefix) {
    RandomIt it_begin = range_begin;
    RandomIt it_end = range_end;
    bool check1 = false;
    bool check2 = false;

    for (auto it = range_begin; it < range_end; ++it) {
        if (*((*it).begin()) == prefix) {
            it_begin = it;
            check1 = true;
            break;
        }
    }
    for (auto it = prev(range_end); it >= range_begin; --it) {
        if (*((*it).begin()) == prefix) {
            it_end = it;
            check2 = true;
            break;
        }
    }

    if (check1 && check2) {
        return make_pair(it_begin, it_end);
    }
    else {
        if ((int)prefix <= (int)(*((*range_begin).begin())))
            return make_pair(next(range_begin), next(range_begin));

        if ((int)prefix >= (int)(*((*prev(range_end)).begin())))
            return make_pair(range_end, range_end);

        for (auto it = range_begin; it < range_end - 1; ++it) {
            if ((int)prefix < (int)(*((*(it + 1)).begin())) &&
                (int)prefix >(int)(*((*(it)).begin()))) {
                return make_pair(next(it), next(it));
            }
        }
    }
    return make_pair(range_begin, range_end);
}

int main() {
    const vector<string> sorted_strings = { "moscow", "murmansk", "vologda", "xaoro", "zaero" };
    const auto m_result = FindStartsWith(begin(sorted_strings), end(sorted_strings), 'm');
    for (auto it = m_result.first; it <= m_result.second; ++it) {
        cout << *it << " ";
    }
    cout << endl;
    const auto p_result = FindStartsWith(begin(sorted_strings), end(sorted_strings), 'p');
    cout << (p_result.first - begin(sorted_strings)) << " " << (p_result.second - begin(sorted_strings)) << endl;

    const auto a_result = FindStartsWith(begin(sorted_strings), end(sorted_strings), 'a');
    cout << (a_result.first - begin(sorted_strings)) << " " << (a_result.second - begin(sorted_strings)) << endl;

    const auto n_result = FindStartsWith(begin(sorted_strings), end(sorted_strings), 'n');
    cout << (n_result.first - begin(sorted_strings)) << " " << (n_result.second - begin(sorted_strings)) << endl;

    const auto z_result = FindStartsWith(begin(sorted_strings), end(sorted_strings), 'z');
    cout << (z_result.first - begin(sorted_strings)) << " " << (z_result.second - begin(sorted_strings)) << endl;
    return 0;
}