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 = int(2e5 + 5);
int a[N], n, d, k;
int al(1), ar(0);
void upd(int x, int y) {
  if (y - x > ar - al || (y - x == ar - al && x < al)) al = x, ar = y;
}
void work0() {
  for (int i = 1, j; i <= n; i = j + 1) {
    for (j = i; j < n && a[j + 1] == a[i]; ++j)
      ;
    upd(i, j);
  }
  printf("%d %d\n", al, ar);
}
int L[N << 2], R[N << 2], tag[N << 2], f[N << 2];
void pup(int x) { f[x] = min(f[x + x], f[x + x + 1]); }
void adtag(int x, int y) { tag[x] += y, f[x] += y; }
void pdw(int x) {
  if (tag[x]) adtag(x + x, tag[x]), adtag(x + x + 1, tag[x]), tag[x] = 0;
}
void build(int x, int l, int r) {
  L[x] = l, R[x] = r, tag[x] = 0, f[x] = -l;
  if (l == r) {
    f[x] = -l;
    return;
  }
  int md = (l + r) >> 1;
  build(x + x, l, md), build(x + x + 1, md + 1, r);
}
void modify(int x, int l, int r, int dd) {
  if (l == L[x] && r == R[x]) {
    adtag(x, dd);
    return;
  }
  pdw(x);
  int md = (L[x] + R[x]) >> 1;
  if (r <= md)
    modify(x + x, l, r, dd);
  else if (l > md)
    modify(x + x + 1, l, r, dd);
  else
    modify(x + x, l, md, dd), modify(x + x + 1, md + 1, r, dd);
  pup(x);
}
int query(int x, int l, int r, int dd) {
  if (L[x] == R[x]) return f[x] <= dd ? l : -1;
  pdw(x);
  int md = (L[x] + R[x]) >> 1;
  if (l == L[x] && r == R[x]) {
    if (f[x + x + 1] <= dd)
      return query(x + x + 1, md + 1, r, dd);
    else if (f[x + x] <= dd)
      return query(x + x, l, md, dd);
    else
      return -1;
  }
  if (r <= md)
    return query(x + x, l, r, dd);
  else if (l > md)
    return query(x + x + 1, l, r, dd);
  else
    return max(query(x + x, l, md, dd), query(x + x + 1, md + 1, r, dd));
}
int broad[N];
void work1(int *a, int n, int pos) {
  set<int> S;
  S.clear();
  for (int i = 1, j = 0; i <= n; i++) {
    for (; j < n && S.find(a[j + 1]) == S.end();) S.insert(a[++j]);
    broad[i] = j, S.erase(a[i]);
  }
  build(1, 1, n);
  stack<int> mis, mas;
  for (int i = n, prev, succ; i; i--) {
    for (; !mis.empty() && a[mis.top()] >= a[i];) {
      prev = mis.top(), mis.pop(), succ = mis.empty() ? n + 1 : mis.top();
      modify(1, prev, succ - 1, a[prev] - a[i]);
    }
    mis.push(i);
    for (; !mas.empty() && a[mas.top()] <= a[i];) {
      prev = mas.top(), mas.pop(), succ = mas.empty() ? n + 1 : mas.top();
      modify(1, prev, succ - 1, a[i] - a[prev]);
    }
    mas.push(i);
    upd(i + pos, query(1, i, broad[i], k - i) + pos);
  }
}
void workd() {
  for (int i = 1, j; i <= n; i = j + 1) {
    for (j = i; j < n && (a[j + 1] % d + d) % d == (a[i] % d + d) % d; ++j)
      ;
    int o = a[i];
    for (int p = i; p <= j; p++) a[p] = (a[p] - o) / d;
    work1(a + i - 1, j - i + 1, i - 1);
  }
  printf("%d %d\n", al, ar);
}
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  d ? workd() : work0();
  return 0;
}
