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 A = 2e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9;
const int inf = 0x3f3f3f3f;
inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
bool flag;
map<int, int> last;
int sl[A], topl, sr[A], topr;
struct tr {
  int l, r, la, po;
} t[A << 2];
int n, k, d, ansl = 1, ansr = 1, a[A], ans;
inline void pushup(int rt) { t[rt].po = min(t[rt << 1].po, t[rt << 1 | 1].po); }
inline void calc(int rt, int x) { t[rt].la += x, t[rt].po += x; }
inline void pushdown(int rt) {
  if (t[rt].la && t[rt].l < t[rt].r) {
    calc(rt << 1, t[rt].la), calc(rt << 1 | 1, t[rt].la);
    t[rt].la = 0;
  }
}
void build(int rt, int l, int r) {
  t[rt].l = l, t[rt].r = r, t[rt].la = 0, t[rt].po = 0;
  if (l == r) {
    t[rt].po = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
  pushup(rt);
}
void insert(int rt, int l, int r, int k) {
  if (l <= t[rt].l && t[rt].r <= r) return calc(rt, k);
  pushdown(rt);
  int mid = (t[rt].l + t[rt].r) >> 1;
  if (l <= mid) insert(rt << 1, l, r, k);
  if (r > mid) insert(rt << 1 | 1, l, r, k);
  pushup(rt);
}
int work(int rt, int k) {
  if (t[rt].l == t[rt].r) return t[rt].l;
  pushdown(rt);
  if (t[rt << 1].po <= k)
    return work(rt << 1, k);
  else
    return work(rt << 1 | 1, k);
}
void query(int rt, int l, int r, int k) {
  if (l <= t[rt].l && t[rt].r <= r) {
    if (t[rt].po <= k) flag = 1, ans = work(rt, k);
    return;
  }
  pushdown(rt);
  int mid = (t[rt].l + t[rt].r) >> 1;
  if (l <= mid && !flag) query(rt << 1, l, r, k);
  if (r > mid && !flag) query(rt << 1 | 1, l, r, k);
}
void del(int rt, int x) {
  if (x < t[rt].l || x > t[rt].r) return;
  pushdown(rt);
  if (t[rt].l == x && t[rt].r == x) {
    t[rt].po = 0;
    return;
  }
  del(rt << 1, x), del(rt << 1 | 1, x);
  pushup(rt);
}
int main() {
  n = read(), k = read(), d = read();
  for (int i = 1; i <= n; i++) a[i] = read() + inf;
  if (d == 0) {
    for (int i = 1; i <= n; i++) {
      int l = i;
      while (a[i] == a[i + 1] && i < n) i++;
      if (ansr - ansl < i - l) ansl = l, ansr = i;
    }
    cout << ansl << ' ' << ansr << '\n';
    return 0;
  }
  build(1, 1, n);
  for (int i = 1, L = 1; i <= n; i++) {
    int tmp = L;
    if (a[i] % d == a[i - 1] % d)
      L = max(L, last[a[i]] + 1);
    else
      L = i;
    last[a[i]] = i;
    while (tmp < L) del(1, tmp++);
    while (topl && sl[topl] >= L && a[sl[topl]] >= a[i]) {
      insert(1, max(L, sl[topl - 1] + 1), sl[topl], a[sl[topl]] / d);
      topl--;
    }
    insert(1, max(L, sl[topl] + 1), i, -a[i] / d);
    sl[++topl] = i;
    while (topr && sr[topr] >= L && a[sr[topr]] <= a[i]) {
      insert(1, max(L, sr[topr - 1] + 1), sr[topr], -a[sr[topr]] / d);
      topr--;
    }
    insert(1, max(L, sr[topr] + 1), i, a[i] / d);
    sr[++topr] = i;
    flag = 0, ans = 0;
    query(1, L, i, k + i);
    if (ansr - ansl < i - ans) ansl = ans, ansr = i;
  }
  cout << ansl << " " << ansr << '\n';
  return 0;
}
