#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T1,typename T2>
using ordered_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>;
using trie_type=trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>;

void print_prefix_match(const trie_type& t, const string& key)
{
    typedef trie_type::const_iterator       const_iterator;
    typedef pair<const_iterator, const_iterator>    pair_type;

    cout << "All keys whose prefix matches \"" << key << "\":" << endl;

    const pair_type match_range = t.prefix_range(key);
    for (const_iterator it = match_range.first; it != match_range.second; ++it)
        cout << *it << ' ';
    cout << endl;
}
int main()
{
    ordered_set<int>  s;
    s.insert(1);
    s.insert(3);
    cout << s.order_of_key(2) << endl; // the number of elements in the s less than 2
    cout << *s.find_by_order(0) << endl; // print the 0-th smallest number in s(0-based)
    trie_type t;

    // Insert some entries.
    t.insert("I");
    assert(t.insert("wish").second == true);
    assert(t.insert("that").second == true);
    assert(t.insert("I").second == false);
    assert(t.insert("could").second == true);
    assert(t.insert("ever").second == true);
    assert(t.insert("see").second == true);
    assert(t.insert("a").second == true);
    assert(t.insert("poem").second == true);
    assert(t.insert("lovely").second == true);
    assert(t.insert("as").second == true);
    assert(t.insert("a").second == false);
    assert(t.insert("trie").second == true);

    // Now search for prefixes.
    print_prefix_match(t, "");
    print_prefix_match(t, "a");
    print_prefix_match(t, "as");
    print_prefix_match(t, "ad");
    print_prefix_match(t, "t");
    print_prefix_match(t, "tr");
    print_prefix_match(t, "trie");
    print_prefix_match(t, "zzz");
}