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;
int n, k, d;
vector<int> a;
int L = 0, R = 1;
void update(int nl, int nr) {
  if (nr - nl > R - L || nr - nl == R - L && nl < L) {
    L = nl;
    R = nr;
  }
}
struct rtree {
  long long v[800000];
  long long o[800000];
  void clear(int i, int rs, int re) {
    if (rs + 1 == re)
      v[i] = o[i] = 0;
    else {
      int m = (rs + re) / 2;
      clear(2 * i + 1, rs, m);
      clear(2 * i + 2, m, re);
      v[i] = o[i] = 0;
    }
  }
  void inc(int i, int rs, int re, int qs, int qe, int dv) {
    if (rs == qs && re == qe) {
      v[i] += dv;
      o[i] += dv;
    } else {
      int m = (rs + re) / 2;
      if (qs < m) inc(2 * i + 1, rs, m, qs, min(qe, m), dv);
      if (qe > m) inc(2 * i + 2, m, re, max(qs, m), qe, dv);
      v[i] = o[i] + min(v[2 * i + 1], v[2 * i + 2]);
    }
  }
  int fle(int i, int rs, int re, int qe, int q) {
    if (rs + 1 == re) {
      assert(v[i] <= q);
      return rs;
    } else {
      q -= o[i];
      int m = (rs + re) / 2;
      if (qe <= m || v[2 * i + 1] <= q)
        return fle(2 * i + 1, rs, m, min(qe, m), q);
      else
        return fle(2 * i + 2, m, re, qe, q);
    }
  }
  long long q(int i, int rs, int re, int j) {
    if (rs + 1 == re)
      return v[i];
    else {
      int m = (rs + re) / 2;
      if (j < m)
        return o[i] + q(2 * i + 1, rs, m, j);
      else
        return o[i] + q(2 * i + 2, m, re, j);
    }
  }
} T;
void solve(vector<int> &v, int init) {
  for (int i = (0); i < (int)(v.size()); i++) v[i] /= d;
  map<int, int> last;
  T.clear(0, 0, v.size());
  vector<int> mx(1, 0);
  vector<int> mn(1, 0);
  last[v[0]] = 0;
  for (int i = (1); i < (int)(v.size()); i++) {
    if (last.count(v[i])) {
      T.inc(0, 0, v.size(), 0, last[v[i]] + 1, k + 2 * n);
    }
    last[v[i]] = i;
    T.inc(0, 0, v.size(), 0, i, -1);
    while (!mx.empty() && v[mx.back()] < v[i]) {
      if (mx.size() >= 2)
        T.inc(0, 0, v.size(), mx[mx.size() - 2] + 1, mx[mx.size() - 1] + 1,
              v[i] - v[mx.back()]);
      else {
        T.inc(0, 0, v.size(), 0, mx[mx.size() - 1] + 1, v[i] - v[mx.back()]);
      }
      mx.pop_back();
    }
    mx.push_back(i);
    while (!mn.empty() && v[mn.back()] > v[i]) {
      if (mn.size() >= 2)
        T.inc(0, 0, v.size(), mn[mn.size() - 2] + 1, mn[mn.size() - 1] + 1,
              v[mn.back()] - v[i]);
      else
        T.inc(0, 0, v.size(), 0, mn[mn.size() - 1] + 1, v[mn.back()] - v[i]);
      mn.pop_back();
    }
    mn.push_back(i);
    update(init + T.fle(0, 0, v.size(), i + 1, k), init + i + 1);
  }
}
int main() {
  scanf("%d %d %d", &n, &k, &d);
  a.resize(n);
  for (int i = (0); i < (int)(n); i++) {
    scanf("%d", &a[i]);
    a[i] += 1e9 + 10;
  }
  if (d == 0) {
    int p = 0;
    for (int i = (0); i < (int)(n); i++) {
      if (a[i] != a[p]) {
        update(p, i);
        p = i;
      }
    }
    update(p, n);
    printf("%d %d\n", L + 1, R);
    return 0;
  }
  vector<int> v;
  v.reserve(n);
  int init = 0;
  for (int i = (0); i < (int)(n); i++) {
    if (!v.empty() && abs(a[i] - v.back()) % d) {
      solve(v, init);
      v.clear();
      init = i;
    }
    v.push_back(a[i]);
  }
  solve(v, init);
  printf("%d %d\n", L + 1, R);
  return 0;
}
