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>
const int kMaxn = 2e5 + 10;
const int kInf = 1e9 + 2077;
int maxlen = 1, ansl = 1, ansr = 1;
int n, k, d, data[kMaxn], a[kMaxn], pre[kMaxn];
int minnum[kMaxn << 2], tag[kMaxn << 2];
int top_up, st_up[kMaxn], top_down, st_down[kMaxn];
std ::map<int, int> pre_equal;
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
void Pushup(int now_) {
  minnum[now_] = std ::min(minnum[(now_ << 1)], minnum[(now_ << 1 | 1)]);
}
void Pushdown(int now_) {
  if (!tag[now_]) return;
  minnum[(now_ << 1)] += tag[now_], minnum[(now_ << 1 | 1)] += tag[now_];
  tag[(now_ << 1)] += tag[now_], tag[(now_ << 1 | 1)] += tag[now_];
  tag[now_] = 0;
}
void Modify(int now_, int L_, int R_, int l_, int r_, int val_) {
  if (l_ <= L_ && R_ <= r_) {
    minnum[now_] += val_;
    tag[now_] += val_;
    return;
  }
  Pushdown(now_);
  int mid = (L_ + R_) >> 1;
  if (l_ <= mid) Modify((now_ << 1), L_, mid, l_, r_, val_);
  if (r_ > mid) Modify((now_ << 1 | 1), mid + 1, R_, l_, r_, val_);
  Pushup(now_);
}
int Query(int now_, int L_, int R_, int ql_, int qr_, int k_) {
  if (minnum[now_] > k_ || R_ < ql_ || L_ > qr_) return n + 1;
  if (L_ == R_) return L_;
  Pushdown(now_);
  int mid = (L_ + R_) >> 1, ret;
  ret = Query((now_ << 1), L_, mid, ql_, qr_, k_);
  if (ret == n + 1) ret = Query((now_ << 1 | 1), mid + 1, R_, ql_, qr_, k_);
  return ret;
}
void StackInsert(int pos_, int minl_) {
  int l, r;
  for (; top_down && a[st_down[top_down]] <= a[pos_]; top_down--) {
    r = st_down[top_down], l = st_down[top_down - 1] + 1;
    if (top_down == 1) l = minl_;
    Modify(1, 1, n, l, r, -a[st_down[top_down]]);
  }
  st_down[++top_down] = pos_;
  r = pos_, l = top_down == 1 ? minl_ : st_down[top_down - 1] + 1;
  Modify(1, 1, n, l, r, a[pos_]);
  for (; top_up && a[st_up[top_up]] >= a[pos_]; top_up--) {
    r = st_up[top_up], l = st_up[top_up - 1] + 1;
    if (top_up == 1) l = minl_;
    Modify(1, 1, n, l, r, a[st_up[top_up]]);
  }
  st_up[++top_up] = pos_;
  r = pos_, l = top_up == 1 ? minl_ : st_up[top_up - 1] + 1;
  Modify(1, 1, n, l, r, -a[pos_]);
}
void Solve(int l_, int r_) {
  top_down = top_up = 0;
  st_down[0] = n + 1, st_up[0] = 0;
  for (int r = l_, l = l_; r <= r_; ++r) {
    Modify(1, 1, n, r, r, r);
    StackInsert(r, l_);
    l = std ::max(l, pre[r] + 1);
    int retl = Query(1, 1, n, l, r, k + r);
    if (retl <= n && r - retl + 1 > maxlen) {
      maxlen = r - retl + 1;
      ansr = r, ansl = retl;
    }
  }
}
int main() {
  n = read(), k = read(), d = read();
  a[0] = -kInf, a[n + 1] = kInf;
  int secl = 1;
  if (d == 0) {
    for (int i = 1; i <= n; ++i) {
      a[i] = read();
      if (i > 1 && a[i] != a[i - 1]) {
        if (i - 1 - secl + 1 > ansr - ansl + 1) {
          ansl = secl, ansr = i - 1;
        }
        secl = i;
      }
    }
    printf("%d %d\n", ansl, ansr);
    return 0;
  }
  for (int i = 1; i <= n; ++i) {
    data[i] = a[i] = read();
    pre[i] = pre_equal[data[i]], pre_equal[data[i]] = i;
    a[i] /= d;
    if (i > 1 && (data[i] % d + d) % d != (data[i - 1] % d + d) % d) {
      if (secl) Solve(secl, i - 1);
      secl = i;
    }
  }
  Solve(secl, n);
  printf("%d %d\n", ansl, ansr);
  return 0;
}
