Шеф и двудольный граф

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

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

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

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

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

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

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

Примеры