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;
int N, K, D;
int A[200002], B[200002];
map<int, int> MP;
int nxt[200002], maxgo[200002];
int ST1[200002], ST2[200002];
int ARB[4 * 200002], A1, A2, Ap, Av, Ar;
int result = 1, d1 = 1, d2 = 1;
void setall(int nod, int i1, int i2) {
  if (i1 == i2) {
    ARB[nod] = 0;
    return;
  }
  int mid = (i1 + i2) / 2;
  setall(nod * 2, i1, mid);
  setall(nod * 2 + 1, mid + 1, i2);
  ARB[nod] = min(ARB[nod * 2], ARB[nod * 2 + 1]);
}
void update(int nod, int i1, int i2) {
  if (A1 <= i1 && i2 <= A2) {
    ARB[nod] += Av;
    return;
  }
  if (ARB[nod] != min(ARB[nod * 2], ARB[nod * 2 + 1])) {
    int diff = ARB[nod] - min(ARB[nod * 2], ARB[nod * 2 + 1]);
    ARB[nod * 2] += diff;
    ARB[nod * 2 + 1] += diff;
  }
  int mid = (i1 + i2) / 2;
  if (A1 <= mid) update(nod * 2, i1, mid);
  if (A2 > mid) update(nod * 2 + 1, mid + 1, i2);
  ARB[nod] = min(ARB[nod * 2], ARB[nod * 2 + 1]);
}
void query(int nod, int i1, int i2) {
  if (ARB[nod] > K) return;
  if (i1 == i2) {
    Ar = i1;
    return;
  }
  if (ARB[nod] != min(ARB[nod * 2], ARB[nod * 2 + 1])) {
    int diff = ARB[nod] - min(ARB[nod * 2], ARB[nod * 2 + 1]);
    ARB[nod * 2] += diff;
    ARB[nod * 2 + 1] += diff;
  }
  int mid = (i1 + i2) / 2;
  if (mid + 1 <= A2) query(nod * 2 + 1, mid + 1, i2);
  if (Ar == 0) query(nod * 2, i1, mid);
}
void solve(int blim) {
  setall(1, 1, B[0]);
  MP.clear();
  MP[B[B[0]]] = B[0];
  maxgo[B[0]] = B[0];
  for (int i = B[0] - 1; i >= 1; --i) {
    maxgo[i] = maxgo[i + 1];
    if (MP.find(B[i]) != MP.end() && MP[B[i]] - 1 < maxgo[i])
      maxgo[i] = MP[B[i]] - 1;
    MP[B[i]] = i;
  }
  ST1[0] = 0;
  ST1[++ST1[0]] = B[0];
  ST2[0] = 0;
  ST2[++ST2[0]] = B[0];
  for (int i = B[0] - 1; i >= 1; --i) {
    while (ST1[0] != 0 && B[i] >= B[ST1[ST1[0]]]) {
      A1 = ST1[ST1[0]], A2 = (ST1[0] == 1 ? B[0] : ST1[ST1[0] - 1] - 1),
      Av = B[i] - B[ST1[ST1[0]]];
      update(1, 1, B[0]);
      --ST1[0];
    }
    ST1[++ST1[0]] = i;
    while (ST2[0] != 0 && B[i] <= B[ST2[ST2[0]]]) {
      A1 = ST2[ST2[0]], A2 = (ST2[0] == 1 ? B[0] : ST2[ST2[0] - 1] - 1),
      Av = -(B[i] - B[ST2[ST2[0]]]);
      update(1, 1, B[0]);
      --ST2[0];
    }
    ST2[++ST2[0]] = i;
    A1 = i + 1, A2 = B[0], Av = -1;
    update(1, 1, B[0]);
    A1 = i, A2 = maxgo[i], Ar = 0;
    query(1, 1, B[0]);
    if (Ar - i + 1 > result || (Ar - i + 1 == result && blim + i < d1)) {
      result = Ar - i + 1;
      d1 = blim + i;
      d2 = blim + i + result - 1;
    }
  }
}
int main() {
  cin.sync_with_stdio(false);
  cin >> N >> K >> D;
  for (int i = 1; i <= N; ++i) cin >> A[i];
  if (D == 0) {
    for (int i = 1; i <= N; ++i) {
      int now = i;
      while (now <= N && A[now] == A[i]) ++now;
      if (now - i > result) {
        result = now - i;
        d1 = i;
        d2 = now - 1;
      }
      i = now - 1;
    }
    cout << d1 << ' ' << d2 << '\n';
    return 0;
  }
  for (int i = 1; i <= N; ++i) {
    int init = i;
    B[0] = 0;
    B[++B[0]] = 0;
    while (i < N && (A[i + 1] - A[i]) % D == 0) {
      ++B[0];
      B[B[0]] = B[B[0] - 1] + (A[i + 1] - A[i]) / D;
      ++i;
    }
    solve(init - 1);
  }
  cout << d1 << ' ' << d2 << '\n';
}
