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 INF = 1e16;
int ansl = 1, ansr = 1;
long long mi[200200 << 2], tg[200200 << 2];
void build(int l, int r, int pos) {
  tg[pos] = 0;
  if (l == r) return mi[pos] = l, void();
  int mid = (l + r) >> 1;
  build(l, mid, (pos << 1)), build(mid + 1, r, (pos << 1 | 1));
  mi[pos] = min(mi[(pos << 1)], mi[(pos << 1 | 1)]);
}
void add(int pos, int w) { mi[pos] += w, tg[pos] += w; }
void pushdown(int pos) {
  if (tg[pos]) {
    add((pos << 1), tg[pos]);
    add((pos << 1 | 1), tg[pos]);
    tg[pos] = 0;
  }
}
void modify(int L, int R, long long w, int l, int r, int pos) {
  if (L <= l && r <= R) return add(pos, w);
  int mid = (l + r) >> 1;
  pushdown(pos);
  if (L <= mid) modify(L, R, w, l, mid, (pos << 1));
  if (mid < R) modify(L, R, w, mid + 1, r, (pos << 1 | 1));
  mi[pos] = min(mi[(pos << 1)], mi[(pos << 1 | 1)]);
}
int query(int w, int l, int r, int pos) {
  if (l == r) return mi[pos] <= w ? l : -1;
  pushdown(pos);
  int mid = (l + r) >> 1;
  return mi[(pos << 1)] <= w ? query(w, l, mid, (pos << 1))
                             : query(w, mid + 1, r, (pos << 1 | 1));
}
void chk(int l, int r) {
  if (r - l > ansr - ansl || (r - l == ansr - ansl && l < ansl))
    ansl = l, ansr = r;
}
long long qmin(int x, int l, int r, int pos) {
  if (l == r) return mi[pos];
  int mid = (l + r) >> 1;
  return x <= mid ? qmin(x, l, mid, (pos << 1))
                  : qmin(x, mid + 1, r, (pos << 1 | 1));
}
int smi[200200], tmi, smx[200200], tmx;
map<int, int> las;
void work(int *a, int n, int m, int dlt) {
  build(1, n, 1);
  tmi = tmx = 0, las.clear();
  int lasi = 1;
  for (int i = 1; i <= n; ++i) {
    while (tmi && a[smi[tmi]] > a[i])
      modify(smi[tmi - 1] + 1, smi[tmi], a[smi[tmi]], 1, n, 1), tmi--;
    modify(smi[tmi] + 1, i, -a[i], 1, n, 1), smi[++tmi] = i;
    while (tmx && a[smx[tmx]] < a[i])
      modify(smx[tmx - 1] + 1, smx[tmx], -a[smx[tmx]], 1, n, 1), tmx--;
    modify(smx[tmx] + 1, i, a[i], 1, n, 1), smx[++tmx] = i;
    if (int tmp = las[a[i]])
      if (lasi <= tmp) modify(lasi, tmp, INF, 1, n, 1), lasi = tmp;
    las[a[i]] = i;
    int l = query(m + i, 1, n, 1);
    assert(l);
    if (l > 0 && l <= i) chk(l + dlt, i + dlt);
  }
}
int main() {
  static int n, m, d, a[200200];
  cin >> n >> m >> d;
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  if (!d) {
    for (int l = 1, r; l <= n; l = r + 1) {
      for (r = l; r < n && a[r + 1] == a[l]; ++r)
        ;
      chk(l, r);
    }
    cout << ansl << " " << ansr << endl;
    return 0;
  }
  for (int l = 1, r; l <= n; l = r + 1) {
    for (r = l; r < n && (a[r + 1] % d + d) % d == (a[l] % d + d) % d; ++r)
      ;
    int tmp = 0;
    for (int i = l; i <= r; ++i) tmp = min(tmp, a[i]);
    for (int i = l; i <= r; ++i) a[i] = (a[i] - tmp) / d;
    work(a + l - 1, r - l + 1, m, l - 1);
  }
  cout << ansl << ' ' << ansr << endl;
  return 0;
}
