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;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
int a[200010], b[200010];
inline void Solve(int n, int k) {
  int len = 1, now = -2147483647, pos = 1, l = 0, r = -1;
  for (int i = 1; i <= n; i++) {
    int x = read();
    if (x != now) {
      if (r - l + 1 < i - pos) l = pos, r = i - 1;
      now = x, pos = i;
    }
  }
  if (r - l + 1 < n - pos) l = pos, r = n;
  printf("%d %d\n", l, r);
}
struct SegmentTree {
  long long val[200010 << 2], tag[200010 << 2];
  inline void upd(int k) { val[k] = min(val[(k << 1)], val[(k << 1 | 1)]); }
  inline void down(int k) {
    if (!tag[k]) return;
    val[(k << 1)] += tag[k], val[(k << 1 | 1)] += tag[k];
    tag[(k << 1)] += tag[k], tag[(k << 1 | 1)] += tag[k];
    tag[k] = 0;
  }
  inline void build(int k, int l, int r) {
    val[k] = tag[k] = 0;
    if (l == r) return;
    build((k << 1), l, ((l + r) >> 1)),
        build((k << 1 | 1), ((l + r) >> 1) + 1, r);
  }
  inline void Mod(int k, int l, int r, int x, int y, int dat) {
    if (y < l || r < x) return;
    if (x <= l && r <= y) return val[k] += dat, tag[k] += dat, void();
    down(k), Mod((k << 1), l, ((l + r) >> 1), x, y, dat),
        Mod((k << 1 | 1), ((l + r) >> 1) + 1, r, x, y, dat), upd(k);
  }
  inline int Find(int k, int l, int r, int p, int x) {
    if (l == r) return val[k] <= x ? l : -1;
    down(k);
    if (val[(k << 1)] <= x) return Find((k << 1), l, ((l + r) >> 1), p, x);
    if (((l + r) >> 1) < p)
      return Find((k << 1 | 1), ((l + r) >> 1) + 1, r, p, x);
    return -1;
  }
} T;
int resl = 0, resr = -1;
map<int, int> Map;
stack<int> U, D;
inline void solve(int l, int r, int d, int k) {
  for (int i = l; i <= r; i++) a[i - l + 1] = b[i] / d;
  int n = r - l + 1, lst = 0;
  T.build(1, 1, n), Map.clear();
  for (int i = 1; i <= n; i++) {
    if (Map.find(a[i]) != Map.end()) {
      T.Mod(1, 1, n, lst + 1, Map[a[i]], 2147483647 / 4), lst = Map[a[i]];
    }
    Map[a[i]] = i;
    T.Mod(1, 1, n, 1, n, -1), T.Mod(1, 1, n, i, i, i);
    while (U.top() && a[U.top()] > a[i]) {
      int Tmp = U.top();
      U.pop();
      T.Mod(1, 1, n, U.top() + 1, Tmp, a[Tmp]);
    }
    T.Mod(1, 1, n, U.top() + 1, i, -a[i]), U.push(i);
    while (D.top() && a[D.top()] < a[i]) {
      int Tmp = D.top();
      D.pop();
      T.Mod(1, 1, n, D.top() + 1, Tmp, -a[Tmp]);
    }
    T.Mod(1, 1, n, D.top() + 1, i, a[i]), D.push(i);
    int L = T.Find(1, 1, n, i, k);
    if (L != -1 && resr - resl + 1 < i - L + 1)
      resl = L + l - 1, resr = i + l - 1;
  }
  while (U.top()) U.pop();
  while (D.top()) D.pop();
}
int main() {
  int n = read(), k = read(), d = read(), Min = 2147483647;
  if (!d) return Solve(n, k), 0;
  U.push(0), D.push(0);
  for (int i = 1; i <= n; i++) Min = min(Min, b[i] = read());
  for (int i = 1; i <= n; i++) b[i] -= Min - 1;
  int pos = 1;
  for (int i = 2; i <= n + 1; i++)
    if (b[pos] % d != b[i] % d || i == n + 1) solve(pos, i - 1, d, k), pos = i;
  printf("%d %d\n", resl, resr);
  return 0;
}
