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;
ifstream in("text.in");
ofstream out("text.out");
const int DIM = 2e5 + 9;
int arr[DIM], nxt[DIM];
vector<pair<int, int>> lst, stk1, stk2;
set<int> mst;
pair<int, int> sgt[DIM << 2];
void updl(int n, int l, int r) {
  if (sgt[n].second != 0) {
    sgt[n].first += sgt[n].second;
    if (l != r) {
      sgt[n << 1].second += sgt[n].second;
      sgt[n << 1 | 1].second += sgt[n].second;
    }
    sgt[n].second = 0;
  }
  return;
}
void update(int n, int l, int r, int st, int en, int x) {
  updl(n, l, r);
  if (l > r || st > en || l > en || st > r) return;
  if (st <= l && r <= en) {
    sgt[n].second += x;
    updl(n, l, r);
  } else {
    int m = (l + r) >> 1;
    update(n << 1, l, m, st, en, x);
    update(n << 1 | 1, m + 1, r, st, en, x);
    sgt[n].first = min(sgt[n << 1].first, sgt[n << 1 | 1].first);
  }
  return;
}
int query(int n, int l, int r, int st, int en, int x) {
  updl(n, l, r);
  int ans = -1;
  if (l > r || st > en || l > en || st > r || sgt[n].first > x) return -1;
  if (l == r)
    ans = (sgt[n].first <= x) ? l : -1;
  else {
    int m = (l + r) >> 1;
    ans = query(n << 1 | 1, m + 1, r, st, en, x);
    if (ans == -1) ans = query(n << 1, l, m, st, en, x);
  }
  return ans;
}
void traverse(int n, int l, int r) {
  updl(n, l, r);
  if (l > r) return;
  if (l == r)
    out << sgt[n].first << " ";
  else {
    int m = (l + r) >> 1;
    traverse(n << 1, l, m);
    traverse(n << 1 | 1, m + 1, r);
  }
  return;
}
int main(void) {
  ios::sync_with_stdio(false);
  int n, k, d;
  cin >> n >> k >> d;
  int ans = 0, pos = 0;
  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
    arr[i] += 1e9 + 1;
  }
  if (d == 0) {
    for (int i = 1, nr = 0; i <= n; i++) {
      if (arr[i] == arr[i - 1])
        nr++;
      else
        nr = 1;
      if (ans < nr) {
        ans = nr;
        pos = i - nr + 1;
      }
    }
  } else {
    for (int i = 1, l = 1; i <= n; i++) {
      if (arr[i] % d != arr[i + 1] % d || i == n) {
        lst.push_back(make_pair(l, i));
        l = i + 1;
      }
    }
    for (pair<int, int> pr : lst) {
      for (int i = pr.first; i <= pr.second; i++) arr[i] /= d;
      mst.clear();
      for (int i = pr.second, j = pr.second; i >= pr.first; i--) {
        while (mst.empty() == false && mst.find(arr[i]) != mst.end()) {
          mst.erase(mst.find(arr[j]));
          j--;
        }
        mst.insert(arr[i]);
        nxt[i] = j;
      }
      stk1.assign(1, make_pair(pr.second + 1, numeric_limits<int>::max()));
      stk2.assign(1, make_pair(pr.second + 1, numeric_limits<int>::min()));
      for (int i = pr.second; i >= pr.first; i--) {
        for (int sz = (int)stk1.size() - 1; stk1.back().second <= arr[i];
             stk1.pop_back(), sz--)
          update(1, 1, n, stk1[sz].first, stk1[sz - 1].first - 1,
                 arr[i] - stk1.back().second);
        stk1.push_back(make_pair(i, arr[i]));
        for (int sz = (int)stk2.size() - 1; stk2.back().second >= arr[i];
             stk2.pop_back(), sz--)
          update(1, 1, n, stk2[sz].first, stk2[sz - 1].first - 1,
                 stk2.back().second - arr[i]);
        stk2.push_back(make_pair(i, arr[i]));
        update(1, 1, n, i + 1, nxt[i], -1);
        int qry = query(1, 1, n, i, nxt[i], k);
        if (ans < qry - i + 1) {
          ans = qry - i + 1;
          pos = i;
        } else if (ans == qry - i + 1 && pos > i)
          pos = i;
      }
    }
  }
  cout << pos << " " << pos + ans - 1 << endl;
  return 0;
}
