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 = 202020;
const int M = 1000000000;
const int INF = 1 << 30;
inline char get(void) {
  static char buf[100000], *S = buf, *T = buf;
  if (S == T) {
    T = (S = buf) + fread(buf, 1, 100000, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
template <typename T>
inline void read(T &x) {
  static char c;
  x = 0;
  int sgn = 0;
  for (c = get(); c < '0' || c > '9'; c = get())
    if (c == '-') sgn = 1;
  for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
  if (sgn) x = -x;
}
int sta1[N], sta2[N];
int ad[N << 2], mn[N << 2];
int n, k, d, top1, top2;
int cur, pos, ansl, ansr, lst;
int a[N], b[N];
map<int, int> usd;
inline void PushDown(int o) {
  if (ad[o]) {
    ad[o << 1] += ad[o];
    ad[o << 1 | 1] += ad[o];
    mn[o << 1] += ad[o];
    mn[o << 1 | 1] += ad[o];
    ad[o] = 0;
  }
}
inline void Add(int o, int l, int r, int L, int R, int x) {
  if (l >= L && r <= R) {
    ad[o] += x;
    mn[o] += x;
    return;
  }
  int mid = (l + r) >> 1;
  PushDown(o);
  if (L <= mid) Add(o << 1, l, mid, L, R, x);
  if (R > mid) Add(o << 1 | 1, mid + 1, r, L, R, x);
  mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
}
inline void Find(int o, int l, int r, int L, int R, int x) {
  if (l >= L && r <= R) {
    if (mn[o] > x) return;
    if (l == r) return (void)(pos = l);
    int mid = (l + r) >> 1;
    PushDown(o);
    if (mn[o << 1 | 1] > x) return Find(o << 1, l, mid, L, R, x);
    return Find(o << 1 | 1, mid + 1, r, L, R, x);
  }
  int mid = (l + r) >> 1;
  PushDown(o);
  if (L <= mid) Find(o << 1, l, mid, L, R, x);
  if (R > mid) Find(o << 1 | 1, mid + 1, r, L, R, x);
}
inline void Build(int o, int l, int r) {
  ad[o] = 0;
  mn[o] = -r;
  if (l == r) return;
  int mid = (l + r) >> 1;
  Build(o << 1, l, mid);
  Build(o << 1 | 1, mid + 1, r);
  mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
}
inline void Solve(int L, int R) {
  if (L == R) return;
  sta1[top1 = 0] = sta2[top2 = 0] = R + 1;
  usd.clear();
  int l, r = R + 1;
  for (l = R; l >= L; l--) {
    if (usd.count(a[l])) r = min(r, usd[a[l]]);
    while (top1 && a[l] > a[sta1[top1]]) {
      Add(1, 1, n, sta1[top1], sta1[top1 - 1] - 1, -a[sta1[top1]]);
      --top1;
    }
    sta1[++top1] = l;
    Add(1, 1, n, sta1[top1], sta1[top1 - 1] - 1, a[sta1[top1]]);
    while (top2 && a[l] < a[sta2[top2]]) {
      Add(1, 1, n, sta2[top2], sta2[top2 - 1] - 1, a[sta2[top2]]);
      --top2;
    }
    sta2[++top2] = l;
    Add(1, 1, n, sta2[top2], sta2[top2 - 1] - 1, -a[sta2[top2]]);
    pos = -1;
    Find(1, 1, n, l, r - 1, k - l);
    if (~pos) {
      if (pos - l > ansr - ansl) ansl = l, ansr = pos;
      if (pos - l == ansr - ansl && l < ansl) ansl = l, ansr = pos;
    }
    usd[a[l]] = l;
  }
}
int main(void) {
  read(n);
  read(k);
  read(d);
  if (d == 0) {
    lst = 1;
    a[0] = INF;
    read(a[1]);
    ansl = ansr = 1;
    for (int i = 2; i <= n; i++) {
      read(a[i]);
      if (a[i] != a[lst]) {
        if (i - 1 - lst > ansr - ansl) ansl = lst, ansr = i - 1;
        lst = i;
      }
    }
    printf("%d %d\n", ansl, ansr);
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    read(a[i]);
    b[i] = (a[i] += M) % d;
    a[i] /= d;
    ++a[i];
  }
  int j;
  Build(1, 1, n);
  ansl = ansr = 1;
  for (int i = 1; i <= n; i = j) {
    for (j = i + 1; j <= n; j++)
      if (b[j] != b[i]) break;
    Solve(i, j - 1);
  }
  printf("%d %d\n", ansl, ansr);
  return 0;
}
