Шеф і двочастковий граф

Шеф зацікавився вивченням двочасткових графів. Сьогодні він хоче створити двочастковий граф, що складається з $n$ вершин у кожній з двох частин, з загальною кількістю ребер, рівною $m$. Вершини зліва пронумеровані від $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$ в правій частині. Якщо існує кілька можливих рішень, виведіть будь-яке з них. Зверніть увагу, що двочастковий граф не повинен містити кратних ребер.

Приклади