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 N = 2e5 + 100;
const long long int mod = 1e9 + 7;
const int lg = 20;
const long long int inf = 1e16;
int n, ans = 0, k, d, ansl = 0, ansr = 0;
map<int, int> last;
long long int seg[4 * N], lazy[4 * N], a[N];
deque<pair<int, pair<int, int>>> mn, mx;
void upd(int ind) {
  seg[ind * 2] += lazy[ind];
  seg[ind * 2 + 1] += lazy[ind];
  lazy[ind * 2] += lazy[ind];
  lazy[ind * 2 + 1] += lazy[ind];
  lazy[ind] = 0;
}
void add(int l, int r, long long int val, int b = 0, int e = n, int ind = 1) {
  if (e <= l || r <= b) return;
  if (l <= b && e <= r) {
    seg[ind] += val;
    lazy[ind] += val;
    return;
  }
  upd(ind);
  int mid = (b + e) / 2;
  add(l, r, val, b, mid, ind * 2);
  add(l, r, val, mid, e, ind * 2 + 1);
  seg[ind] = min(seg[ind * 2], seg[ind * 2 + 1]);
}
int get(int b = 0, int e = n, int ind = 1) {
  if (b + 1 == e) {
    return b;
  }
  upd(ind);
  int mid = (b + e) / 2;
  if (seg[ind * 2] <= 0) return get(b, mid, ind * 2);
  return get(mid, e, ind * 2 + 1);
}
void solve(int b, int e) {
  for (int i = b; i < e; i++) {
    a[i] /= d;
    last[a[i]] = -1;
  }
  int pt = b;
  for (int i = b; i < e; i++) {
    if (last[a[i]] != -1) add(pt, last[a[i]] + 1, inf);
    pt = max(pt, last[a[i]] + 1);
    last[a[i]] = i;
    add(i, i + 1, -k);
    add(pt, i, -1);
    int l = i, r, x;
    while (!mn.empty() && mn.front().first >= a[i]) {
      l = max(pt, mn.front().second.first);
      r = max(pt, mn.front().second.second);
      x = mn.front().first;
      add(l, r, x - a[i]);
      mn.pop_front();
    }
    mn.push_front({a[i], {l, i + 1}});
    l = i;
    while (!mx.empty() && mx.front().first <= a[i]) {
      l = max(pt, mx.front().second.first);
      r = max(pt, mx.front().second.second);
      x = mx.front().first;
      add(l, r, a[i] - x);
      mx.pop_front();
    }
    mx.push_front({a[i], {l, i + 1}});
    l = get();
    if (ans < i - l + 1 || (ans == i - l + 1 && l < ansl)) {
      ans = i - l + 1;
      ansl = l;
      ansr = i;
    }
  }
  mx.clear();
  mn.clear();
  add(b, e, inf);
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k >> d;
  long long int m = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    m = min(m, a[i]);
  }
  if (m < 0) {
    for (int i = 0; i < n; i++) a[i] -= m;
  }
  if (d == 0) {
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
      if (a[i] == a[l])
        r = i;
      else
        r = l = i;
      if (ans < r - l + 1) {
        ans = r - l + 1;
        ansl = l;
        ansr = r;
      }
    }
    cout << ansl + 1 << ' ' << ansr + 1 << endl;
    return 0;
  }
  long long int r = a[0] % d, l = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] % d != r) {
      solve(l, i);
      l = i;
      r = a[i] % d;
    }
  }
  solve(l, n);
  cout << ansl + 1 << ' ' << ansr + 1 << endl;
  return 0;
}
