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>
template <class T>
inline void read(T &res) {
  res = 0;
  bool bo = 0;
  char c;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  if (c == '-')
    bo = 1;
  else
    res = c - 48;
  while ((c = getchar()) >= '0' && c <= '9')
    res = (res << 3) + (res << 1) + (c - 48);
  if (bo) res = ~res + 1;
}
template <class T>
inline T Max(const T &a, const T &b) {
  return a > b ? a : b;
}
template <class T>
inline T Min(const T &a, const T &b) {
  return a < b ? a : b;
}
const int N = 3e5 + 5, M = N << 2;
int n, rqy, q, a[N], ans, ansl, ansr, stk1[N], top1, stk2[N], top2;
long long mx[M], add[M];
std::map<int, int> orz;
void build(int l, int r, int p) {
  mx[p] = add[p] = 0;
  if (l == r) return;
  int mid = l + r >> 1;
  build(l, mid, p << 1);
  build(mid + 1, r, p << 1 | 1);
}
void down(int p) {
  add[p << 1] += add[p];
  mx[p << 1] += add[p];
  add[p << 1 | 1] += add[p];
  mx[p << 1 | 1] += add[p];
  add[p] = 0;
}
void change(int l, int r, int s, int e, long long v, int p) {
  if (e < l || s > r) return;
  if (s <= l && r <= e) return (void)(mx[p] += v, add[p] += v);
  int mid = l + r >> 1;
  down(p);
  change(l, mid, s, e, v, p << 1);
  change(mid + 1, r, s, e, v, p << 1 | 1);
  mx[p] = Min(mx[p << 1], mx[p << 1 | 1]);
}
int query(int l, int r, long long v, int p) {
  if (l == r) return l;
  int mid = l + r >> 1;
  down(p);
  if (mx[p << 1] <= v)
    return query(l, mid, v, p << 1);
  else
    return query(mid + 1, r, v, p << 1 | 1);
}
int first(int l, int r, int s, int e, long long v, int p) {
  if (e < l || s > r) return 0;
  if (s <= l && r <= e) return mx[p] <= v ? query(l, r, v, p) : 0;
  int mid = l + r >> 1;
  down(p);
  int tmp = first(l, mid, s, e, v, p << 1);
  return tmp ? tmp : first(mid + 1, r, s, e, v, p << 1 | 1);
}
void jiejuediao(int L, int R) {
  orz.clear();
  top1 = top2 = 0;
  build(L, R, 1);
  int lst = L - 1;
  stk1[0] = stk2[0] = L - 1;
  for (int i = L; i <= R; i++) {
    while (top1 && a[stk1[top1]] > a[i]) {
      change(L, R, stk1[top1 - 1] + 1, stk1[top1], a[stk1[top1]], 1);
      top1--;
    }
    stk1[++top1] = i;
    change(L, R, stk1[top1 - 1] + 1, stk1[top1], -a[i], 1);
    while (top2 && a[stk2[top2]] < a[i]) {
      change(L, R, stk2[top2 - 1] + 1, stk2[top2], -a[stk2[top2]], 1);
      top2--;
    }
    stk2[++top2] = i;
    change(L, R, stk2[top2 - 1] + 1, stk2[top2], a[i], 1);
    change(L, R, i, i, 1ll * rqy * i, 1);
    if (orz.count(a[i])) lst = Max(lst, orz[a[i]]);
    orz[a[i]] = i;
    int lef = first(L, R, lst + 1, i, 1ll * rqy * (i + q), 1);
    if (i - lef + 1 > ans || (i - lef + 1 == ans && lef < ansl))
      ans = i - lef + 1, ansl = lef, ansr = i;
  }
}
int main() {
  read(n);
  read(q);
  read(rqy);
  for (int i = 1; i <= n; i++) read(a[i]);
  if (rqy == 0) {
    for (int i = 1, j = 1; i <= n; i++) {
      if (i > 1 && a[i] != a[i - 1]) j = i;
      if (i - j + 1 > ans) ans = i - j + 1, ansl = j, ansr = i;
    }
    std::cout << ansl << " " << ansr << std::endl;
    return 0;
  }
  for (int i = 1; i <= n;) {
    int nxt = i;
    while (nxt <= n && (nxt == i || ((a[nxt] % rqy + rqy) % rqy ==
                                     (a[nxt - 1] % rqy + rqy) % rqy)))
      nxt++;
    jiejuediao(i, nxt - 1);
    i = nxt;
  }
  return std::cout << ansl << " " << ansr << std::endl, 0;
}
