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 = 2e5 + 5;
unordered_map<int, int> cnt;
int n, m, k, d, ans_l, ans_r, a[N];
struct segment_pos {
  int seg[N << 2], lz[N << 2];
  inline void add(int id, int x) { seg[id] += x, lz[id] += x; }
  inline void shift(int id) {
    add(id << 1 | 1, lz[id]);
    add(id << 1, lz[id]), lz[id] = 0;
  }
  inline void find(int id) { seg[id] = min(seg[id << 1], seg[id << 1 | 1]); }
  void build(int id = 1, int st = 0, int en = m) {
    if (en - st == 1) {
      seg[id] = st - k;
      return;
    }
    int mid = st + en >> 1;
    build(id << 1, st, mid), lz[id] = 0;
    build(id << 1 | 1, mid, en), find(id);
  }
  void update(int l, int r, int x, int id = 1, int st = 0, int en = m) {
    if (r <= st || en <= l) return;
    if (l <= st && en <= r) return add(id, x);
    int mid = st + en >> 1;
    shift(id), update(l, r, x, id << 1, st, mid);
    update(l, r, x, id << 1 | 1, mid, en), find(id);
  }
  int get(int l, int r, int id = 1, int st = 0, int en = m) {
    if (r <= st || en <= l || seg[id] >= r) return -1;
    if (en - st == 1) return st;
    shift(id);
    int mid = st + en >> 1;
    int p = get(l, r, id << 1, st, mid);
    return ~p ? p : get(l, r, id << 1 | 1, mid, en);
  }
} val;
struct segment_col {
  int seg[N << 2], mx[N << 2];
  inline void add(int id, int x) { seg[id] = mx[id] = x; }
  inline void shift(int id) {
    if (~seg[id]) {
      add(id << 1, seg[id]);
      add(id << 1 | 1, seg[id]);
    }
  }
  inline void find(int id) {
    mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
    seg[id] = seg[id << 1] ^ seg[id << 1 | 1] ? -1 : seg[id << 1];
  }
  void build(int id = 1, int st = 0, int en = m) {
    if (en - st == 1) return add(id, a[st]);
    int mid = st + en >> 1;
    build(id << 1 | 1, mid, en);
    build(id << 1, st, mid), find(id);
  }
  void update(int l, int r, int x, int id = 1, int st = 0, int en = m) {
    if (r <= st || en <= l || mx[id] <= x) return;
    if (l <= st && en <= r && ~seg[id]) {
      val.update(st, en, seg[id] - x);
      return add(id, x);
    }
    int mid = st + en >> 1;
    shift(id), update(l, r, x, id << 1, st, mid);
    update(l, r, x, id << 1 | 1, mid, en), find(id);
  }
} mn, mx;
inline void read_input() {
  cin >> n >> k >> d;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] += 1e9;
  }
}
inline void solve(int l, int r) {
  m = 0;
  for (int i = l; i < r; i++) a[m++] = a[i] / d;
  val.build(), mn.build();
  for (int i = 0; i < m; i++) a[i] *= -1;
  cnt.clear(), mx.build();
  for (int i = 0, p = 0; i < m; cnt[a[i++]]++) {
    mn.update(p, i, -a[i]), mx.update(p, i, a[i]);
    while (cnt[a[i]]) cnt[a[p++]]--;
    int x = val.get(p, i + 1);
    if (i - x > ans_r - ans_l) {
      ans_l = l + x;
      ans_r = l + i;
    }
  }
}
inline void write_output() {
  if (d) {
    int p = 0;
    for (int i = 0; i < n; i++)
      if (a[i] % d ^ a[p] % d) {
        solve(p, i);
        p = i;
      }
    solve(p, n);
  } else
    for (int i = 0, p = 0; i < n; i++) {
      while (a[i] ^ a[p]) p++;
      if (i - p > ans_r - ans_l) {
        ans_l = p;
        ans_r = i;
      }
    }
  cout << ++ans_l << ' ' << ++ans_r;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  read_input(), write_output();
  return 0;
}
