#include <bits/stdc++.h>
#define int long long

using namespace std;

inline int read () {
    int w = 1, s = 0; char ch = getchar ();
    for (; ! isdigit (ch); ch = getchar ()) if (ch == '-') w = -1;
    for (; isdigit (ch); ch = getchar ()) s = (s << 1) + (s << 3) + (ch ^ 48);
    return s * w;
}

constexpr int P = 11451;
constexpr int N = 1E6 + 10;
constexpr int mod = 1E9 + 33;

int p[N];

void solve () {
    string s;
    cin >> s;

    const int n = s.size ();

    s = " " + s;

    vector <int> Hash (n + 1);
    for (int i = 1; i <= n; i ++) {
        Hash[i] = (Hash[i - 1] * P + s[i]) % mod;
    }

    auto cal = [&] (int l, int r) {
        return (Hash[r] - Hash[l - 1] * p[r - l + 1] % mod + mod) % mod;
    };

    auto cmp = [&] (int l1, int r1, int l2, int r2) {
        int l = 1, r = min (r1 - l1 + 1, r2 - l2 + 1);

        auto check = [&] (int x) {
            int x1 = l1, y1 = x1 + x - 1;
            int x2 = l2, y2 = x2 + x - 1;
            return cal (x1, y1) != cal (x2, y2);
        };
        while (l < r) {
            int mid = (l + r) / 2;
            if (check (mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (! check (l)) {
            return false;
        } else {
            return s[l1 + l - 1] < s[l2 + l - 1];
        }   
    };

    vector <int> ans (n + 1);

    auto work = [&] (auto &&self, int l, int r, int bl, int br) -> void {
        if (l > r) {
            return;
        }
        int mid = (l + r) / 2;
        int id = bl;
        for (int i = id + 1; i <= min (br, mid); i ++) {
            if (cmp (id, mid, i, mid)) {
                id = i;
            }
        }
        ans[mid] = id;
        self (self, l, mid - 1, bl, id);
        self (self, mid + 1, r, id, br);
    };
    work (work, 1, n, 1, n);

    for (int i = 1; i <= n; i ++) {
        cout << ans[i] << " " << i << '\n';
    }
} 

signed main () {
	ios::sync_with_stdio (false);
    cin.tie (nullptr);

    p[0] = 1;
    for (int i = 1; i < N; i ++) {
        p[i] = p[i - 1] * P % mod;
    }

	int T = 1; 
	// cin >> T;
	// T = read ();

	while (T --) {
		solve ();
	}
	
	return 0;
}