We'll call a sequence of integers a good k-d sequence if we can add to it at most k numbers in such a way that after the sorting the sequence will be an arithmetic progression with difference d.

You got hold of some sequence a, consisting of n integers. Your task is to find its longest contiguous subsegment, such that it is a good k-d sequence.

Input

The first line contains three space-separated integers n, k, d (1 ≤ n ≤ 2·105; 0 ≤ k ≤ 2·105; 0 ≤ d ≤ 109). The second line contains n space-separated integers: a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the actual sequence.

Output

Print two space-separated integers l, r (1 ≤ l ≤ r ≤ n) show that sequence al, al + 1, ..., ar is the longest subsegment that is a good k-d sequence.

If there are multiple optimal answers, print the one with the minimum value of l.

Examples

Input

6 1 2
4 3 2 8 6 2


Output

3 5

Note

In the first test sample the answer is the subsegment consisting of numbers 2, 8, 6 — after adding number 4 and sorting it becomes sequence 2, 4, 6, 8 — the arithmetic progression with difference 2.
#include <bits/stdc++.h>
using namespace std;
const long long N = 212212;
long long a[N], Q[N], W[N], n, k, d;
long long E[6 * N], T[6 * N];
pair<long long, long long> P[6 * N];
void Y(long long i = 1, long long l = 0, long long r = N) {
  P[i] = pair<long long, long long>(l, r);
  if (r - l <= 1) return;
  long long U = (l + r) / 2;
  Y(i * 2, l, U);
  Y(i * 2 + 1, U, r);
}
long long I(long long l, long long r, long long O) {
  return max(0LL, min(r, P[O].second) - max(l, P[O].first));
}
void A(long long O) {
  E[O] += T[O];
  T[O * 2 + 1] += T[O];
  T[O * 2] += T[O];
  T[O] = 0;
}
void G(long long l, long long r, long long x, long long O = 1) {
  A(O);
  long long s = I(l, r, O);
  if (s == P[O].second - P[O].first) {
    T[O] += x;
    A(O);
  } else if (s) {
    G(l, r, x, O * 2);
    G(l, r, x, O * 2 + 1);
    E[O] = min(E[O * 2], E[O * 2 + 1]);
  }
}
long long H(long long l, long long r, long long x, long long O = 1) {
  A(O);
  long long s = I(l, r, O);
  long long J = -1;
  if (E[O] <= x && s)
    if (P[O].second - P[O].first == 1)
      J = P[O].first;
    else {
      J = H(l, r, x, O * 2 + 1);
      if (J == -1) J = H(l, r, x, O * 2);
    }
  return J;
}
void first() {
  for (long long i = n - 1; i >= 0; i--)
    if (i == n - 1 || ((a[i] % d) + d) % d != ((a[i + 1] % d) + d) % d)
      W[i] = i + 1;
    else
      W[i] = W[i + 1];
  set<long long> s;
  long long r = n;
  for (long long l = n - 1; l >= 0; l--) {
    while (s.find(a[l]) != s.end()) {
      r--;
      s.erase(a[r]);
    }
    s.insert(a[l]);
    Q[l] = r;
  }
  Y();
  for (long long r = 1; r <= n; r++) G(r, r + 1, -r + 1);
  for (long long i = 0; i < n; i++) a[i] /= d;
}
void Z() {
  long long X = 1, C = 1, l = 0;
  for (long long i = n - 2; i >= 0; i--) {
    if (a[i] == a[i + 1])
      C++;
    else
      C = 1;
    if (X <= C) l = i;
    X = max(X, C);
  }
  cout << l + 1 << " " << l + X << endl;
}
int main() {
  cin >> n >> k >> d;
  for (long long i = 0; i < n; i++) cin >> a[i];
  if (d == 0) return Z(), 0;
  first();
  long long V = 0, X = 1;
  deque<long long> second, E;
  second.push_back(n);
  E.push_back(n);
  for (long long l = n - 1; l >= 0; l--) {
    while (second.front() < n && a[second.front()] <= a[l]) {
      long long r = second.front();
      second.pop_front();
      G(r + 1, second.front() + 1, a[l] - a[r]);
    }
    second.push_front(l);
    while (E.front() < n && a[E.front()] >= a[l]) {
      long long r = E.front();
      E.pop_front();
      G(r + 1, E.front() + 1, a[r] - a[l]);
    }
    E.push_front(l);
    long long r = min(Q[l], W[l]) + 1;
    long long bestR = H(l + 1, r, k - l);
    long long C = bestR - l;
    if (X <= C) V = l;
    X = max(X, C);
  }
  cout << V + 1 << " " << V + X << endl;
}
