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;
inline char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline void read(int &x) {
  char c = nc(), b = 1;
  for (; !(c >= '0' && c <= '9'); c = nc())
    if (c == '-') b = -1;
  for (x = 0; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = nc())
    ;
  x *= b;
}
const int N = 200005;
int n, K, d;
int a[N];
namespace Work {
int ans1 = 1, ans2 = 1;
inline void Solve() {
  int ans = 0;
  for (int i = 1, j; i <= n; i = j + 1) {
    j = i;
    while (j + 1 <= n && a[i] == a[j + 1]) j++;
    if (j - i > ans2 - ans1 || (j - i == ans2 - ans1 && i < ans1))
      ans1 = i, ans2 = j;
  }
  printf("%d %d\n", ans1, ans2);
}
}  // namespace Work
int T[N << 2], F[N << 2];
inline void mark(int x, int a) {
  T[x] += a;
  F[x] += a;
}
inline void push(int x) {
  if (F[x]) mark(x << 1, F[x]), mark(x << 1 | 1, F[x]), F[x] = 0;
}
inline void Build(int x, int l, int r) {
  if (l == r) return void(T[x] = -l);
  int mid = (l + r) >> 1;
  Build(x << 1, l, mid);
  Build(x << 1 | 1, mid + 1, r);
  T[x] = min(T[x << 1], T[x << 1 | 1]);
}
inline void Add(int x, int l, int r, int ql, int qr, int a) {
  if (ql <= l && r <= qr) {
    mark(x, a);
    return;
  }
  push(x);
  int mid = (l + r) >> 1;
  if (ql <= mid) Add(x << 1, l, mid, ql, qr, a);
  if (qr > mid) Add(x << 1 | 1, mid + 1, r, ql, qr, a);
  T[x] = min(T[x << 1], T[x << 1 | 1]);
}
int Ret = 0;
inline void query(int x, int l, int r, int K) {
  if (l == r) return void(Ret = l);
  push(x);
  int mid = (l + r) >> 1;
  if (T[x << 1 | 1] <= K)
    query(x << 1 | 1, mid + 1, r, K);
  else
    query(x << 1, l, mid, K);
}
inline void Query(int x, int l, int r, int ql, int qr, int lim) {
  if (Ret) return;
  if (ql <= l && r <= qr) {
    if (T[x] <= lim) query(x, l, r, lim);
    return;
  }
  push(x);
  int mid = (l + r) >> 1;
  if (qr > mid) Query(x << 1 | 1, mid + 1, r, ql, qr, lim);
  if (ql <= mid) Query(x << 1, l, mid, ql, qr, lim);
}
map<int, int> nxt;
int last[N];
int sta1[N], pnt1;
int sta2[N], pnt2;
int ans1 = 1, ans2 = 1;
inline void Solve(int l, int r) {
  if (l == r) return;
  for (int i = l; i <= r; i++) a[i] = (a[i] + 1e9) / d + 1;
  int R = r + 1;
  pnt1 = pnt2 = 0;
  sta1[0] = sta2[0] = r + 1;
  for (int i = r; i >= l; i--) {
    if (nxt.count(a[i])) R = min(R, nxt[a[i]]);
    while (pnt1 && a[i] > a[sta1[pnt1]]) {
      Add(1, 1, n, sta1[pnt1], sta1[pnt1 - 1] - 1, -a[sta1[pnt1]]);
      pnt1--;
    }
    sta1[++pnt1] = i;
    Add(1, 1, n, sta1[pnt1], sta1[pnt1 - 1] - 1, a[i]);
    while (pnt2 && a[i] < a[sta2[pnt2]]) {
      Add(1, 1, n, sta2[pnt2], sta2[pnt2 - 1] - 1, a[sta2[pnt2]]);
      pnt2--;
    }
    sta2[++pnt2] = i;
    Add(1, 1, n, sta2[pnt2], sta2[pnt2 - 1] - 1, -a[i]);
    Ret = 0;
    Query(1, 1, n, i, R - 1, K - i);
    if (Ret - i > ans2 - ans1 || (Ret - i == ans2 - ans1 && i < ans1))
      ans1 = i, ans2 = Ret;
    nxt[a[i]] = i;
  }
  nxt.clear();
}
int main() {
  read(n);
  read(K);
  read(d);
  for (int i = 1; i <= n; i++) read(a[i]);
  if (d == 0) {
    Work::Solve();
    return 0;
  }
  Build(1, 1, n);
  for (int i = 1, j; i <= n; i = j + 1) {
    j = i;
    while (j + 1 <= n && (a[i] % d + d) % d == (a[j + 1] % d + d) % d) j++;
    Solve(i, j);
  }
  printf("%d %d\n", ans1, ans2);
  return 0;
}
