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;
struct Answer {
  int ans, l, r;
  Answer() { ans = -1, l = r = 0; }
  Answer(int l, int r) : ans(r - l + 1), l(l), r(r) {}
  int operator<(const Answer& d) const {
    if (ans != d.ans) return ans < d.ans;
    return l > d.l;
  }
} ans;
map<int, int> cnt;
int pre[200100], pre2[200100];
int n, a[200100], stmn[200100], stmx[200100], tp1, tp2, d, K;
long long atg[200100 << 2];
pair<long long, int> s[200100 << 2];
void pd(int o) {
  if (atg[o]) {
    atg[o << 1] += atg[o];
    atg[o << 1 | 1] += atg[o];
    s[o << 1].first += atg[o];
    s[o << 1 | 1].first += atg[o];
    atg[o] = 0;
  }
}
void upd(int o) { s[o] = min(s[o << 1], s[o << 1 | 1]); }
void mdy(int o, int l, int r, int ql, int qr, int x) {
  if (ql <= l && r <= qr) {
    s[o].first += x;
    atg[o] += x;
    return;
  }
  int mid = l + r >> 1;
  pd(o);
  if (ql <= mid) mdy(o << 1, l, mid, ql, qr, x);
  if (qr > mid) mdy(o << 1 | 1, mid + 1, r, ql, qr, x);
  upd(o);
}
int qry(int o, int l, int r, int ql, int qr, long long x) {
  if (s[o].first > x) return -1;
  if (l == r) return l;
  int ans = -1, mid = l + r >> 1;
  pd(o);
  if (ql <= mid) ans = qry(o << 1, l, mid, ql, qr, x);
  if (qr > mid && ans == -1) ans = qry(o << 1 | 1, mid + 1, r, ql, qr, x);
  return ans;
}
void build(int o, int l, int r) {
  if (l == r) {
    s[o] = pair<long long, int>((long long)l * d, l);
    return;
  }
  int mid = l + r >> 1;
  build(o << 1, l, mid);
  build(o << 1 | 1, mid + 1, r);
  upd(o);
}
int main() {
  scanf("%d%d%d", &n, &K, &d);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  if (d == 0) {
    int lst = 0;
    for (int i = 1; i <= n; ++i)
      if (i == 1 || a[i] != a[i - 1])
        ans = max(ans, Answer(lst + 1, i - 1)), lst = i - 1;
    ans = max(ans, Answer(lst + 1, n));
    printf("%d %d\n", ans.l, ans.r);
    return 0;
  } else {
    int lst = 0;
    for (int i = 1; i <= n; ++i) {
      pre[i - 1] = lst + 1;
      if (i == 1 || (a[i] % d + d) % d != (a[i - 1] % d + d) % d) lst = i - 1;
    }
    pre[n] = lst + 1;
    build(1, 1, n);
    Answer ans;
    for (int i = 1, l = 1; i <= n; ++i) {
      cnt[a[i]]++;
      while (cnt[a[i]] >= 2) cnt[a[l]]--, l++;
      while (tp1 && a[stmn[tp1]] > a[i])
        mdy(1, 1, n, stmn[tp1 - 1] + 1, stmn[tp1], a[stmn[tp1]]), tp1--;
      while (tp2 && a[stmx[tp2]] < a[i])
        mdy(1, 1, n, stmx[tp2 - 1] + 1, stmx[tp2], -a[stmx[tp2]]), tp2--;
      mdy(1, 1, n, stmn[tp1] + 1, i, -a[i]), stmn[++tp1] = i;
      mdy(1, 1, n, stmx[tp2] + 1, i, a[i]), stmx[++tp2] = i;
      int pos = qry(1, 1, n, max(l, pre[i]), i, 1ll * (K + i) * d);
      if (pos != -1) ans = max(ans, Answer(pos, i));
    }
    printf("%d %d\n", ans.l, ans.r);
  }
}
