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 long long MOD = 1e9 + 7;
const int INF = 1e9 + 1;
const long long INF64 = 1e18;
const double EPS = 1e-9;
const double PI = acos(-1);
const long long MD = 1551513443;
const long long T = 25923;
const int N = 200110;
const int M = 401;
struct Tree {
  long long t[N * 4], p[N * 4];
  Tree() {
    for (int i = 0; i < int(N * 4); i++) t[i] = p[i] = 0;
  }
  inline void push(int v, int tl, int tr) {
    if (tl != tr) {
      p[v * 2] += p[v];
      p[v * 2 + 1] += p[v];
    }
    t[v] += p[v];
    p[v] = 0;
  }
  void update(int v, int tl, int tr, int l, int r, long long val) {
    push(v, tl, tr);
    if (l > r) return;
    if (tl == l && tr == r) {
      p[v] += val;
      push(v, tl, tr);
    } else {
      int sdfjahlfasfh = (tl + tr) / 2;
      update(v * 2, tl, sdfjahlfasfh, l, min(r, sdfjahlfasfh), val);
      update(v * 2 + 1, sdfjahlfasfh + 1, tr, max(l, sdfjahlfasfh + 1), r, val);
      t[v] = min(t[v * 2], t[v * 2 + 1]);
    }
  }
  inline void upd(int l, int r, long long val) {
    update(1, 0, N - 10, l, r, val);
  }
  int get(int v, int tl, int tr, int l, int r, int k) {
    push(v, tl, tr);
    if (t[v] > k) return -1;
    if (l > r) return -1;
    if (tl == tr) {
      if (t[v] <= k) return tl;
      return -1;
    }
    if (tl == l && tr == r) {
      if (t[v] > k) return -1;
      int sdfjahlfasfh = (tl + tr) / 2;
      int ans1 =
          get(v * 2 + 1, sdfjahlfasfh + 1, tr, max(l, sdfjahlfasfh + 1), r, k);
      if (ans1 != -1) return ans1;
      return get(v * 2, tl, sdfjahlfasfh, l, min(r, sdfjahlfasfh), k);
    } else {
      int sdfjahlfasfh = (tl + tr) / 2;
      int ans1 =
          get(v * 2 + 1, sdfjahlfasfh + 1, tr, max(l, sdfjahlfasfh + 1), r, k);
      if (ans1 != -1) return ans1;
      return get(v * 2, tl, sdfjahlfasfh, l, min(r, sdfjahlfasfh), k);
    }
  }
  inline int get_k(int l, int r, int k) { return get(1, 0, N - 10, l, r, k); }
} t;
int n, k, d, a[N], l_ans, r_ans;
int p[N], r[N];
map<int, int> mm;
stack<pair<int, int> > s1, s2;
int main() {
  cin >> n >> k >> d;
  for (int i = 0; i < int(n); i++) {
    cin >> a[i];
    a[i] += INF;
  }
  if (d == 0) {
    for (int i = 0; i < int(n); i++) {
      int j = i;
      while (j < n && a[j] == a[i]) j++;
      if (j - i > r_ans - l_ans + 1) {
        l_ans = i;
        r_ans = j - 1;
      }
      i = j - 1;
    }
  } else {
    for (int i = 0; i < int(n); i++) {
      p[i] = a[i] % d;
      a[i] /= d;
      mm[a[i]] = n;
    }
    r[n - 1] = n - 1;
    for (int i = n - 1; i >= 0; i--) {
      if (i < n - 1) r[i] = r[i + 1];
      r[i] = min(r[i], mm[a[i]] - 1);
      mm[a[i]] = i;
    }
    for (int i = n - 1; i >= 0; i--) {
      int j = i;
      while (j >= 0 && p[j] == p[i]) {
        r[j] = min(r[j], i);
        j--;
      }
      i = j + 1;
    }
    for (int i = n - 1; i >= 0; i--) {
      while (!s1.empty() && a[s1.top().first] <= a[i]) {
        t.upd(s1.top().first, s1.top().second, -a[s1.top().first]);
        s1.pop();
      }
      if (!s1.empty())
        s1.push(make_pair(i, s1.top().first - 1));
      else
        s1.push(make_pair(i, n - 1));
      t.upd(s1.top().first, s1.top().second, a[s1.top().first]);
      while (!s2.empty() && a[s2.top().first] >= a[i]) {
        t.upd(s2.top().first, s2.top().second, a[s2.top().first]);
        s2.pop();
      }
      if (!s2.empty())
        s2.push(make_pair(i, s2.top().first - 1));
      else
        s2.push(make_pair(i, n - 1));
      t.upd(s2.top().first, s2.top().second, -a[s2.top().first]);
      t.upd(i + 1, n - 1, -1);
      int v = t.get_k(i, r[i], k);
      if (v >= i && v - i + 1 >= r_ans - l_ans + 1) {
        l_ans = i;
        r_ans = v;
      }
    }
  }
  cout << l_ans + 1 << ' ' << r_ans + 1;
  return 0;
}
