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 BAS = 1e9, N = 200010;
struct node {
  int mn, tag;
  inline void operator+=(int x) {
    mn += x;
    tag += x;
  }
  inline void reset() { mn = tag = 0; }
} t[N << 2];
void push_down(int x) {
  t[x << 1] += t[x].tag;
  t[x << 1 | 1] += t[x].tag;
  t[x].tag = 0;
}
void push_up(int x) {
  if (t[x].tag) push_down(x);
  t[x].mn = min(t[x << 1].mn, t[x << 1 | 1].mn);
}
void modify(int x, int l, int r, int v, int lp, int rp) {
  if (lp > r || rp < l) return;
  if (lp >= l && rp <= r) return (void)(t[x] += v);
  int mid = (lp + rp) >> 1;
  modify(x << 1, l, r, v, lp, mid);
  modify(x << 1 | 1, l, r, v, mid + 1, rp);
  push_up(x);
}
int find(int x, int p, int lp, int rp) {
  if (lp > p || rp < p) return 0;
  if (lp == rp) return t[x].mn;
  push_down(x);
  int mid = (lp + rp) >> 1;
  if (p <= mid)
    return find(x << 1, p, lp, mid);
  else
    return find(x << 1 | 1, p, mid + 1, rp);
}
int dfs(int x, int lim, int v, int lp, int rp) {
  if (t[x].mn > v) return -1;
  if (lp == rp) return lp;
  push_down(x);
  int mid = (lp + rp) >> 1;
  if (t[x << 1 | 1].mn <= v && mid + 1 <= lim) {
    int res = dfs(x << 1 | 1, lim, v, mid + 1, rp);
    if (~res) return res;
  }
  return dfs(x << 1, lim, v, lp, mid);
}
int n, k, d, arr[N], len;
map<int, int> mp;
int tmp[N];
struct data_sta {
  int l, r, val;
  inline bool operator<(const data_sta& x) const { return val < x.val; }
} st[2][N];
int top[2];
struct data_ans {
  int l, r;
  inline bool operator<(const data_ans& x) const {
    return r - l + 1 != x.r - x.l + 1 ? r - l + 1 > x.r - x.l + 1 : l < x.l;
  }
  inline void debug() const { printf("(%d,%d)\n", l, r); }
};
data_ans solve() {
  mp.clear();
  data_sta tp;
  data_ans res = (data_ans){len, -1};
  int cur = len, rec;
  top[0] = top[1] = 0;
  for (int i = len; i >= 1; --i) {
    if (mp[tmp[i]]) cur = min(cur, mp[tmp[i]] - 1);
    mp[tmp[i]] = i;
    tp = (data_sta){i, i, tmp[i]};
    while (top[0] && st[0][top[0]].val < tp.val) {
      modify(1, st[0][top[0]].l, st[0][top[0]].r, -st[0][top[0]].val, 1, len);
      tp.r = st[0][top[0]--].r;
    }
    st[0][++top[0]] = tp;
    modify(1, tp.l, tp.r, tp.val, 1, len);
    tp = (data_sta){i, i, tmp[i]};
    while (top[1] && st[1][top[1]].val > tp.val) {
      modify(1, st[1][top[1]].l, st[1][top[1]].r, st[1][top[1]].val, 1, len);
      tp.r = st[1][top[1]--].r;
    }
    st[1][++top[1]] = tp;
    modify(1, tp.l, tp.r, -tp.val, 1, len);
    modify(1, i, i, -i, 1, len);
    rec = dfs(1, cur, k - i, 1, len);
    if (~rec) res = min(res, (data_ans){i, rec});
  }
  for (int i = 1; i <= (len << 2); ++i) t[i].reset();
  return res;
}
int special_solve() {
  int res = 0, p = -1;
  for (int i = 1, j; i <= n; i += j) {
    j = 1;
    while (arr[i + j] == arr[i] && i + j <= n) ++j;
    if (res < j) res = j, p = i;
  }
  printf("%d %d\n", p, p + res - 1);
  return 0;
}
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]), arr[i] += BAS;
  if (d == 0) return special_solve();
  data_ans res = (data_ans){1, 1}, tp;
  for (int i = 1, j; i <= n; i += j) {
    j = 1;
    while (arr[i + j] % d == arr[i] % d && i + j <= n) ++j;
    len = j;
    for (int s = 0; s < j; ++s) tmp[s + 1] = arr[i + s] / d;
    tp = solve();
    tp.l += i - 1, tp.r += i - 1;
    res = min(res, tp);
  }
  printf("%d %d\n", res.l, res.r);
  return 0;
}
