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 = 800005, inf = 2100000000;
int n, k, d, last, st, ed, ans, a[N], f[N], g[N];
map<int, int> w;
struct Tree {
  int ma[N], mi[N], A[N], I[N], tl[N];
  unsigned int opt[N];
  void update(int t) {
    int L = t << 1, R = L + 1;
    ma[t] = min(ma[L], ma[R]);
    mi[t] = min(mi[L], mi[R]);
    opt[t] = min(opt[L], opt[R]);
  }
  void renew(int t, int v, int flag) {
    if (flag)
      ma[t] = A[t] = v;
    else
      mi[t] = tl[t] - v, I[t] = v;
    opt[t] = ma[t] + mi[t];
  }
  void down(int t) {
    if (A[t]) renew(t * 2, A[t], 1), renew(t * 2 + 1, A[t], 1), A[t] = 0;
    if (I[t]) renew(t * 2, I[t], 0), renew(t * 2 + 1, I[t], 0), I[t] = 0;
  }
  void build(int t, int l, int r) {
    opt[t] = ma[t] = inf, tl[t] = l;
    if (l == r) return;
    int mid = l + r >> 1;
    build(t * 2, l, mid), build(t * 2 + 1, mid + 1, r);
  }
  void modify(int t, int l, int r, int ll, int rr, int v, int flag) {
    if (l == ll && r == rr) {
      renew(t, v, flag);
      return;
    }
    int mid = l + r >> 1;
    down(t);
    if (rr <= mid)
      modify(t * 2, l, mid, ll, rr, v, flag);
    else if (ll > mid)
      modify(t * 2 + 1, mid + 1, r, ll, rr, v, flag);
    else
      modify(t * 2, l, mid, ll, mid, v, flag),
          modify(t * 2 + 1, mid + 1, r, mid + 1, rr, v, flag);
    update(t);
  }
  int get(int t, int l, int r, int k) {
    if (l == r) return opt[t] <= k ? l : inf;
    int mid = l + r >> 1;
    down(t);
    return opt[t * 2] <= k ? get(t * 2, l, mid, k)
                           : get(t * 2 + 1, mid + 1, r, k);
  }
} T;
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i), a[i] += 1000000000;
  last = 0, T.build(1, 1, n);
  if (!d) {
    for (int i = 1; i <= n; ++i) {
      if (i > 1 && a[i - 1] != a[i]) last = i - 1;
      if (i - last > ans) ans = i - last, st = last + 1, ed = i;
    }
  } else
    for (int i = 1; i <= n; ++i) {
      last = max(last, w[a[i]]), w[a[i]] = i;
      if (i > 1 && a[i - 1] % d != a[i] % d) last = i - 1;
      while (*f && a[f[*f]] < a[i]) --*f;
      while (*g && a[g[*g]] > a[i]) --*g;
      T.modify(1, 1, n, f[*f] + 1, i, a[i] / d, 1);
      T.modify(1, 1, n, g[*g] + 1, i, a[i] / d, 0);
      f[++*f] = g[++*g] = i;
      if (last) T.modify(1, 1, n, 1, last, inf, 1);
      int p = T.get(1, 1, n, k + i);
      if (i - p + 1 > ans) ans = i - p + 1, st = p, ed = i;
    }
  printf("%d %d\n", st, ed);
  return 0;
}
