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, a[200010];
int l, r;
void update(int pl, int pr) {
  if (pr - pl > r - l) {
    l = pl;
    r = pr;
  }
}
class sgt {
 public:
  long long mn[800010], tag[800010];
  inline void pushnow(int p, long long v) {
    tag[p] += v;
    mn[p] += v;
  }
  inline void pushdown(int p) {
    if (tag[p]) {
      pushnow((p << 1), tag[p]);
      pushnow(((p << 1) | 1), tag[p]);
      tag[p] = 0;
    }
  }
  inline void build(int p, int l, int r) {
    if (l == r) {
      mn[p] = l;
      return;
    }
    int mid = (l + r) >> 1;
    build((p << 1), l, mid);
    build(((p << 1) | 1), mid + 1, r);
    mn[p] = min(mn[(p << 1)], mn[((p << 1) | 1)]);
  }
  inline void modify(int p, int l, int r, int ml, int mr, int v) {
    if (ml <= l && r <= mr) {
      pushnow(p, v);
      return;
    }
    pushdown(p);
    int mid = (l + r) >> 1;
    if (ml <= mid) modify((p << 1), l, mid, ml, mr, v);
    if (mr > mid) modify(((p << 1) | 1), mid + 1, r, ml, mr, v);
    mn[p] = min(mn[(p << 1)], mn[((p << 1) | 1)]);
  }
  inline int query(int p, int l, int r, int ql, int qr, int v) {
    if (mn[p] > v) return -1;
    if (l == r) return l;
    pushdown(p);
    int mid = (l + r) >> 1;
    if (qr <= mid) return query((p << 1), l, mid, ql, qr, v);
    if (ql > mid) return query(((p << 1) | 1), mid + 1, r, ql, qr, v);
    int pl = query((p << 1), l, mid, ql, mid, v);
    if (pl != -1) return pl;
    return query(((p << 1) | 1), mid + 1, r, mid + 1, qr, v);
  }
} T;
int pre[200010];
map<int, int> cur;
int main() {
  scanf("%d%d%d", &n, &K, &d);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  if (d == 0) {
    l = r = 1;
    for (int i = 1, j; i <= n; i = j + 1) {
      j = i;
      while (j <= n && a[j] == a[i]) j++;
      j--;
      update(i, j);
    }
  } else {
    l = r = 1;
    T.build(1, 1, n);
    for (int i = 1, j; i <= n; i = j + 1) {
      j = i;
      while (j <= n && (a[j] % d + d) % d == (a[i] % d + d) % d) j++;
      j--;
      for (int k = i; k <= j; k++) {
        if (a[k] >= 0)
          a[k] = a[k] / d;
        else
          a[k] = (a[k] - ((a[k] % d + d) % d)) / d;
      }
      cur.clear();
      for (int k = i; k <= j; k++) {
        if (cur.find(a[k]) != cur.end())
          pre[k] = cur[a[k]];
        else
          pre[k] = i - 1;
        cur[a[k]] = k;
      }
      vector<pair<int, int> > stk1, stk2;
      int mnl = i;
      for (int k = i; k <= j; k++) {
        int pl = k;
        while (!stk1.empty() && stk1.back().first >= a[k]) {
          T.modify(1, 1, n, stk1.back().second, pl - 1,
                   stk1.back().first - a[k]);
          pl = stk1.back().second;
          stk1.pop_back();
        }
        stk1.push_back(make_pair(a[k], pl));
        pl = k;
        while (!stk2.empty() && stk2.back().first <= a[k]) {
          T.modify(1, 1, n, stk2.back().second, pl - 1,
                   a[k] - stk2.back().first);
          pl = stk2.back().second;
          stk2.pop_back();
        }
        stk2.push_back(make_pair(a[k], pl));
        mnl = max(mnl, pre[k] + 1);
        update(T.query(1, 1, n, mnl, k, k + K), k);
      }
    }
  }
  printf("%d %d\n", l, r);
  return 0;
}
