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>
bool upmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
T Min(const T &a, const T &b) {
  return a < b ? a : b;
}
template <class T>
T Abs(const T &a) {
  return a > 0 ? a : -a;
}
const long long LLF = (~0LLU >> 1) - 10;
long long getx() {
  char c;
  long long x;
  bool pd = 0;
  for (c = getchar(); c != '-' && (c < '0' || c > '9'); c = getchar())
    ;
  if (c == '-') pd = 1, c = getchar();
  for (x = 0; c >= '0' && c <= '9'; c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  return pd ? -x : x;
}
const int MAX_N = 200050;
int n, k;
long long d;
long long a[MAX_N];
namespace zeroD {
void solve() {
  int l = 1, L = 1, R = 1;
  a[n + 1] = -1;
  for (int i = 1; i <= n + 1; ++i)
    if (a[i] != a[l]) {
      if (i - l > R - L + 1) L = l, R = i - 1;
      l = i;
    }
  printf("%d %d\n", L, R);
  exit(0);
}
}  // namespace zeroD
namespace positiveD {
struct Segment_Tree {
  long long k[MAX_N << 2], tag[MAX_N << 2];
  void up(int v) { k[v] = Min(k[v << 1], k[v << 1 | 1]); }
  void down(int v) {
    if (tag[v]) {
      k[v << 1] += tag[v];
      k[v << 1 | 1] += tag[v];
      tag[v << 1] += tag[v];
      tag[v << 1 | 1] += tag[v];
      tag[v] = 0;
    }
  }
  void modify(int v, int l, int r, int s, int t, long long x) {
    if (s <= l && r <= t) {
      k[v] += x;
      tag[v] += x;
      return;
    }
    down(v);
    int mid = l + r >> 1;
    if (s <= mid) modify(v << 1, l, mid, s, t, x);
    if (t > mid) modify(v << 1 | 1, mid + 1, r, s, t, x);
    up(v);
  }
  long long query(int v, int l, int r, int s, int t) {
    if (s <= l && r <= t) return k[v];
    down(v);
    int mid = l + r >> 1;
    long long res = LLF;
    if (s <= mid) res = query(v << 1, l, mid, s, t);
    if (t > mid) upmin(res, query(v << 1 | 1, mid + 1, r, s, t));
    up(v);
    return res;
  }
  int getr(int v, int l, int r, int s, int t, long long x) {
    if (r < s || l > t) return -1;
    if (l == r) return l;
    down(v);
    int mid = l + r >> 1;
    int tp = -1;
    if (k[v << 1 | 1] <= x)
      if (-1 != (tp = getr(v << 1 | 1, mid + 1, r, s, t, x))) return tp;
    if (k[v << 1] <= x)
      if (-1 != (tp = getr(v << 1, l, mid, s, t, x))) return tp;
    return tp;
  }
} T;
std::map<long long, int> suf;
int R[MAX_N];
int max[MAX_N], min[MAX_N];
int pL, C = 0;
void calc() {
  int hx = 0, hn = 0;
  max[0] = min[0] = n + 1;
  for (int L = n; L >= 1; --L) {
    T.modify(1, 1, n, L, L, -L);
    while (hx >= 1 && a[L] >= a[max[hx]]) {
      T.modify(1, 1, n, max[hx], max[hx - 1] - 1, (a[L] - a[max[hx]]) / d);
      hx--;
    }
    max[++hx] = L;
    while (hn >= 1 && a[L] <= a[min[hn]]) {
      T.modify(1, 1, n, min[hn], min[hn - 1] - 1, (a[min[hn]] - a[L]) / d);
      hn--;
    }
    min[++hn] = L;
    if (R[L] - L + 1 >= C) {
      int r = T.getr(1, 1, n, L, R[L], k - L);
      if (r - L + 1 >= C) pL = L, C = r - L + 1;
    }
  }
  printf("%d %d\n", pL, pL + C - 1);
}
void solve() {
  R[n] = n;
  for (int i = n - 1; i >= 1; --i) {
    suf[a[i + 1]] = i + 1;
    if (Abs(a[i + 1] - a[i]) % d == 0)
      R[i] = R[i + 1];
    else
      R[i] = i;
    int p = suf[a[i]];
    if (p && R[i] >= p) R[i] = p - 1;
  }
  calc();
}
}  // namespace positiveD
int main() {
  n = getx(), k = getx(), d = getx();
  for (int i = 1; i <= n; ++i) a[i] = getx();
  if (d == 0) zeroD::solve();
  positiveD::solve();
}
