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 int MAXN = 200005;
const int MAXS = 1 << 19;
int input[MAXN], A[MAXN], K, n, ansL = 1, ansR;
long long minf[MAXS], offset[MAXS];
int query(int sn, int s, int e, int minpos, long long lim) {
  if (s == e) return s;
  lim -= offset[sn];
  int m = (s + e) >> 1, lsn = sn * 2 + 1, rsn = sn * 2 + 2;
  if (minf[lsn] + offset[lsn] <= lim && minpos <= m) {
    return query(lsn, s, m, minpos, lim);
  }
  return query(rsn, m + 1, e, minpos, lim);
}
void add(int sn, int s, int e, int qs, int qe, int v) {
  if (qs <= s && e <= qe) {
    offset[sn] += v;
    return;
  }
  int m = (s + e) >> 1, lsn = sn * 2 + 1, rsn = sn * 2 + 2;
  if (qs <= m) add(lsn, s, m, qs, qe, v);
  if (qe > m) add(rsn, m + 1, e, qs, qe, v);
  minf[sn] = min(minf[lsn] + offset[lsn], minf[rsn] + offset[rsn]);
}
void updateAns(int l, int r) {
  if (r - l > ansR - ansL || (r - l == ansR - ansL && l < ansL)) {
    ansL = l;
    ansR = r;
  }
}
void solve(int delta) {
  int p = 1;
  stack<pair<int, int> > mxst, mnst;
  map<int, bool> has;
  for (int i = 1; i <= n; ++i) {
    while (has[A[i]]) {
      has.erase(A[p]);
      add(0, 1, n, p, p, INT_MAX);
      ++p;
    }
    has[A[i]] = true;
    int cnt = 0;
    while (!mxst.empty() && mxst.top().first <= A[i]) {
      int siz = mxst.top().second;
      cnt += siz;
      add(0, 1, n, i - cnt, i - cnt + siz - 1, A[i] - mxst.top().first);
      mxst.pop();
    }
    mxst.push(make_pair(A[i], cnt + 1));
    cnt = 0;
    while (!mnst.empty() && mnst.top().first >= A[i]) {
      int siz = mnst.top().second;
      cnt += siz;
      add(0, 1, n, i - cnt, i - cnt + siz - 1, mnst.top().first - A[i]);
      mnst.pop();
    }
    mnst.push(make_pair(A[i], cnt + 1));
    add(0, 1, n, i, i, i);
    int bestL = query(0, 1, n, p, i + K);
    updateAns(bestL + delta, i + delta);
  }
  for (int i = 0; i < min(MAXS, 4 * n); ++i) minf[i] = offset[i] = 0;
}
int main() {
  int N, D;
  scanf("%d%d%d", &N, &K, &D);
  for (int i = 0; i < N; ++i) scanf("%d", &input[i]);
  if (!D) {
    for (int i = 0; i < N; ++i) {
      if (i && input[i] != input[i - 1]) {
        updateAns(i - n + 1, i);
        n = 0;
      }
      ++n;
    }
    updateAns(N - n + 1, N);
  } else {
    int pmod;
    for (int i = 0; i < N; ++i) {
      int div = input[i] < 0 ? (input[i] - D + 1) / D : input[i] / D;
      int mod = input[i] - div * D;
      if (i && mod != pmod) {
        solve(i - n);
        n = 0;
      }
      pmod = mod;
      A[++n] = div;
    }
    solve(N - n);
  }
  printf("%d %d\n", ansL, ansR);
}
