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 N = 2e5 + 5;
long long n, k, d, a[N], seg[N << 2], lazy[N << 2], ansl, ansr;
void add(int id, long long val) {
  seg[id] += val;
  lazy[id] += val;
}
void shift(int id) {
  long long &l = lazy[id];
  add(id << 1, l);
  add(id << 1 | 1, l);
  l = 0;
}
void update(int l, int r, long long val, int st = 0, int en = n, int id = 1) {
  if (l <= st && en <= r) return add(id, val);
  if (r <= st || en <= l) return;
  shift(id);
  int mid = st + en >> 1;
  update(l, r, val, st, mid, id << 1);
  update(l, r, val, mid, en, id << 1 | 1);
  seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}
int get(int l, int r, int st = 0, int en = n, int id = 1) {
  if (r <= st || en <= l || seg[id] > k) return -1;
  if (en - st == 1) return st;
  shift(id);
  int mid = st + en >> 1, res = get(l, r, st, mid, id << 1);
  return res == -1 ? get(l, r, mid, en, id << 1 | 1) : res;
}
void solve(int l, int r) {
  unordered_map<int, int> cnt;
  vector<int> mx(1, l), mn(1, l);
  for (int i = l; i < r; i++) {
    a[i] = (a[i] + 1e9) / d;
    while (cnt[a[i]]) {
      cnt[a[l]]--;
      l++;
    }
    cnt[a[i]] = 1;
    update(l, i, -1);
    while (mx.size() > 1 && a[mx.back() - 1] <= a[i]) {
      update(mx[mx.size() - 2], mx.back(), a[i] - a[mx.back() - 1]);
      mx.pop_back();
    }
    mx.push_back(i + 1);
    while (mn.size() > 1 && a[mn.back() - 1] >= a[i]) {
      update(mn[mn.size() - 2], mn.back(), a[mn.back() - 1] - a[i]);
      mn.pop_back();
    }
    mn.push_back(i + 1);
    int j = get(l, i + 1);
    if (i - j > ansr - ansl) {
      ansl = j;
      ansr = i;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k >> d;
  for (int i = 0; i < n; i++) cin >> a[i];
  if (d == 0)
    for (int l = 0, r = 0; r < n; l = r) {
      while (a[r] == a[l] && r < n) r++;
      if (r - l - 1 > ansr - ansl) {
        ansl = l;
        ansr = r - 1;
      }
    }
  else
    for (int l = 0, r = 0; r < n; l = r) {
      while ((a[r] - a[l]) % d == 0 && r < n) r++;
      solve(l, r);
    }
  cout << ansl + 1 << ' ' << ansr + 1 << endl;
}
