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 N = 2e5 + 10;
const int M = 1000000000;
const int INF = 1e18;
int a[N], b[N], s1[N], s2[N];
int n, m, k, d, top1, top2, ansr, ansl, sum[N], pos[N], t[N], mn[N];
map<int, int> mp;
void reset(int x) {
  mn[x] = INF;
  for (int i = (x - 1) * m + 1; i <= min(n, x * m); i++)
    mn[x] = min(mn[x], t[i] + sum[x]);
}
inline void add(int l, int r, int c) {
  for (int i = l; i <= min(r, pos[l] * m); i++) t[i] += c;
  reset(pos[l]);
  if (pos[l] != pos[r]) {
    for (int i = (pos[r] - 1) * m + 1; i <= min(n, r); i++) t[i] += c;
    reset(pos[r]);
  }
  for (int i = pos[l] + 1; i <= pos[r] - 1; i++) sum[i] += c, mn[i] += c;
}
inline int query(int l, int r, int c) {
  for (int i = r; i >= max((pos[r] - 1) * m + 1, l); i--) {
    if (t[i] + sum[pos[i]] <= c) {
      return i;
    }
  }
  for (int i = pos[r] - 1; i >= pos[l] + 1; i--)
    if (mn[i] <= c) {
      for (int j = i * m; j >= (i - 1) * m + 1; j--)
        if (t[j] + sum[pos[j]] <= c) {
          return j;
        }
    }
  if (pos[l] != pos[r]) {
    for (int i = pos[l] * m; i >= l; i--) {
      if (t[i] + sum[pos[i]] <= c) return i;
    }
  }
}
inline void sol(int L, int R) {
  if (L == R) return;
  mp.clear();
  int r = R + 1;
  top1 = top2 = 0;
  s1[top1] = s2[top2] = R + 1;
  for (int i = 0; i <= pos[n]; i++) sum[i] = 0;
  for (int i = R; i >= L; i--) {
    if (mp.count(a[i])) r = min(r, mp[a[i]]);
    while (top1 && a[i] > a[s1[top1]]) {
      add(s1[top1], s1[top1 - 1] - 1, -a[s1[top1]]);
      top1--;
    }
    s1[++top1] = i;
    add(s1[top1], s1[top1 - 1] - 1, a[s1[top1]]);
    while (top2 && a[i] < a[s2[top2]]) {
      add(s2[top2], s2[top2 - 1] - 1, a[s2[top2]]);
      top2--;
    }
    s2[++top2] = i;
    add(s2[top2], s2[top2 - 1] - 1, -a[s2[top2]]);
    int rr = query(i, r - 1, k - i);
    if (rr - i > ansr - ansl || (rr - i == ansr - ansl && i < ansl))
      ansl = i, ansr = rr;
    mp[a[i]] = i;
  }
  return;
}
int main() {
  scanf("%d%d%d", &n, &k, &d);
  if (d == 0) {
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int ansl = 1;
    int ansr = 1;
    int lst = 1;
    for (int i = 2; i <= n; i++) {
      if (a[i] != a[lst]) {
        if (i - 1 - lst > ansr - ansl) {
          ansl = lst;
          ansr = i - 1;
        }
        lst = i;
      }
    }
    printf("%d %d\n", ansl, ansr);
    return 0;
  }
  ansl = n + 1;
  ansr = 0;
  m = sqrt(n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[i] = (a[i] += M) % d;
    a[i] = (a[i]) / d + 1;
    pos[i] = (i - 1) / m + 1;
    t[i] = -i;
  }
  for (int i = 1, j; i <= n; i = j) {
    for (j = i + 1; j <= n; j++) {
      if (b[i] != b[j]) break;
    }
    sol(i, j - 1);
  }
  printf("%d %d\n", ansl, ansr);
  return 0;
}
