You are given four integers n, m, l and r.

Let's name a tuple (x_1, y_1, x_2, y_2) as good if: 

  1. 1 ≤ x_1 < x_2 ≤ n; 
  2. 1 ≤ y_2 < y_1 ≤ m; 
  3. x_1 ⋅ y_1 = x_2 ⋅ y_2; 
  4. l ≤ x_1 ⋅ y_1 ≤ r. 



Find any good tuple for each x_1 from 1 to n inclusive.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 2 ⋅ 10^5).

The second line contains two integers l and r (1 ≤ l ≤ r ≤ nm).

Output

For each x_1 from 1 to n inclusive: 

  * if there are no such four integers, print -1; 
  * otherwise, print four integers x_1, y_1, x_2 and y_2. If there are multiple answers, print any of them. 

Examples

Input


8 20
91 100


Output


-1
-1
-1
-1
-1
6 16 8 12
-1
-1


Input


4 5
1 10


Output


1 2 2 1
2 3 3 2
-1
-1


Input


5 12
16 60


Output


-1
2 9 3 6
3 8 4 6
4 5 5 4
-1
#include <bits/stdc++.h>
constexpr int N = 2e5;
std::vector<int> divisors[N + 1];
int cnt[N + 1];
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m;
  std::cin >> n >> m;
  int64_t l, r;
  std::cin >> l >> r;
  --l;
  for (int i = 1; i <= N; ++i)
    for (int j = i; j <= N; j += i) divisors[j].push_back(i);
  std::set<int> s;
  for (int x1 = 1, L = m, R = m; x1 <= n; ++x1) {
    int64_t ly = l / x1;
    int64_t ry = std::min<int64_t>(m, r / x1);
    if (ly >= ry) {
      std::cout << -1 << "\n";
      continue;
    }
    while (L > ly) {
      for (auto c : divisors[L]) {
        if (cnt[c] == 0) s.insert(c);
        ++cnt[c];
      }
      --L;
    }
    while (R > ry) {
      for (auto c : divisors[R]) {
        --cnt[c];
        if (cnt[c] == 0) s.erase(c);
      }
      --R;
    }
    bool ok = false;
    for (auto b : divisors[x1]) {
      int a = x1 / b;
      auto it = s.upper_bound(b);
      if (it != s.end() && *it <= n / a) {
        int c = *it;
        int d = R / c;
        std::cout << a * b << " " << c * d << " " << a * c << " " << b * d
                  << "\n";
        ok = true;
        break;
      }
    }
    if (!ok) std::cout << -1 << "\n";
  }
  return 0;
}
