Шеф заинтересовался изучением двудольных графов. Сегодня он хочет построить двудольный граф с $n$ вершинами в каждой из двух частей и с общим числом ребер, равным $m$. Вершины слева пронумерованы от $1$ до $n$. Вершины справа тоже пронумерованы от $1$ до $n$. Он также хочет, чтобы степень каждой вершины была больше или равна $d$ и меньше или равна $D$. т.е. для всех $v: d \le deg(v) \le D$. По четырем целым числам $n, m, d, D$ Вы должны помочь Шефу построить некоторый двудольный граф, удовлетворяющий описанному свойству. Если такого графа не существует, выведите $-1$. \InputFile Первая строка содержит количество тестов $t$. Одна строка каждого набора входных данных содержит четыре целых числа $n~(1 \le n \le 100)$, $m~(0 \le m \le n \cdot n)$, $d, D~(1 \le d \le D \le n)$. \OutputFile Для каждого набора входных данных выведите $-1$, если не существует двудольного графа, удовлетворяющего заданному свойству. В противном случае выведите $m$ строк, каждая из которых должна содержать два целых числа $u$ и $v$, обозначающие наличие ребра между вершиной $u$ в левой части и вершиной $v$ в правой части. Если существует несколько возможных ответов, выведите любой. Обратите внимание, что двудольный граф не должен иметь кратных ребер.