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 maxn = 2e5 + 10;
const long long inf = 2e12 + 10;
int n, k, d;
long long seg[4 * maxn], lazy[4 * maxn];
stack<long long> mx, mn;
inline pair<int, int> pairmax(pair<int, int> fi, pair<int, int> se) {
  if (fi.second - fi.first >= se.second - se.first) return fi;
  return se;
}
void propagate(int, int, int);
int get(int id, int L, int R, int l, int r, long long val) {
  if (seg[id] > val) return n + 1;
  if (L + 1 == R) return L;
  propagate(id, L, R);
  int mid = (L + R) >> 1, ret = n + 1;
  if (l < mid) ret = get(2 * id + 0, L, mid, l, min(mid, r), val);
  if (ret != n + 1) return ret;
  return get(2 * id + 1, mid, R, max(l, mid), r, val);
}
void add(int id, int L, int R, int l, int r, long long val = 1) {
  if (L == l and R == r) {
    seg[id] += val;
    lazy[id] += val;
    return;
  }
  propagate(id, L, R);
  int mid = (L + R) >> 1;
  if (l < mid) add(2 * id + 0, L, mid, l, min(mid, r), val);
  if (mid < r) add(2 * id + 1, mid, R, max(l, mid), r, val);
  seg[id] = min(seg[2 * id + 0], seg[2 * id + 1]);
}
void propagate(int id, int L, int R) {
  if (lazy[id] == 0) return;
  int mid = (L + R) >> 1;
  add(2 * id + 0, L, mid, L, mid, lazy[id]);
  add(2 * id + 1, mid, R, mid, R, lazy[id]);
  lazy[id] = 0;
}
long long a[maxn], b[maxn];
map<long long, int> last;
void relax_max(int idx) {
  add(1, 1, n + 1, idx, idx + 1, a[idx]);
  while (a[mx.top()] < a[idx]) {
    int k = a[mx.top()];
    int now = mx.top();
    mx.pop();
    int pre = mx.top();
    add(1, 1, n + 1, pre + 1, now + 1, a[idx] - k);
  }
  mx.push(idx);
}
void relax_min(int idx) {
  add(1, 1, n + 1, idx, idx + 1, -b[idx]);
  while (b[mn.top()] > b[idx]) {
    int k = b[mn.top()];
    int now = mn.top();
    mn.pop();
    int pre = mn.top();
    add(1, 1, n + 1, pre + 1, now + 1, -b[idx] + k);
  }
  mn.push(idx);
}
pair<int, int> solve(int L, int R) {
  for (int i = L; i <= R; i++) {
    if (a[i] < 0) {
      a[i] = -a[i];
      a[i] = (a[i] - 1) / d + 1;
      a[i] = -a[i];
    } else {
      a[i] /= d;
    }
    b[i] = a[i];
    add(1, 1, n + 1, i, i + 1, i);
  }
  while (!mx.empty()) mx.pop();
  while (!mn.empty()) mn.pop();
  a[L - 1] = inf;
  mx.push(L - 1);
  b[L - 1] = -inf;
  mn.push(L - 1);
  last.clear();
  int pre = L - 1;
  pair<int, int> ret{1, 1};
  for (int i = L; i <= R; i++) {
    relax_max(i);
    relax_min(i);
    if (last.count(a[i])) pre = max(pre, last[a[i]]);
    last[a[i]] = i;
    int l = get(1, 1, n + 1, pre + 1, i + 1, k + i);
    ret = pairmax(ret, {l, i});
  }
  return ret;
}
int d0[maxn];
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> k >> d;
  if (d == 0) {
    pair<int, int> answer = {1, 1};
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      d0[i] = 1;
      if (a[i] == a[i - 1]) d0[i] = d0[i - 1] + 1;
      answer = pairmax(answer, {i - d0[i] + 1, i});
    }
    cout << answer.first << " " << answer.second << endl;
    return 0;
  }
  int last = 1;
  pair<int, int> answer = {1, 1};
  for (int i = 1; i <= n + 1; i++) {
    if (i != n + 1) cin >> a[i];
    if (i == n + 1 or
        (i > 1 and ((a[i] % d) + d) % d != ((a[i - 1] % d) + d) % d)) {
      answer = pairmax(answer, solve(last, i - 1));
      last = i;
    }
  }
  cout << answer.first << " " << answer.second << endl;
}
