const int k = 316;

struct sqrtd {
    int n;

    vector<int> a;
    vector<int> next;
    vector<int> cnt;

    sqrtd(vector<int> b) {
        n = b.size();
        a = b;
        next.resize(n, 0);
        cnt.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            if (cnt[i]) continue;
            int j = i;
            while (j / k < i / k + 1 && j < n) {
                cnt[i]++; j += a[j];
            }
            next[i] = j;
            j = i + a[i]; int c = 1;
            while (j / k < i / k + 1 && j < n) {
                cnt[j] = cnt[i] - c;
                next[j] = next[i];
                j += a[j];
                ++c;
            }
        }
    }

    void update(int j, int m) {
        int block = j / k;
        a[j] = m;
        for (int i = block * k; i <= j; ++i) {
            next[i] = 0;
            cnt[i] = 0;
        }

        for (int i = block * k; i <= j; ++i) {
            if (cnt[i]) continue;
            int j = i;
            while (j / k < i / k + 1 && j < n) {
                cnt[i]++; j += a[j];
            }
            next[i] = j;
            j = i + a[i]; int c = 1;
            while (j / k < i / k + 1 && j < n) {
                cnt[j] = cnt[i] - c;
                next[j] = next[i];
                j += a[j];
                ++c;
            }
        }
    }

    pair<int, int> get(int j) {
        int ans = 0;
        while (next[j] < a.size()) {
            ans += cnt[j];
            j = next[j];
        }
        while (j + a[j] < n) {
            j += a[j];
            ++ans;
        }
        return {j + 1, ans + 1};
    }
};