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 long long N = (long long)2e5 + 10, oo = (long long)1e9 + 10;
long long n, k, d, a[N], tmx[N], tmn[N], lz[N << 2], b[N], seg[N << 2];
pair<long long, long long> res;
map<long long, long long> nxt;
void update(long long id, long long val) {
  lz[id] += val;
  seg[id] += val;
}
void shift(long long id) {
  update(id << 1, lz[id]);
  update(id << 1 | 1, lz[id]);
  lz[id] = 0;
}
void add(long long x, long long y, long long val, long long id = 1,
         long long l = 0, long long r = n) {
  if (r <= x || l >= y) return;
  if (l >= x && r <= y) {
    update(id, val);
    return;
  }
  shift(id);
  long long mid = r + l >> 1, lc = id << 1, rc = lc | 1;
  add(x, y, val, lc, l, mid);
  add(x, y, val, rc, mid, r);
  seg[id] = max(seg[lc], seg[rc]);
}
long long bs(long long x, long long y, long long val, long long id = 1,
             long long l = 0, long long r = n) {
  if (r <= x || l >= y || seg[id] < val) return -1;
  if (r - l < 2) return l;
  shift(id);
  long long mid = r + l >> 1, lc = id << 1, rc = lc | 1;
  long long ret = bs(x, y, val, rc, mid, r);
  if (!~ret) ret = bs(x, y, val, lc, l, mid);
  return ret;
}
void solve(long long bl, long long br) {
  vector<long long> mn, mx;
  for (long long j = bl; j <= br; ++j) add(j, j + 1, j + k), nxt[a[j]] = oo;
  long long can = br + 1;
  for (long long j = br; j >= bl; --j) {
    while (!mx.empty() && a[mx.back()] <= a[j]) {
      long long cur = mx.back();
      add(cur, tmx[cur] + 1, a[cur]);
      mx.pop_back();
    }
    tmx[j] = (mx.empty() ? br : mx.back() - 1);
    add(j, tmx[j] + 1, -a[j]);
    mx.push_back(j);
    while (!mn.empty() && a[mn.back()] >= a[j]) {
      long long cur = mn.back();
      add(cur, tmn[cur] + 1, -a[cur]);
      mn.pop_back();
    }
    tmn[j] = (mn.empty() ? br : mn.back() - 1);
    add(j, tmn[j] + 1, a[j]);
    mn.push_back(j);
    can = min(can, nxt[a[j]]);
    nxt[a[j]] = j;
    res = max(res, {bs(j, can, j) - j + 1, -j});
  }
}
int32_t main() {
  scanf("%lld%lld%lld", &n, &k, &d);
  for (long long j = 0; j < n; ++j) {
    scanf("%lld", &a[j]);
    a[j] += oo;
    b[j] = a[j];
    if (d) a[j] /= d;
  }
  if (!d) {
    for (long long j = 0; j < n;) {
      long long ptr = j;
      while (ptr < n && b[ptr] == b[j]) ++ptr;
      res = max(res, {ptr - j, -j});
      j = ptr;
    }
  } else {
    for (long long j = 0; j < n;) {
      long long ptr = j;
      while (ptr < n && b[ptr] % d == b[j] % d) ++ptr;
      solve(j, ptr - 1);
      j = ptr;
    }
  }
  long long l = -res.second;
  ++l;
  cout << l << ' ' << l + res.first - 1 << endl;
}
