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 = 200005, M = 100005, mod = 1e9 + 7;
inline void gmin(int &x, int y) {
  if (x > y) x = y;
}
inline void gmax(int &x, int y) {
  if (x < y) x = y;
}
inline void ch(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
pair<int, int> ans;
int n, K, d, a[N], use[N], p[N << 2], flag[N << 2];
int s1[N], s2[N], t1, t2;
map<int, int> last;
void add(int k, int b) {
  p[k] += b;
  flag[k] += b;
}
void pushdown(int k) {
  if (!flag[k]) return;
  add((k << 1), flag[k]);
  add((k << 1 | 1), flag[k]);
  flag[k] = 0;
}
void change(int l, int r, int x, int y, int k, int b) {
  if (x <= l && r <= y) {
    add(k, b);
    return;
  }
  pushdown(k);
  int mid = l + r >> 1;
  if (x <= mid) change(l, mid, x, y, (k << 1), b);
  if (y > mid) change(mid + 1, r, x, y, (k << 1 | 1), b);
  p[k] = min(p[(k << 1)], p[(k << 1 | 1)]);
}
int get(int l, int r, int x, int y, int k) {
  if (p[k] > K) return -1;
  if (l == r) return l;
  pushdown(k);
  int mid = l + r >> 1;
  if (x <= l && r <= y) {
    if (p[(k << 1)] <= K) return get(l, mid, x, y, (k << 1));
    return get(mid + 1, r, x, y, (k << 1 | 1));
  }
  if (x <= mid) {
    int t = get(l, mid, x, y, (k << 1));
    if (~t) return t;
  }
  if (y > mid) return get(mid + 1, r, x, y, (k << 1 | 1));
}
void solve(int l, int r) {
  int minx = 0x3f3f3f3f;
  for (int i = l; i <= r; i++) gmin(minx, a[i]);
  for (int i = l; i <= r; i++) a[i] = (a[i] - minx) / d;
  last.clear();
  use[l - 1] = l - 1;
  for (int i = l; i <= r; i++) {
    use[i] = max(last[a[i]], use[i - 1]);
    last[a[i]] = i;
  }
  t1 = t2 = 1;
  s1[1] = l - 1;
  s2[1] = l - 1;
  for (int i = l; i <= r; i++) {
    while (t1 > 1 && a[s1[t1]] > a[i])
      change(1, n, s1[t1 - 1] + 1, s1[t1], 1, a[s1[t1]] - a[i]), t1--;
    s1[++t1] = i;
    while (t2 > 1 && a[s2[t2]] < a[i])
      change(1, n, s2[t2 - 1] + 1, s2[t2], 1, a[i] - a[s2[t2]]), t2--;
    s2[++t2] = i;
    if (i > l) change(1, n, l, i - 1, 1, -1);
    int tmp = get(1, n, use[i] + 1, i, 1);
    ans = min(ans, make_pair(tmp - i, tmp));
  }
}
int main() {
  ans = make_pair(1, 0);
  scanf("%d%d%d", &n, &K, &d);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  if (!d) {
    int last = 1;
    for (int i = 2; i <= n; i++)
      if (a[i] != a[i - 1])
        ans = min(ans, make_pair(last - i + 1, last)), last = i;
    ans = min(ans, make_pair(last - n, last));
  } else {
    int last = 1;
    for (int i = 2; i <= n; i++)
      if ((a[i] - a[i - 1]) % d != 0) solve(last, i - 1), last = i;
    solve(last, n);
  }
  printf("%d %d\n", ans.second, ans.second - ans.first);
  return 0;
}
