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 maxl = 200005;
int read() {
  int s = 0, w = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -w;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + (ch ^ '0');
    ch = getchar();
  }
  return s * w;
}
int n, k, d, pos1, pos2, maxv, ansl, ansr;
int a[maxl], lim[maxl], tree[maxl << 2], tag[maxl << 2];
int mint[maxl], maxt[maxl], minval[maxl], maxval[maxl];
map<int, int> la;
void pushup(int rt) { tree[rt] = min(tree[2 * rt], tree[2 * rt + 1]); }
void f(int l, int r, int rt, int num) { tree[rt] += num, tag[rt] += num; }
void pushdown(int l, int r, int rt) {
  if (l == r) return;
  if (tag[rt]) {
    int mid = (l + r) >> 1;
    f(l, mid, rt << 1, tag[rt]);
    f(mid + 1, r, rt << 1 | 1, tag[rt]);
    tag[rt] = 0;
  }
}
void build_tree(int l, int r, int rt) {
  if (l == r) {
    tree[rt] = l;
    return;
  }
  int mid = (l + r) >> 1;
  build_tree(l, mid, rt << 1), build_tree(mid + 1, r, rt << 1 | 1);
  pushup(rt);
}
void change(int nl, int nr, int l, int r, int rt, int k) {
  if (nl <= l && r <= nr) {
    f(l, r, rt, k);
    return;
  }
  pushdown(l, r, rt);
  int mid = (l + r) >> 1;
  if (nl <= mid) change(nl, nr, l, mid, rt << 1, k);
  if (nr > mid) change(nl, nr, mid + 1, r, rt << 1 | 1, k);
  pushup(rt);
}
int tree_query(int nl, int nr, int l, int r, int rt, int k) {
  pushdown(l, r, rt);
  if (tree[rt] > k) return 1000000007;
  if (nl <= l && r <= nr) {
    if (l == r)
      return l;
    else {
      int mid = (l + r) >> 1;
      if (tree[rt << 1] <= k)
        return tree_query(nl, nr, l, mid, rt << 1, k);
      else
        return tree_query(nl, nr, mid + 1, r, rt << 1 | 1, k);
    }
  }
  int mid = (l + r) >> 1, res = 1000000007;
  if (nl <= mid) res = tree_query(nl, nr, l, mid, rt << 1, k);
  if (nr > mid) res = min(res, tree_query(nl, nr, mid + 1, r, rt << 1 | 1, k));
  return res;
}
signed main() {
  n = read(), k = read(), d = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  if (d == 0) {
    int len = 0, res = 0;
    a[n + 1] = 1000000007;
    for (int i = 1; i <= n + 1; i++) {
      if (a[i] != a[i - 1]) {
        if (len > res) {
          res = len, ansl = i - len, ansr = i - 1;
        }
        len = 1;
      } else
        len++;
    }
    cout << ansl << ' ' << ansr << endl;
    return 0;
  }
  lim[1] = 1;
  for (int i = 2; i <= n; i++) {
    if ((a[i] % d + d) % d == (a[i - 1] % d + d) % d)
      lim[i] = lim[i - 1];
    else
      lim[i] = i;
  }
  for (int i = 1; i <= n; i++)
    lim[i] = max(lim[i], max(lim[i - 1], la[a[i]] + 1)), la[a[i]] = i;
  build_tree(1, n, 1);
  for (int i = 1; i <= n; i++) {
    if (a[i] >= 0)
      a[i] /= d;
    else {
      if (a[i] % d == 0)
        a[i] /= d;
      else
        a[i] = (a[i] / d) - 1;
    }
  }
  for (int i = 1; i <= n; i++) {
    while (pos1 > 0 && maxval[pos1] <= a[i]) {
      change(maxt[pos1 - 1] + 1, maxt[pos1], 1, n, 1, -maxval[pos1]);
      pos1--;
    }
    while (pos2 > 0 && minval[pos2] >= a[i]) {
      change(mint[pos2 - 1] + 1, mint[pos2], 1, n, 1, minval[pos2]);
      pos2--;
    }
    change(maxt[pos1] + 1, i, 1, n, 1, a[i]);
    change(mint[pos2] + 1, i, 1, n, 1, -a[i]);
    maxt[++pos1] = i, maxval[pos1] = a[i];
    mint[++pos2] = i, minval[pos2] = a[i];
    int le = tree_query(lim[i], i, 1, n, 1, k + i);
    if (i - le + 1 > maxv) ansl = le, ansr = i, maxv = i - le + 1;
  }
  cout << ansl << ' ' << ansr << endl;
  return 0;
}
