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, inf = 1e9;
int a[maxn], ANS = -1, L = -1, R = -1, n, k;
long long mn[4 * maxn], lz[4 * maxn];
inline void Best(int l, int r) {
  if (r - l > ANS) ANS = r - l, R = r - 1, L = l;
  if (r - l == ANS && l < L) R = r - 1, L = l;
}
void get(int l, int r, int id) {
  mn[id] += lz[id];
  if (r - l > 1) {
    lz[2 * id] += lz[id];
    lz[2 * id + 1] += lz[id];
  }
  lz[id] = 0;
}
void Add(int f, int s, int x, int l = 0, int r = n, int id = 1) {
  if (f >= s || l >= r) return;
  get(l, r, id);
  if (s <= l || r <= f) return;
  if (f <= l && r <= s) {
    lz[id] += x;
    get(l, r, id);
    return;
  }
  int mid = (l + r) >> 1;
  Add(f, s, x, l, mid, 2 * id);
  Add(f, s, x, mid, r, 2 * id + 1);
  mn[id] = min(mn[2 * id], mn[2 * id + 1]);
}
int Ask(int x, int l = 0, int r = n, int id = 1) {
  get(l, r, id);
  if (r - l == 1) return l;
  int mid = (l + r) >> 1;
  if (mn[2 * id] + lz[2 * id] <= x) return Ask(x, l, mid, 2 * id);
  return Ask(x, mid, r, 2 * id + 1);
}
void solve(int f, int s) {
  map<int, int> lst;
  deque<int> MX, MN;
  MX.push_back(-1), MN.push_back(-1);
  int pos = f;
  for (int i = f; i < s; i++) {
    if (lst.count(a[i])) {
      int num = lst[a[i]] + 1;
      Add(pos, num, inf);
      pos = max(pos, num);
    }
    lst[a[i]] = i;
    while (MX.back() != -1 && a[MX.back()] < a[i]) {
      Add(MX[int((MX).size()) - 2] + 1, MX.back() + 1, a[i] - a[MX.back()]);
      MX.pop_back();
    }
    while (MN.back() != -1 && a[MN.back()] > a[i]) {
      Add(MN[int((MN).size()) - 2] + 1, MN.back() + 1, a[MN.back()] - a[i]);
      MN.pop_back();
    }
    MX.push_back(i), MN.push_back(i);
    Add(pos, i, -1);
    Best(Ask(k), i + 1);
  }
  Add(pos, s, inf);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int d;
  cin >> n >> k >> d;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (d == 0) {
    int beg = 0, bef = a[0];
    for (int i = 0; i < n; i++) {
      if (a[i] != bef) {
        Best(beg, i);
        beg = i, bef = a[i];
      }
    }
    Best(beg, n);
  } else {
    int beg = 0, bef = a[0] % d;
    for (int i = 0; i < n; i++) {
      int num = a[i] % d;
      num = (num + d) % d;
      a[i] = (a[i] - num) / d;
      if (bef != num) solve(beg, i), beg = i, bef = num;
    }
    solve(beg, n);
  }
  return cout << L + 1 << " " << R + 1 << endl, 0;
}
