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 int maxn = (3e5) + 10, mod = 1e9 + 7, inff = 1e15, inf = 1e9;
long long int n, k, d, a[maxn], seg[4 * maxn], lazy[4 * maxn], anss, pnt, ppnt;
map<long long int, long long int> lst;
void shift(long long int s, long long int e, long long int id) {
  seg[2 * id] += lazy[id];
  seg[2 * id + 1] += lazy[id];
  lazy[2 * id] += lazy[id];
  lazy[2 * id + 1] += lazy[id];
  lazy[id] = 0;
}
void upd(long long int l, long long int r, long long int x, long long int s = 0,
         long long int e = n, long long int id = 1) {
  if (l == -1) return;
  if (r == 0) return;
  if (r <= s || e <= l) return;
  if (l <= s && e <= r) {
    seg[id] += x;
    lazy[id] += x;
    return;
  }
  long long int mid = (s + e) >> 1;
  shift(s, e, id);
  upd(l, r, x, s, mid, 2 * id);
  upd(l, r, x, mid, e, 2 * id + 1);
  seg[id] = min(seg[2 * id], seg[2 * id + 1]);
}
long long int get(long long int s = 0, long long int e = n,
                  long long int id = 1) {
  if (s == e - 1) return s;
  long long int mid = (s + e) >> 1;
  shift(s, e, id);
  if (seg[2 * id] <= 0) return get(s, mid, 2 * id);
  if (seg[2 * id + 1] <= 0) return get(mid, e, 2 * id + 1);
}
void deb(long long int s = 0, long long int e = n, long long int id = 1) {
  if (s == e - 1) {
    cout << seg[id] << ' ';
    return;
  }
  shift(s, e, id);
  long long int mid = (s + e) >> 1;
  deb(s, mid, 2 * id);
  deb(mid, e, 2 * id + 1);
}
void solve(long long int L, long long int R) {
  stack<pair<long long int, long long int> > mni, mxi;
  mni.push({-inff, L - 1});
  mxi.push({inff, L - 1});
  for (long long int i = L; i <= R; i++) {
    upd(0, lst[a[i]], 10 * inf);
    lst[a[i]] = i + 1;
    while (a[i] >= mxi.top().first) {
      long long int id = mxi.top().second;
      long long int val = mxi.top().first;
      mxi.pop();
      long long int idd = mxi.top().second;
      upd(idd + 1, id + 1, -val);
    }
    upd(mxi.top().second + 1, i + 1, a[i]);
    mxi.push({a[i], i});
    while (a[i] <= mni.top().first) {
      long long int id = mni.top().second;
      long long int val = mni.top().first;
      mni.pop();
      long long int idd = mni.top().second;
      upd(idd + 1, id + 1, +val);
    }
    upd(mni.top().second + 1, i + 1, -a[i]);
    mni.push({a[i], i});
    if (i != 0) upd(0, n, -1);
    long long int aa = pnt, bb = ppnt;
    if (seg[1] > 0) continue;
    long long int o = get();
    long long int res = i - o + 1;
    if (anss < res) {
      anss = max(anss, res);
      pnt = o + 1;
      ppnt = i + 1;
    }
  }
  upd(L, R + 1, inf * 10);
  return;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> k >> d;
  for (long long int i = 0; i < n; i++) cin >> a[i];
  if (d == 0) {
    long long int ans = 1;
    long long int L = 0;
    for (long long int i = 0; i < n; i++) {
      long long int res = 1;
      long long int p = i;
      while (i < n - 1 && a[i] == a[i + 1]) {
        i++;
        res++;
      }
      res = (i - p) + 1;
      if (ans < res) {
        ans = max(ans, res);
        L = p;
      }
    }
    return cout << L + 1 << ' ' << L + 1 + ans - 1 << endl, 0;
  }
  vector<pair<long long int, long long int> > ba;
  for (long long int i = 0; i < n; i++) upd(i, i + 1, i);
  upd(0, n, -k);
  long long int x = 1e9;
  for (long long int i = 0; i < n; i++) a[i] += x;
  for (long long int i = 0; i < n; i++) {
    long long int pn = i + 1;
    ba.push_back({i, 0});
    while (i < n - 1 && (a[i] % d == a[i + 1] % d)) i++;
    ba[ba.size() - 1].second = i;
  }
  long long int ans = 0;
  for (long long int i = 0; i < n; i++) a[i] = (a[i] - (a[i] % d)) / d;
  for (long long int i = 0; i < ba.size(); i++) {
    solve(ba[i].first, ba[i].second);
  }
  cout << pnt << ' ' << ppnt << endl;
  return 0;
}
