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 int MAXN = 2e5 + 10;
vector<int> y;
stack<pair<int, int> > w;
stack<pair<int, int> > z;
int a[MAXN];
int pre[MAXN];
int last[MAXN];
int lazy[4 * MAXN];
int segt[4 * MAXN];
int n, k, d;
void lzu(int id) {
  segt[2 * id + 1] += lazy[id];
  lazy[2 * id + 1] += lazy[id];
  segt[2 * id + 2] += lazy[id];
  lazy[2 * id + 2] += lazy[id];
  lazy[id] = 0;
}
void update(int id, int L, int R, int l, int r, int val) {
  if (L > r || R < l) {
    return;
  }
  if (L >= l && R <= r) {
    segt[id] += val;
    lazy[id] += val;
    return;
  }
  lzu(id);
  int mid = (L + R) / 2;
  update(2 * id + 1, L, mid, l, r, val);
  update(2 * id + 2, mid + 1, R, l, r, val);
  segt[id] = min(segt[2 * id + 1], segt[2 * id + 2]);
}
int get_res(int id, int L, int R, int l, int r, int val) {
  if (L > r || R < l) {
    return -1;
  }
  if (L >= l && R <= r) {
    if (segt[id] - val <= k) {
      while (L != R) {
        lzu(id);
        int mid = (L + R) / 2;
        if (segt[2 * id + 1] - val > k) {
          L = mid + 1;
          id = 2 * id + 2;
        } else {
          R = mid;
          id = 2 * id + 1;
        }
      }
      return L;
    } else {
      return -1;
    }
  }
  lzu(id);
  int mid = (L + R) / 2;
  int d = get_res(2 * id + 1, L, mid, l, r, val);
  if (d != -1) {
    return d;
  } else {
    return get_res(2 * id + 2, mid + 1, R, l, r, val);
  }
}
pair<int, int> max_sz(pair<int, int> x, pair<int, int> y) {
  if ((x.second - x.first + 1) == (y.second - y.first + 1)) {
    return (x.first < y.first ? x : y);
  }
  return ((x.second - x.first + 1) > (y.second - y.first + 1) ? x : y);
}
pair<int, int> solve(int l, int r) {
  if (l > r) {
    return make_pair(1, 1);
  }
  while (!w.empty()) {
    w.pop();
  }
  while (!z.empty()) {
    z.pop();
  }
  int p = l;
  pair<int, int> res = make_pair(l, l);
  for (int i = l; i <= r; i++) {
    a[i] /= d;
    update(0, 1, n, i, i, i);
    int f = i;
    while (!w.empty() && w.top().first >= a[i]) {
      update(0, 1, n, w.top().second, f - 1, w.top().first);
      f = w.top().second;
      w.pop();
    }
    w.push(make_pair(a[i], f));
    update(0, 1, n, f, i, -a[i]);
    f = i;
    while (!z.empty() && z.top().first <= a[i]) {
      update(0, 1, n, z.top().second, f - 1, -z.top().first);
      f = z.top().second;
      z.pop();
    }
    z.push(make_pair(a[i], f));
    update(0, 1, n, f, i, a[i]);
    p = max(p, pre[i] + 1);
    res = max_sz(res, make_pair(get_res(0, 1, n, p, i, i), i));
  }
  return res;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k >> d;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    y.push_back(a[i]);
  }
  sort(y.begin(), y.end());
  y.resize(unique(y.begin(), y.end()) - y.begin());
  for (int i = 1; i <= n; i++) {
    int t = lower_bound(y.begin(), y.end(), a[i]) - y.begin() + 1;
    pre[i] = last[t];
    last[t] = i;
  }
  int p = -1, x = 1;
  pair<int, int> res = make_pair(1, 1);
  if (d == 0) {
    for (int i = 1; i <= n; i++) {
      if (i == 1 || a[i] != a[i - 1]) {
        int r = i;
        while (r < n && a[r + 1] == a[i]) {
          r++;
        }
        res = max_sz(res, make_pair(i, r));
      }
    }
    cout << res.first << " " << res.second << endl;
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    if (((a[i] % d) >= 0 ? (a[i] % d) : (a[i] % d) + d) != p) {
      res = max_sz(res, solve(x, i - 1));
      x = i;
      p = ((a[i] % d) >= 0 ? (a[i] % d) : (a[i] % d) + d);
    }
  }
  res = max_sz(res, solve(x, n));
  cout << res.first << " " << res.second;
}
