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 INF = 2e9 + 1e8;
struct node {
  int l, r, tag, mn;
} t[800010];
struct elem {
  int v, id;
} st1[200010], st2[200010];
int n, k, d, a[200010], mn = INF, sz1, sz2, ans, al, ar, L, mxp;
map<int, int> mp;
void Build(const int& x, const int& l, const int& r) {
  t[x].l = l, t[x].r = r, t[x].tag = 0;
  if (l == r) return (void)(t[x].mn = l);
  int mid = l + r >> 1;
  Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r),
      (t[x].mn = min(t[x << 1].mn, t[x << 1 | 1].mn));
}
void Change(const int& x, const int& l, const int& r, const int& v) {
  if (t[x].l == l && t[x].r == r) return (void)(t[x].tag += v, t[x].mn += v);
  (t[x].tag ? t[x << 1].tag += t[x].tag, t[x << 1].mn += t[x].tag,
   t[x << 1 | 1].tag += t[x].tag, t[x << 1 | 1].mn += t[x].tag,
   t[x].tag = 0 : 0);
  int mid = t[x].l + t[x].r >> 1;
  r <= mid
      ? Change(x << 1, l, r, v)
      : (l > mid
             ? Change(x << 1 | 1, l, r, v)
             : (Change(x << 1, l, mid, v), Change(x << 1 | 1, mid + 1, r, v))),
      (t[x].mn = min(t[x << 1].mn, t[x << 1 | 1].mn));
}
int Find(const int& x, const int& mxv) {
  if (t[x].mn > mxv) return INF;
  if (t[x].l == t[x].r) return t[x].l;
  (t[x].tag ? t[x << 1].tag += t[x].tag, t[x << 1].mn += t[x].tag,
   t[x << 1 | 1].tag += t[x].tag, t[x << 1 | 1].mn += t[x].tag,
   t[x].tag = 0 : 0);
  return t[x << 1].mn <= mxv ? Find(x << 1, mxv) : Find(x << 1 | 1, mxv);
}
int Query(const int& x, const int& l, const int& r, const int& mxv) {
  if (t[x].l == l && t[x].r == r) return Find(x, mxv);
  (t[x].tag ? t[x << 1].tag += t[x].tag, t[x << 1].mn += t[x].tag,
   t[x << 1 | 1].tag += t[x].tag, t[x << 1 | 1].mn += t[x].tag,
   t[x].tag = 0 : 0);
  int mid = t[x].l + t[x].r >> 1;
  return r <= mid ? Query(x << 1, l, r, mxv)
                  : (l > mid ? Query(x << 1 | 1, l, r, mxv)
                             : min(Query(x << 1, l, mid, mxv),
                                   Query(x << 1 | 1, mid + 1, r, mxv)));
}
int main() {
  scanf("%d%d%d", &n, &k, &d);
  if (!d) {
    mxp = 1;
    for (int i = 1; i <= n; ++i)
      scanf("%d", &a[i]),
          a[i] != a[i - 1] ? mxp = i : 0, i - mxp + 1 > ans ? ans = i - mxp + 1,
                             al = mxp, ar = i               : 0;
    return printf("%d %d", al, ar), 0;
  }
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), mn = min(mn, a[i]);
  for (int i = 1; i <= n; ++i) a[i] -= mn;
  for (int i = 1, j; i <= n; i = j + 1) {
    for (j = i; j < n && a[i] % d == a[j + 1] % d; ++j)
      ;
    sz1 = sz2 = 0, Build(1, i, j);
    st1[0].id = st2[0].id = i - 1, mp.clear(), mxp = i;
    for (int R = i; R <= j; ++R) {
      a[R] /= d;
      while (sz1 && st1[sz1].v <= a[R])
        Change(1, st1[sz1 - 1].id + 1, st1[sz1].id, a[R] - st1[sz1].v), --sz1;
      while (sz2 && st2[sz2].v >= a[R])
        Change(1, st2[sz2 - 1].id + 1, st2[sz2].id, st2[sz2].v - a[R]), --sz2;
      st1[++sz1] = (elem){a[R], R}, st2[++sz2] = (elem){a[R], R};
      mxp = max(mxp, mp[a[R]] + 1), mp[a[R]] = R;
      L = Query(1, mxp, R, R + k), R - L + 1 > ans ? ans = R - L + 1, al = L,
      ar = R : 0;
    }
  }
  printf("%d %d", al, ar);
  return 0;
}
