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;
template <class T, class L>
bool smax(T &x, L y) {
  return x < y ? (x = y, 1) : 0;
}
template <class T, class L>
bool smin(T &x, L y) {
  return y < x ? (x = y, 1) : 0;
}
const int maxn = 2e5 + 17;
int n, d, k, a[maxn], l, r, ans, iman[maxn << 2], sina[maxn << 2];
bool mark[maxn << 2];
void up(int id, int v) {
  iman[id] += v, sina[id] += v;
  mark[id] = 1;
}
void sadra(int id) {
  up(id << 1, sina[id]), up(id << 1 | 1, sina[id]);
  sina[id] = 0;
}
void majid(int st, int en, int v, int l = 0, int r = n, int id = 1) {
  mark[id] = 1;
  if (st <= l && r <= en) {
    up(id, v);
    return;
  }
  if (en <= l || r <= st) return;
  sadra(id);
  int mid = l + r >> 1;
  majid(st, en, v, l, mid, id << 1), majid(st, en, v, mid, r, id << 1 | 1);
  iman[id] = min(iman[id << 1], iman[id << 1 | 1]);
}
int hamid(int en, int l = 0, int r = n, int id = 1) {
  mark[id] = 1;
  if (iman[id] > k || en <= l) return -1;
  if (l + 1 == r) return l;
  sadra(id);
  int mid = l + r >> 1;
  int ans = hamid(en, mid, r, id << 1 | 1);
  return ~ans ? ans : hamid(en, l, mid, id << 1);
}
void clear(int id = 1) {
  if (!mark[id]) return;
  mark[id] = iman[id] = sina[id] = 0;
  clear(id << 1), clear(id << 1 | 1);
}
map<int, int> lastseen;
void solve(int *a, int n, int base) {
  lastseen.clear();
  clear();
  stack<int> mn, mx;
  int ptr = n;
  for (int i = n - 1; ~i; i--) {
    majid(i + 1, ptr, -1);
    while (mn.size() && a[mn.top()] > a[i]) {
      int j = mn.top();
      mn.pop();
      majid(j, mn.size() ? mn.top() : n, a[j] - a[i]);
    }
    mn.push(i);
    while (mx.size() && a[mx.top()] < a[i]) {
      int j = mx.top();
      mx.pop();
      majid(j, mx.size() ? mx.top() : n, a[i] - a[j]);
    }
    mx.push(i);
    if (lastseen.count(a[i])) smin(ptr, lastseen[a[i]]);
    int to = hamid(ptr);
    if (smax(ans, to - i + 1) || ans == to - i + 1 && l > i + base)
      l = i + base, r = to + base;
    lastseen[a[i]] = i;
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k >> d;
  for (int i = 0; i < n; i++) cin >> a[i];
  if (d == 0) {
    for (int i = 0; i < n;) {
      int j = i;
      while (j < n && a[j] == a[i]) j++;
      if (smax(ans, j - i)) l = i, r = j - 1;
      i = j;
    }
    return cout << l + 1 << ' ' << r + 1 << '\n', 0;
  }
  for (int i = 0, j = 0; i < n; i = j) {
    while (j < n && (a[i] % d + d) % d == (a[j] % d + d) % d) j++;
    int mod = a[i] % d;
    for (int k = i; k < j; k++) a[k] -= mod, a[k] /= d;
    solve(a + i, j - i, i);
  }
  cout << l + 1 << ' ' << r + 1 << '\n';
  return 0;
}
