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 = 0x7f7f7f7f;
const int mo = 1e9 + 7;
const int iv2 = 5e8 + 4;
const int jzm = 2333;
const int orG = 3, invG = 332748118;
const double Pi = acos(-1.0);
const double PI = acos(-1.0);
template <typename _T>
_T Fabs(_T x) {
  return x < 0 ? -x : x;
}
template <typename _T>
void read(_T &x) {
  _T f = 1;
  x = 0;
  char s = getchar();
  while (s > '9' || s < '0') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while ('0' <= s && s <= '9') {
    x = (x << 3) + (x << 1) + (s ^ 48);
    s = getchar();
  }
  x *= f;
}
template <typename _T>
void print(_T x) {
  if (x < 0) {
    x = (~x) + 1;
    putchar('-');
  }
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int add(int x, int y) { return x + y < mo ? x + y : x + y - mo; }
int K, d, n, a[200005], nxt[200005], lim[200005], ans, ansk;
int stamx[200005], stkmx, stamn[200005], stkmn;
map<int, int> head;
class SegmentTree {
 public:
  int sum[200005 << 2], lzy[200005 << 2];
  bool clr[200005 << 2];
  void pushup(int rt) { sum[rt] = max(sum[(rt << 1)], sum[(rt << 1 | 1)]); }
  void pushdown(int rt) {
    if (lzy[rt]) {
      lzy[(rt << 1)] += lzy[rt];
      sum[(rt << 1)] += lzy[rt];
      lzy[(rt << 1 | 1)] += lzy[rt];
      sum[(rt << 1 | 1)] += lzy[rt];
      lzy[rt] = 0;
    }
    if (clr[rt]) {
      sum[(rt << 1)] = sum[(rt << 1 | 1)] = -INF;
      lzy[(rt << 1)] = lzy[(rt << 1 | 1)] = 0;
      clr[(rt << 1)] = clr[(rt << 1 | 1)] = 1;
      clr[rt] = 1;
    }
  }
  void build(int rt, int l, int r) {
    sum[rt] = -INF;
    lzy[rt] = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build((rt << 1), l, mid);
    build((rt << 1 | 1), mid + 1, r);
  }
  void insert(int rt, int l, int r, int ai) {
    if (l > r || l > ai || r < ai) return;
    int mid = l + r >> 1;
    if (l == r) {
      sum[rt] = ai;
      lzy[rt] = 0;
      return;
    }
    pushdown(rt);
    if (ai <= mid)
      insert((rt << 1), l, mid, ai);
    else
      insert((rt << 1 | 1), mid + 1, r, ai);
    pushup(rt);
  }
  void modify(int rt, int l, int r, int al, int ar, int aw) {
    if (al > ar || l > r || al > r || ar < l) return;
    if (al <= l && r <= ar) {
      sum[rt] += aw;
      lzy[rt] += aw;
      return;
    }
    int mid = l + r >> 1;
    pushdown(rt);
    if (al <= mid) modify((rt << 1), l, mid, al, ar, aw);
    if (ar > mid) modify((rt << 1 | 1), mid + 1, r, al, ar, aw);
    pushup(rt);
  }
  void clear(int rt, int l, int r, int al, int ar) {
    if (al > ar || l > r || l > ar || r < al) return;
    if (al <= l && r <= ar) {
      sum[rt] = -INF;
      lzy[rt] = 0;
      clr[rt] = 1;
      return;
    }
    int mid = l + r >> 1;
    pushdown(rt);
    if (al <= mid) clear((rt << 1), l, mid, al, ar);
    if (ar > mid) clear((rt << 1 | 1), mid + 1, r, al, ar);
    pushup(rt);
  }
  int query(int rt, int l, int r, int k) {
    if (l > r || sum[rt] < k) return 0;
    if (l == r) return l;
    int mid = l + r >> 1;
    pushdown(rt);
    if (sum[(rt << 1 | 1)] >= k) return query((rt << 1 | 1), mid + 1, r, k);
    return query((rt << 1), l, mid, k);
  }
} T;
signed main() {
  read(n);
  read(K);
  read(d);
  for (int i = 1; i <= n; i++) read(a[i]);
  T.build(1, 1, n);
  if (!d) {
    int tmp = 0;
    a[0] = -INF;
    for (int i = 1; i <= n; i++) {
      if (a[i] == a[i - 1])
        tmp++;
      else
        tmp = 1;
      if (tmp > ans) ansk = i - tmp + 1, ans = tmp;
    }
    printf("%d %d\n", ansk, ansk + ans - 1);
    return 0;
  }
  for (int i = 1, j; i <= n; i = j + 1) {
    j = i;
    while (j < n && Fabs(a[j + 1] - a[j]) % d == 0) j++;
    for (int k = i; k <= j; k++) a[k] = (int)floor(1.0 * a[k] / d);
    head.clear();
    int tmp = j + 1;
    stkmx = stkmn = 0;
    for (int k = j; k >= i; k--) {
      if (!head[a[k]])
        nxt[k] = j + 1;
      else
        nxt[k] = head[a[k]];
      tmp = min(nxt[k], tmp);
      head[a[k]] = k;
      lim[k] = tmp - 1;
    }
    for (int k = j, r; k >= i; k--) {
      while (stkmx && a[stamx[stkmx]] < a[k]) {
        r = stkmx > 1 ? stamx[stkmx - 1] - 1 : j;
        T.modify(1, 1, n, stamx[stkmx], r, a[stamx[stkmx]]);
        stkmx--;
      }
      r = stkmx > 0 ? stamx[stkmx] - 1 : j;
      T.modify(1, 1, n, k + 1, r, -a[k]);
      stamx[++stkmx] = k;
      while (stkmn && a[stamn[stkmn]] > a[k]) {
        r = stkmn > 1 ? stamn[stkmn - 1] - 1 : j;
        T.modify(1, 1, n, stamn[stkmn], r, -a[stamn[stkmn]]);
        stkmn--;
      }
      r = stkmn > 0 ? stamn[stkmn] - 1 : j;
      T.modify(1, 1, n, k + 1, r, a[k]);
      stamn[++stkmn] = k;
      T.insert(1, 1, n, k);
      T.clear(1, 1, n, lim[k] + 1, j);
      int tmp = T.query(1, 1, n, k - K) - k + 1;
      if (ans < tmp || (ans == tmp && ansk > k)) ans = tmp, ansk = k;
    }
    T.clear(1, 1, n, i, j);
  }
  printf("%d %d\n", ansk, ansk + ans - 1);
  return 0;
}
