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 = 202020;
int n, k, d, sp, bp;
int a[N], b[N], ma[N << 2], la[N << 2], mi[N << 2];
struct NN {
  int l, r, w;
} ss[N], bs[N];
void up(int rt) {
  ma[rt] = max(ma[rt << 1], ma[rt << 1 | 1]);
  mi[rt] = min(mi[rt << 1], mi[rt << 1 | 1]);
}
void build(int l = 1, int r = n, int rt = 1) {
  la[rt] = 0;
  if (l == r) {
    ma[rt] = mi[rt] = -l;
    return;
  }
  int mid = l + r >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  up(rt);
}
void down(int rt) {
  if (la[rt]) {
    int c = la[rt];
    int L = (rt << 1), R = (L | 1);
    ma[L] += c;
    ma[R] += c;
    mi[L] += c;
    mi[R] += c;
    la[L] += c;
    la[R] += c;
    la[rt] = 0;
  }
}
void upd(int L, int R, int c, int l = 1, int r = n, int rt = 1) {
  if (L <= l && r <= R) {
    ma[rt] += c;
    mi[rt] += c;
    la[rt] += c;
    return;
  }
  int mid = l + r >> 1;
  down(rt);
  if (L <= mid) upd(L, R, c, l, mid, rt << 1);
  if (R >= mid + 1) upd(L, R, c, mid + 1, r, rt << 1 | 1);
  up(rt);
}
int qry(int L, int R, int u, int l = 1, int r = n, int rt = 1) {
  if (L <= l && r <= R) {
    if (mi[rt] > u) return -1;
    if (l == r) return l;
  }
  int mid = l + r >> 1;
  down(rt);
  int ans = -1;
  if (R >= mid + 1) ans = qry(L, R, u, mid + 1, r, rt << 1 | 1);
  if (L <= mid && ans == -1) ans = qry(L, R, u, l, mid, rt << 1);
  up(rt);
  return ans;
}
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int i = (1); i < (n + 1); i++) scanf("%d", a + i);
  int st = 1, ed = 1;
  if (!d) {
    for (int l = 1, r = 1; r <= n; ++r) {
      if (a[l] != a[r]) ++l;
      if (r - l > ed - st) {
        ed = r;
        st = l;
      }
    }
  } else {
    for (int i = (1); i < (n + 1); i++) b[i] = (a[i] % d + d) % d;
    for (int i = (1); i < (n + 1); i++) a[i] = (a[i] - b[i]) / d;
    build();
    int ri = n;
    map<int, int> vis;
    for (int i = n; i; --i) {
      if (i < n && b[i] != b[i + 1]) ri = i;
      if (vis.count(a[i])) ri = min(ri, vis[a[i]] - 1);
      vis[a[i]] = i;
      while (sp && ss[sp].w >= a[i]) {
        upd(ss[sp].l, ss[sp].r, ss[sp].w);
        --sp;
      }
      ++sp;
      ss[sp].l = i;
      ss[sp].r = (sp == 1) ? n : ss[sp - 1].l - 1;
      ss[sp].w = a[i];
      upd(ss[sp].l, ss[sp].r, -ss[sp].w);
      while (bp && bs[bp].w <= a[i]) {
        upd(bs[bp].l, bs[bp].r, -bs[bp].w);
        --bp;
      }
      ++bp;
      bs[bp].l = i;
      bs[bp].r = (bp == 1) ? n : bs[bp - 1].l - 1;
      bs[bp].w = a[i];
      upd(bs[bp].l, bs[bp].r, bs[bp].w);
      int id = qry(i, ri, k - i);
      if (id != -1 && id - i >= ed - st) {
        ed = id;
        st = i;
      }
    }
  }
  printf("%d %d\n", st, ed);
  return 0;
}
