#include <iostream>
#include <iomanip>

// 原则上不要直接引用这个头文件，这里只是为了测试
#include <bits/stl_tree.h>

using namespace std;

struct Node {
    int first, second;
    Node(int _first, int _second) : first(_first), second(_second){};

    friend ostream& operator<<(ostream& outs, const Node& node) {
        outs << '{' << node.first << ',' << node.second << '}';
        return outs;
    }
};

template <class T>
struct Selector {
    // MUST return const int&, not int.
    // if return int, segmentation fault will occur.
    // I have spent much time because of this.
    const int& operator()(const T& obj) const {
        return obj.first;
    }
};

int main() {
    // _Rb_tree: red-black tree in STL.
    using tree_type = _Rb_tree<int, Node, Selector<Node>, less<int>>;
    using iterator_type = tree_type::iterator;
    using result_pair_type = pair<tree_type::iterator, bool>;
    tree_type tree;

    // 插入元素Node(1, 2)
    result_pair_type res = tree._M_insert_unique(Node(1, 2));
    cout << "insert address = " << res.first._M_node << endl;
    cout << "insert result = " << boolalpha << res.second << endl; // true

    iterator_type it = tree.begin();
    cout << "begin address = " << it._M_node << endl;

    it = tree.find(1);
    cout << "address = " << it._M_node << ", value = " << *it << endl;

    // 再插入元素Node(1, 2)但是因为调用的是insert_unique
    // 它不会添加重复值，所以插入会被拒绝
    res = tree._M_insert_unique(Node(1, 2));
    cout << "insert result = " << boolalpha << res.second << endl; // false

    // 再插入元素Node(1, 2)但这次调用insert_equal
    // multiset和multimap就是利用这个函数来插入重复值
    // 也就是这个函数允许重复值，所以插入成功
    tree._M_insert_equal(Node(1, 3));
    cout << "size = " << tree.size() << endl; // 大小就变为2

    pair<iterator_type, iterator_type> result = tree.equal_range(1);
    for (iterator_type ite = result.first; ite != result.second; ++ite) {
        cout << "address = " << ite._M_node << ", value = " << *ite << endl;
    }
    
    return 0;
}

// main.cpp, main()
int main() {
    ...
    it = tree.find(1);
    ...
}

// stl_tree.h, std::_Rb_tree::find(const _Key&)
template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    find(const _Key& __k) {
        iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
        return (__j == end() || _M_impl._M_key_compare(__k,
            _S_key(__j._M_node))) ? end() : __j;
   }

// stl_tree.h, std::_Rb_tree::_M_lower_bound(_Link_type, _Link_type, const _Key&)
template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_lower_bound(_Link_type __x, _Link_type __y, const _Key& __k) {
        while (__x != 0)
            if (!_M_impl._M_key_compare(_S_key(__x), __k))
                __y = __x, __x = _S_left(__x);
            else
                __x = _S_right(__x);
        return iterator(__y);
    }

// stl_tree.h, std::_Rb_tree::_S_key(_Const_Base_ptr)
static const _Key& _S_key(_Const_Base_ptr __x) {
    return _KeyOfValue()(_S_value(__x));
}

#include <iostream>
#include <map>

using namespace std;

typedef multimap<int, char>::iterator iterType;

int main() {
    multimap<int, char> mp;
    mp.insert(make_pair(1, 'A'));
    mp.insert(make_pair(2, 'B'));
    mp.insert(make_pair(2, 'C'));
    mp.insert(make_pair(2, 'D'));
    mp.insert(make_pair(4, 'E'));
    mp.insert(make_pair(3, 'F'));
    pair<iterType, iterType> range = mp.equal_range(2);
    for (iterType it = range.first; it != range.second; ++it) {
        cout << it->first << ' ' << it->second << '\n';
    }
    return 0;
}

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e6 + 50;

char s[N];
int sa[N], rk[N], cnt[N], height[N], t1[N], t2[N];

void calcSA(char *s, int n) {
    int m = 256;
    int i, *x = t1, *y = t2;
    for (i = 1; i <= m; ++i) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[x[i] = s[i]];
    for (i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int p = 0;
        for (i = n - k + 1; i <= n; ++i) y[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > k) y[++p] = sa[i] - k;
        for (i = 1; i <= m; ++i) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[x[i]];
        for (i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[x[y[i]]]--] = y[i];
        swap(x, y);
        x[sa[1]] = 1;
        p = 1;
        for (i = 2; i <= n; ++i)
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p : ++p;
        if (p >= n) break;
        m = p;
    }
    for (i = 1; i <= n; ++i) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; ++i) {
        if (rk[i] == 1) {
            height[rk[i]] = 0;
        } else {
            if (k) --k;
            int j = sa[rk[i] - 1];
            while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
            height[rk[i]] = k;
        }
    }
}

int main() {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    calcSA(s, len);
    for (int i = 1; i <= len; ++i) printf("%d ", sa[i]);
    return 0;
}