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, inf = 1e9;
int n, k, d, a[N], ansl, ansr = -1;
bool flag;
namespace SGT {
long long tag[N << 2], mn[N << 2];
inline void up(int rt) { mn[rt] = min(mn[(rt << 1)], mn[(rt << 1 | 1)]); }
inline void cov(int rt, long long tg) { mn[rt] += tg, tag[rt] += tg; }
inline void down(int rt) {
  long long& tg = tag[rt];
  cov((rt << 1), tg), cov((rt << 1 | 1), tg);
  tg = 0;
}
void build(int rt, int l, int r) {
  if (l == r) return mn[rt] = l, void();
  int mid = l + r >> 1;
  build((rt << 1), l, mid), build((rt << 1 | 1), mid + 1, r);
  return up(rt);
}
void update(int rt, int l, int r, int ql, int qr, long long v) {
  if (ql <= l && r <= qr) return cov(rt, v);
  if (tag[rt]) down(rt);
  int mid = l + r >> 1;
  if (ql <= mid) update((rt << 1), l, mid, ql, qr, v);
  if (mid < qr) update((rt << 1 | 1), mid + 1, r, ql, qr, v);
  return up(rt);
}
int query(int rt, int l, int r, int ql, int qr, int k) {
  if (mn[rt] > k) return -1;
  if (l == r) return mn[rt] <= k ? (flag = 1, l) : -1;
  if (tag[rt]) down(rt);
  int mid = l + r >> 1, ans;
  if (ql <= mid && !flag) ans = query((rt << 1), l, mid, ql, qr, k);
  if (qr > mid && !flag) ans = query((rt << 1 | 1), mid + 1, r, ql, qr, k);
  return ans;
}
}  // namespace SGT
using namespace SGT;
map<int, int> mp;
int pre[N];
int p[N], q[N], topp, topq;
int main() {
  scanf("%d%d%d", &n, &k, &d);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  if (!d) {
    for (int i = 1; i <= n; ++i) {
      int j = i;
      while (a[j] == a[j + 1]) ++j;
      if (ansr - ansl < j - i) ansl = i, ansr = j;
      i = j;
    }
    return printf("%d %d\n", ansl, ansr), 0;
  }
  for (int i = 1; i <= n; ++i) a[i] += inf;
  for (int i = 1; i <= n; ++i) {
    if (mp.count(a[i]))
      pre[i] = mp[a[i]];
    else
      pre[i] = 0;
    mp[a[i]] = i;
  }
  build(1, 1, n);
  for (int i = 1, L = 1; i <= n; ++i) {
    if (i != 1) L = (a[i] % d == a[i - 1] % d) ? max(L, pre[i] + 1) : i;
    while (topp && p[topp] >= L && a[i] >= a[p[topp]]) {
      update(1, 1, n, max(p[topp - 1] + 1, L), p[topp], -a[p[topp]] / d);
      --topp;
    }
    update(1, 1, n, max(p[topp] + 1, L), i, a[i] / d);
    p[++topp] = i;
    while (topq && q[topq] >= L && a[i] <= a[q[topq]]) {
      update(1, 1, n, max(q[topq - 1] + 1, L), q[topq], a[q[topq]] / d);
      --topq;
    }
    update(1, 1, n, max(q[topq] + 1, L), i, -a[i] / d);
    q[++topq] = i;
    flag = 0;
    int ans = query(1, 1, n, L, i, k + i);
    if (i - ans > ansr - ansl) ansl = ans, ansr = i;
  }
  printf("%d %d\n", ansl, ansr);
  return 0;
}
