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 long long INF = 1e10;
const int MAXN = 2.1e5;
int k;
struct seg_node {
  seg_node* c[2];
  long long maxv;
  long long lazy;
};
const int SEG_SZ = 2 * MAXN;
seg_node seg_pool[SEG_SZ];
int SEG_IND;
seg_node* alloc_seg() {
  assert(SEG_IND < SEG_SZ);
  return &seg_pool[SEG_IND++];
}
void update(seg_node* v) {
  v->maxv = max(v->c[0]->maxv, v->c[1]->maxv) + v->lazy;
}
seg_node* init_seg(int lx, int rx) {
  seg_node* v = alloc_seg();
  v->c[0] = v->c[1] = NULL;
  v->maxv = -1;
  v->lazy = 0;
  if (lx + 1 < rx) {
    v->c[0] = init_seg(lx, (lx + rx) / 2);
    v->c[1] = init_seg((lx + rx) / 2, rx);
  }
  return v;
}
void update(seg_node* v, int lx, int rx, int ulx, int urx, long long del) {
  if (urx <= lx || rx <= ulx) {
  } else if (ulx <= lx && rx <= urx) {
    v->maxv += del;
    v->lazy += del;
  } else {
    update(v->c[0], lx, (lx + rx) / 2, ulx, urx, del);
    update(v->c[1], (lx + rx) / 2, rx, ulx, urx, del);
    update(v);
  }
}
int find_last(seg_node* v, int lx, int rx, long long accum = 0) {
  if (v->maxv + accum < 0) return -1;
  if (lx + 1 == rx) {
    return lx;
  } else {
    accum += v->lazy;
    if (v->c[1]->maxv + accum >= 0) {
      return find_last(v->c[1], (lx + rx) / 2, rx, accum);
    } else {
      assert(v->c[0]->maxv + accum >= 0);
      return find_last(v->c[0], lx, (lx + rx) / 2, accum);
    }
  }
}
long long query(seg_node* v, int lx, int rx, int qx) {
  if (lx + 1 == rx) {
    assert(lx == qx);
    return v->maxv;
  } else {
    if (qx < (lx + rx) / 2) {
      return v->lazy + query(v->c[0], lx, (lx + rx) / 2, qx);
    } else {
      return v->lazy + query(v->c[1], (lx + rx) / 2, rx, qx);
    }
  }
}
vector<pair<int, int> > min_st;
vector<pair<int, int> > max_st;
pair<int, int> solve(const vector<int>& a) {
  int n = int(a.size());
  pair<int, int> ans(-1, -1);
  min_st.clear();
  max_st.clear();
  min_st.push_back(make_pair(-1e9, n));
  max_st.push_back(make_pair(2e9 + 100, n));
  SEG_IND = 0;
  seg_node* segtree = init_seg(0, n);
  map<int, int> last_seen;
  for (int i = n - 1; i >= 0; i--) {
    int cur = a[i];
    update(segtree, 0, n, i, i + 1, k + 1);
    {
      int last = i + 1;
      while (cur < min_st.back().first) {
        pair<int, int> z = min_st.back();
        min_st.pop_back();
        update(segtree, 0, n, last, z.second, -z.first);
        last = z.second;
      }
      update(segtree, 0, n, i + 1, last, cur);
      min_st.push_back(make_pair(cur, last));
    }
    {
      int last = i + 1;
      while (cur > max_st.back().first) {
        pair<int, int> z = max_st.back();
        max_st.pop_back();
        update(segtree, 0, n, last, z.second, z.first);
        last = z.second;
      }
      update(segtree, 0, n, i + 1, last, -cur);
      max_st.push_back(make_pair(cur, last));
    }
    update(segtree, 0, n, i + 1, n, 1);
    if (last_seen.count(cur)) {
      update(segtree, 0, n, last_seen[cur], n, -INF);
    }
    last_seen[cur] = i;
    int best = find_last(segtree, 0, n);
    assert(best >= 0);
    pair<int, int> cnd(best - i + 1, -i);
    ans = max(ans, cnd);
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, d;
  cin >> n >> k >> d;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] += int(1e9);
  }
  pair<int, int> ans(-1, -1);
  if (d == 0) {
    for (int s = 0, e = 0; s < n; s = e) {
      while (e < n && a[s] == a[e]) e++;
      ans = max(ans, make_pair(e - s, -s));
    }
  } else {
    min_st.reserve(n + 1);
    max_st.reserve(n + 1);
    vector<int> b;
    b.reserve(n);
    for (int s = 0, e = 0; s < n; s = e) {
      b.clear();
      while (e < n && a[s] % d == a[e] % d) {
        b.push_back(a[e] / d);
        e++;
      }
      pair<int, int> cnd = solve(b);
      cnd.second -= s;
      ans = max(ans, cnd);
    }
  }
  int l = -ans.second;
  int r = l + ans.first;
  cout << l + 1 << ' ' << r << '\n';
}
