#include <bits/stdc++.h>
using namespace std;

vector<vector<string>> getProductSuggestions(vector<string>& products, const string& search) {
    // Sort products lexicographically
    sort(products.begin(), products.end());
    vector<vector<string>> results;
    string prefix = "";

    // Build up the prefix from each character in 'search'
    for (char ch : search) {
        prefix += ch;
        vector<string> matches;

        // Using binary search to optimize finding the start of matching products
        auto it = lower_bound(products.begin(), products.end(), prefix);

        // Collect up to 3 matches that start with the current prefix
        for (int i = 0; i < 3 && it + i != products.end(); i++) {
            string& product = *(it + i);
            if (product.find(prefix) == 0) {  // starts with 'prefix'
                matches.push_back(product);
            } else {
                break;
            }
        }

        // Add matches for this prefix to results
        results.push_back(matches);
    }

    return results;
}

int main() {
    vector<string> products = {"mobile", "mouse", "moneypot", "monitor", "mousepad"};
    string search = "mouse";

    vector<vector<string>> result = getProductSuggestions(products, search);

    // Display results
    for (const auto& suggestions : result) {
        for (const auto& suggestion : suggestions) {
            cout << suggestion << " ";
        }
        cout << endl;
    }

    return 0;
}