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;
int N, K, D;
int A[200000];
void solve1() {
  pair<int, int> res = make_pair((1 << 30), -1);
  int ptr = 0;
  while (ptr < N) {
    int st = ptr;
    while (ptr < N && A[ptr] == A[st]) ptr++;
    if (res.second - res.first < (ptr - 1) - st) res = make_pair(st, ptr - 1);
  }
  printf("%d %d\n", res.first + 1, res.second + 1);
}
pair<int, int> res = make_pair((1 << 30), -1);
void updateres(int l, int r) {
  if (res.second - res.first < r - l)
    res = make_pair(l, r);
  else if (res.second - res.first == r - l && l < res.first)
    res = make_pair(l, r);
}
vector<int> lis;
struct SegTree {
  int dat[(1 << 18) * 2 - 1];
  int n;
  void init(int n_) {
    n = 1;
    while (n < n_) n *= 2;
    for (int(i) = 0; (i) < (n); (i)++) dat[i + n - 1] = -i + n_;
    for (int i = n - 2; i >= 0; i--) {
      int pp = min(dat[i * 2 + 1], dat[i * 2 + 2]);
      dat[i] = pp, dat[i * 2 + 1] -= pp, dat[i * 2 + 2] -= pp;
    }
  }
  void add(int a, int b, int k, int l, int r, int s) {
    if (r <= a || b <= l) return;
    if (a <= l && r <= b)
      dat[k] += s;
    else {
      add(a, b, k * 2 + 1, l, (l + r) / 2, s);
      add(a, b, k * 2 + 2, (l + r) / 2, r, s);
      int pp = min(dat[k * 2 + 1], dat[k * 2 + 2]);
      dat[k] += pp, dat[k * 2 + 1] -= pp, dat[k * 2 + 2] -= pp;
    }
  }
  int search(int a, int b, int k, int l, int r, int s) {
    if (r <= a || b <= l) return -1;
    if (dat[k] > s) return -1;
    if (l + 1 == r) return l;
    int tmp = search(a, b, k * 2 + 2, (l + r) / 2, r, s - dat[k]);
    if (tmp != -1) return tmp;
    return search(a, b, k * 2 + 1, l, (l + r) / 2, s - dat[k]);
  }
} seg;
pair<int, int> st1[210000];
pair<int, int> st2[210000];
int ptr1, ptr2;
void ins_M(int a, int s) {
  while (st1[ptr1 - 1].first <= s) {
    seg.add(st1[ptr1 - 1].second, st1[ptr1 - 2].second, 0, 0, seg.n,
            -st1[ptr1 - 1].first);
    ptr1--;
  }
  seg.add(a, st1[ptr1 - 1].second, 0, 0, seg.n, s);
  st1[ptr1++] = make_pair(s, a);
}
void ins_m(int a, int s) {
  while (st2[ptr2 - 1].first >= s) {
    seg.add(st2[ptr2 - 1].second, st2[ptr2 - 2].second, 0, 0, seg.n,
            st2[ptr2 - 1].first);
    ptr2--;
  }
  seg.add(a, st2[ptr2 - 1].second, 0, 0, seg.n, -s);
  st2[ptr2++] = make_pair(s, a);
}
void solve(int fis) {
  int n = lis.size();
  seg.init(n);
  ptr1 = ptr2 = 0;
  st1[ptr1++] = make_pair((1 << 30), n);
  st2[ptr2++] = make_pair(-(1 << 30), n);
  map<int, int> m;
  int rp = lis.size();
  for (int i = n - 1; i >= 0; i--) {
    seg.add(0, seg.n, 0, 0, seg.n, -1);
    ins_M(i, lis[i]);
    ins_m(i, lis[i]);
    if (m.count(lis[i])) rp = min(rp, m[lis[i]]);
    m[lis[i]] = i;
    int tmp = seg.search(i, rp, 0, 0, seg.n, K);
    if (tmp != -1) updateres(fis + i, fis + tmp);
  }
}
int main() {
  scanf("%d%d%d", &N, &K, &D);
  for (int(i) = 0; (i) < (N); (i)++) scanf("%d", &A[i]);
  if (D == 0) {
    solve1();
    return 0;
  }
  int ptr = 0;
  while (ptr < N) {
    int st = ptr;
    while (ptr < N && (A[st] % D + D) % D == (A[ptr] % D + D) % D) ptr++;
    lis.clear();
    for (int(i) = (st); (i) < (ptr); (i)++)
      lis.push_back((A[i] - (A[i] % D + D) % D) / D);
    solve(st + 1);
  }
  printf("%d %d\n", res.first, res.second);
}
