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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long maxn = 2e5 + 10;
const long long mod = 1e9 + 7;
const long double PI = acos((long double)-1);
long long pw(long long a, long long b, long long md = mod) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res = (a * res) % md;
    }
    a = (a * a) % md;
    b >>= 1;
  }
  return (res);
}
pair<long long, long long> pos[maxn];
long long a[maxn];
long long n, k, d;
stack<long long> mn, mx;
struct segment {
  long long lazy[maxn * 4], seg[maxn * 4], cnt[maxn * 4];
  long long& ans = cnt[1];
  void build(long long v = 1, long long l = 1, long long r = maxn) {
    if (r - l == 1) {
      cnt[v] = 1;
      return;
    }
    long long mid = (l + r) / 2;
    build(2 * v, l, mid);
    build(2 * v + 1, mid, r);
    cnt[v] = cnt[2 * v] + cnt[2 * v + 1];
  }
  void shift(long long v, long long l, long long r) {
    if (lazy[v] == 0) return;
    seg[v] += lazy[v];
    if (r - l == 1) {
      lazy[v] = 0;
      return;
    }
    lazy[2 * v] += lazy[v];
    lazy[2 * v + 1] += lazy[v];
    lazy[v] = 0;
  }
  void update(long long L, long long R, long long val, long long v = 1,
              long long l = 1, long long r = maxn) {
    shift(v, l, r);
    if (l >= R or r <= L) return;
    if (l >= L and r <= R) {
      lazy[v] += val;
      shift(v, l, r);
      return;
    }
    long long mid = (l + r) / 2;
    update(L, R, val, 2 * v, l, mid);
    update(L, R, val, 2 * v + 1, mid, r);
    if (seg[2 * v] < seg[2 * v + 1]) {
      seg[v] = seg[2 * v];
      cnt[v] = cnt[2 * v];
    } else if (seg[2 * v] == seg[2 * v + 1]) {
      seg[v] = seg[2 * v];
      cnt[v] = cnt[2 * v] + cnt[2 * v + 1];
    } else {
      seg[v] = seg[2 * v + 1];
      cnt[v] = cnt[2 * v + 1];
    }
  }
  long long solve(long long pos, long long v = 1, long long l = 1,
                  long long r = maxn) {
    shift(v, l, r);
    if (r - l == 1) {
      if (seg[v] <= 0)
        return (l);
      else
        return (maxn);
    }
    long long mid = (l + r) / 2;
    shift(2 * v, l, mid);
    shift(2 * v + 1, mid, r);
    if (seg[2 * v] <= 0) return (solve(pos, 2 * v, l, mid));
    return (solve(pos, 2 * v + 1, mid, r));
  }
} seg;
long long rmn[maxn];
map<long long, long long> lst;
long long A[maxn];
void solve() {
  long long L = 1, ans = 1, cur;
  cin >> cur;
  long long cnt = 1;
  for (long long i = 2; i <= n; i++) {
    cin >> a[i];
    if (a[i] == cur)
      cnt++;
    else
      cur = a[i], cnt = 1;
    if (cnt > ans) L = i, ans = cnt;
  }
  cout << L - ans + 1 << ' ' << L;
  exit(0);
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k >> d;
  if (d == 0) solve();
  for (long long i = 1; i <= n; i++)
    cin >> a[i], a[i] += 1e9, A[i] = a[i], rmn[i] = a[i] % d, a[i] -= rmn[i],
                              a[i] /= d;
  seg.build();
  long long ans = 1;
  long long L = 1;
  seg.update(1, maxn, -k);
  for (long long i = 1; i <= n; i++) {
    if (rmn[i] != rmn[i - 1]) {
      seg.update(1, i, 1e10);
      while (mx.size()) mx.pop();
      while (mn.size()) mn.pop();
    }
    seg.update(1, lst[A[i]] + 1, 1e10);
    lst[A[i]] = i;
    seg.update(1, i, -1);
    long long cur = i;
    while (!mx.empty() and a[i] > a[mx.top()]) {
      long long bz = mx.top();
      mx.pop();
      if (mx.size()) {
        seg.update(mx.top() + 1, cur, a[i] - a[bz]);
        cur = mx.top() + 1;
      } else {
        seg.update(1, cur, a[i] - a[bz]);
      }
    }
    cur = i;
    while (!mn.empty() and a[i] < a[mn.top()]) {
      long long bz = mn.top();
      mn.pop();
      if (mn.size()) {
        seg.update(mn.top() + 1, cur, a[bz] - a[i]);
        cur = mn.top() + 1;
      } else {
        seg.update(1, cur, a[bz] - a[i]);
      }
    }
    long long res = i - seg.solve(i) + 1;
    if (res > ans) L = i, ans = res;
    mn.push(i);
    mx.push(i);
  }
  cout << L - ans + 1 << ' ' << L;
  return (0);
}
