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 = 200000;
int n, K, D, a[maxn + 5], b[maxn + 5], tem[maxn + 5], r[maxn + 5], ans, AL, AR;
bool vis[maxn + 5];
int top[2], stk[2][maxn + 5], R[2][maxn + 5];
long long MIN[(maxn << 2) + 5], tag[(maxn << 2) + 5];
inline int Find(int x, int L = 1, int R = tem[0]) {
  for (int mid = L + (R - L >> 1); L <= R; mid = L + (R - L >> 1))
    if (x == tem[mid])
      return mid;
    else
      x < tem[mid] ? R = mid - 1 : L = mid + 1;
}
inline void OrzZH() {
  int ans = 1, L = 1, R = 1, lst = 1;
  for (int i = 2; i <= n; i++)
    if (a[i - 1] != a[i]) {
      if (i - lst > ans) ans = i - lst, L = lst, R = i - 1;
      lst = i;
    }
  if (n - lst + 1 > ans) L = lst, R = n;
  printf("%d %d\n", L, R);
}
inline void Addtag(int p, long long k) {
  MIN[p] += k;
  tag[p] += k;
}
inline void Pushdown(int p) {
  if (tag[p]) Addtag(p << 1, tag[p]), Addtag(p << 1 | 1, tag[p]), tag[p] = 0;
}
void Insert(int L, int R, long long k, int l = 1, int r = n, int p = 1) {
  if (L == l && r == R) return Addtag(p, k);
  int mid = l + (r - l >> 1);
  Pushdown(p);
  if (R <= mid)
    Insert(L, R, k, l, mid, p << 1);
  else if (L > mid)
    Insert(L, R, k, mid + 1, r, p << 1 | 1);
  else
    Insert(L, mid, k, l, mid, p << 1),
        Insert(mid + 1, R, k, mid + 1, r, p << 1 | 1);
  (MIN[p] = min(MIN[(p) << 1], MIN[(p) << 1 | 1]));
}
inline void Push(int x, int lst = 0) {
  lst = x;
  while (top[0] && stk[0][top[0]] > a[x])
    Insert(lst + 1, R[0][top[0]], stk[0][top[0]] - a[x]), lst = R[0][top[0]--];
  stk[0][++top[0]] = a[x];
  R[0][top[0]] = lst;
  lst = x;
  while (top[1] && stk[1][top[1]] < a[x])
    Insert(lst + 1, R[1][top[1]], a[x] - stk[1][top[1]]), lst = R[1][top[1]--];
  stk[1][++top[1]] = a[x];
  R[1][top[1]] = lst;
}
int Ask(int L, int R, long long k, int l = 1, int r = n, int p = 1) {
  if (R < l || r < L) return -1;
  if (l == r) return l;
  int mid = l + (r - l >> 1);
  Pushdown(p);
  int pos = -1;
  if (MIN[p << 1 | 1] <= k) pos = Ask(L, R, k, mid + 1, r, p << 1 | 1);
  if (pos < 0 && MIN[p << 1] <= k) pos = Ask(L, R, k, l, mid, p << 1);
  return pos;
}
int main() {
  scanf("%d%d%d", &n, &K, &D);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  if (!D) return OrzZH(), 0;
  for (int i = 1; i <= n; i++) b[i] = (a[i] % D + D) % D;
  tem[0] = 0;
  for (int i = 1; i <= n; i++) tem[++tem[0]] = a[i];
  sort(tem + 1, tem + 1 + tem[0]);
  tem[0] = unique(tem + 1, tem + 1 + tem[0]) - tem - 1;
  for (int i = 1; i <= n; i++) a[i] = Find(a[i]);
  for (int i = 1, j = 0; i <= n; vis[a[i]] = false, r[i++] = j)
    while (j < n && b[i] == b[j + 1] && !vis[a[j + 1]]) vis[a[++j]] = true;
  for (int i = 1; i <= n; i++) a[i] = tem[a[i]];
  ans = 1;
  AL = n;
  AR = n;
  Insert(n, n, (long long)-D * n);
  Push(n);
  for (int i = n - 1; i; i--) {
    Insert(i, i, (long long)-D * i);
    Push(i);
    if (MIN[1] > (long long)D * (K - i)) continue;
    int pos = Ask(i, r[i], (long long)D * (K - i));
    if (pos - i + 1 >= ans) ans = pos - i + 1, AL = i, AR = pos;
  }
  return printf("%d %d\n", AL, AR), 0;
}
