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;
int seg[maxn << 2], lz[maxn << 2], b[maxn], a[maxn], N, k, d;
pair<long long, long long> Ans;
vector<int> ma, mi;
void upd(int x, int val) {
  lz[x] += val;
  seg[x] += val;
}
void shift(int x) {
  if (!lz[x]) return;
  upd(x * 2, lz[x]);
  upd(x * 2 + 1, lz[x]);
  lz[x] = 0;
}
void add(int i, int j, int x, int l, int r, int val) {
  if (i >= r || j <= l) return;
  if (i >= l && j <= r) {
    upd(x, val);
    return;
  }
  int md = (i + j) >> 1;
  shift(x);
  add(i, md, x * 2, l, r, val);
  add(md, j, x * 2 + 1, l, r, val);
  seg[x] = min(seg[x * 2], seg[x * 2 + 1]);
}
void build(int i, int j, int x) {
  seg[x] = lz[x] = 0;
  if (i + 1 == j) return;
  int md = (i + j) >> 1;
  build(i, md, x * 2);
  build(md, j, x * 2 + 1);
}
int bs(int i, int j, int x, int l, int r) {
  if (i >= r || j <= l || seg[x] > k) return maxn - 1;
  if (i + 1 == j) {
    return i;
  }
  shift(x);
  int md = (i + j) >> 1;
  if (i >= l && j <= r) {
    if (seg[x * 2] <= k) return bs(i, md, x * 2, l, r);
    return bs(md, j, x * 2 + 1, l, r);
  }
  int ret = bs(i, md, x * 2, l, r);
  if (ret != maxn - 1) return ret;
  return bs(md, j, x * 2 + 1, l, r);
}
void solve(int n, int Firs) {
  map<int, int> mp;
  for (int y = 1; y <= n; y++) a[y] /= d;
  ma.push_back(0);
  mi.push_back(0);
  int po = 1;
  for (int y = 1; y <= n; y++) {
    po = max(po, mp[a[y]] + 1);
    mp[a[y]] = y;
    if (y != 1) add(1, n + 1, 1, 1, y, -1);
    while (ma.back() && a[ma.back()] <= a[y]) {
      add(1, n + 1, 1, ma[ma.size() - 2] + 1, ma.back() + 1,
          a[y] - a[ma.back()]);
      ma.pop_back();
    }
    while (mi.back() && a[mi.back()] >= a[y]) {
      add(1, n + 1, 1, mi[mi.size() - 2] + 1, mi.back() + 1,
          -(a[y] - a[mi.back()]));
      mi.pop_back();
    }
    mi.push_back(y);
    ma.push_back(y);
    int t = bs(1, n + 1, 1, po, y + 1);
    if (y - t > Ans.second - Ans.first)
      Ans = pair<long long, long long>(t + Firs, y + Firs);
  }
  build(1, n + 1, 1);
  while (ma.size()) ma.pop_back();
  while (mi.size()) mi.pop_back();
  for (int y = 1; y <= n; y++) a[y] = 0;
}
int main() {
  cin >> N >> k >> d;
  Ans = pair<long long, long long>(1, 1);
  for (int y = 1; y <= N; y++) scanf("%d", &b[y]), b[y] += 1e9;
  if (d == 0) {
    int po = 1;
    for (int y = 2; y <= N + 1; y++) {
      if (y == N + 1 || b[y] != b[y - 1]) {
        if (Ans.second - Ans.first < (y - 1) - po)
          Ans = pair<long long, long long>(po, y - 1);
        po = y;
      }
    }
    cout << Ans.first << ' ' << Ans.second;
    return 0;
  }
  int po = 1;
  for (int y = 2; y <= N + 1; y++) {
    if (b[y] % d != b[y - 1] % d || y == N + 1) {
      for (int u = po; u < y; u++) a[u - po + 1] = b[u];
      solve(y - po, po - 1);
      po = y;
    }
  }
  cout << Ans.first << ' ' << Ans.second;
}
