Шеф заинтересовался изучением двудольных графов. Сегодня он хочет построить двудольный граф с n вершинами в каждой из двух частей и с общим числом ребер, равным m. Вершины слева пронумерованы от 1 до n. Вершины справа тоже пронумерованы от 1 до n. Он также хочет, чтобы степень каждой вершины была больше или равна d и меньше или равна D. т.е. для всех v: d ≤ deg(v) ≤ D.

По четырем целым числам n, m, d, D Вы должны помочь Шефу построить некоторый двудольный граф, удовлетворяющий описанному свойству. Если такого графа не существует, выведите -1.

Входные данные

Первая строка содержит количество тестов t.

Одна строка каждого набора входных данных содержит четыре целых числа n (1 ≤ n ≤ 100), m (0 ≤ m ≤ n * n), d, D (1 ≤ d ≤ D ≤ n).

Выходные данные

Для каждого набора входных данных выведите -1, если не существует двудольного графа, удовлетворяющего заданному свойству. В противном случае выведите m строк, каждая из которых должна содержать два целых числа u и v, обозначающие наличие ребра между вершиной u в левой части и вершиной v в правой части. Если существует несколько возможных ответов, выведите любой. Обратите внимание, что двудольный граф не должен иметь кратных ребер.