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;
const int INF = 1e9;
struct node {
  int len, l, r;
  inline node(int _l, int _r) {
    l = _l;
    r = _r;
    len = r - l + 1;
  }
  inline node() {}
};
int n, K, D, a[N], A[N];
node ans;
inline long long getint() {
  long long x = 0;
  char c = getchar();
  bool flag = false;
  while ((c != '-') && ((c < '0') || (c > '9'))) c = getchar();
  if (c == '-') flag = true, c = getchar();
  while ((c >= '0') && (c <= '9'))
    x = x * 10 + (long long)(c - '0'), c = getchar();
  if (flag)
    return -x;
  else
    return x;
}
void init() {
  n = getint();
  K = getint();
  D = getint();
  int mint = INF;
  for (int i = 1; i <= n; i++) a[i] = getint(), mint = min(mint, a[i]);
  for (int i = 1; i <= n; i++) a[i] -= mint;
}
inline void updata(node nowans) {
  if (nowans.len < ans.len) return;
  if (nowans.len > ans.len) {
    ans = nowans;
    return;
  }
  if (nowans.l < ans.l) ans = nowans;
}
namespace Fuck {
void solve() {
  for (int i = 1, j; i <= n; updata((node){i, j - 1}), i = j)
    for (j = i; (j <= n) && (a[i] == a[j]); j++)
      ;
  printf("%d %d\n", ans.l, ans.r);
}
}  // namespace Fuck
namespace Segment {
const long long INF = 1e18;
struct node {
  long long mint, lazy;
} tree[N * 4];
int nowans;
void build(int p, int l, int r) {
  tree[p].mint = tree[p].lazy = 0;
  if (l == r) return;
  int mid = (l + r) / 2;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
}
inline void tag(int p, long long x) {
  tree[p].lazy += x;
  tree[p].mint += x;
}
inline void lazy_tag(int p) {
  if (tree[p].lazy == 0) return;
  tag(p * 2, tree[p].lazy);
  tag(p * 2 + 1, tree[p].lazy);
  tree[p].lazy = 0;
}
void modify(int p, int l, int r, int ll, int rr, int x) {
  if (l != r) lazy_tag(p);
  int mid = (l + r) / 2;
  if ((l == ll) && (r == rr)) {
    tag(p, x);
    return;
  }
  if (rr <= mid)
    modify(p * 2, l, mid, ll, rr, x);
  else if (ll > mid)
    modify(p * 2 + 1, mid + 1, r, ll, rr, x);
  else
    modify(p * 2, l, mid, ll, mid, x),
        modify(p * 2 + 1, mid + 1, r, mid + 1, rr, x);
  tree[p].mint = min(tree[p * 2].mint, tree[p * 2 + 1].mint);
}
void ask(int p, int l, int r, int limit) {
  if (l >= nowans) return;
  if (l != r) lazy_tag(p);
  if (tree[p].mint > limit) return;
  if (l == r) {
    nowans = l;
    return;
  }
  int mid = (l + r) / 2;
  if (tree[p * 2].mint <= limit)
    ask(p * 2, l, mid, limit);
  else
    ask(p * 2 + 1, mid + 1, r, limit);
}
void ask(int p, int l, int r, int ll, int rr, int limit) {
  if (ll >= nowans) return;
  if (l != r) lazy_tag(p);
  int mid = (l + r) / 2;
  if ((l == ll) && (r == rr)) {
    ask(p, l, r, limit);
    return;
  }
  if (rr <= mid)
    ask(p * 2, l, mid, ll, rr, limit);
  else if (ll > mid)
    ask(p * 2 + 1, mid + 1, r, ll, rr, limit);
  else
    ask(p * 2, l, mid, ll, mid, limit),
        ask(p * 2 + 1, mid + 1, r, mid + 1, rr, limit);
}
}  // namespace Segment
namespace Orz {
int n, a[N], far, top1, stack1[N], top2, stack2[N];
map<int, int> mp;
void init() {
  for (int i = 1; i <= n; i++) a[i] /= D;
  Segment::build(1, 1, n);
  top1 = top2 = 0;
  mp.clear();
}
void solve(int fst) {
  far = 0;
  for (int i = 1; i <= n; i++) {
    for (; (top1) && (a[i] >= a[stack1[top1]]); top1--)
      Segment::modify(1, 1, n, stack1[top1 - 1] + 1, stack1[top1],
                      a[i] - a[stack1[top1]]);
    for (; (top2) && (a[i] <= a[stack2[top2]]); top2--)
      Segment::modify(1, 1, n, stack2[top2 - 1] + 1, stack2[top2],
                      a[stack2[top2]] - a[i]);
    stack1[++top1] = i;
    stack2[++top2] = i;
    far = max(far, mp[a[i]] + 1);
    mp[a[i]] = i;
    Segment::modify(1, 1, n, i, i, i);
    Segment::nowans = i;
    Segment::ask(1, 1, n, far, i, K + i);
    updata((node){Segment::nowans + fst, i + fst});
  }
}
}  // namespace Orz
void solve() {
  if (D == 0) {
    Fuck::solve();
    return;
  }
  for (int i = 1; i <= n; i++) A[i] = a[i] % D;
  for (int i = 1, j; i <= n; i = j) {
    for (j = i; (j <= n) && (A[i] == A[j]); j++)
      ;
    Orz::n = 0;
    for (int k = i; k < j; k++) Orz::a[++Orz::n] = a[k];
    Orz::init();
    Orz::solve(i - 1);
  }
  printf("%d %d\n", ans.l, ans.r);
}
int main() {
  init();
  solve();
  return 0;
}
