Şef və ikiqat qraf

Şef iki hissəli qrafiklərin öyrənilməsinə maraq göstərdi. Bu gün o, hər iki hissədə $n$ təpəsi olan və ümumi kənar sayı $m$ olan iki hissəli qrafik qurmaq istəyir. Sol tərəfdəki təpələr $1$-dən $n$-ə qədər nömrələnmişdir. Sağ tərəfdəki təpələr də $1$-dən $n$-ə qədər nömrələnmişdir. O həmçinin istəyir ki, hər bir təpənin dərəcəsi $d$-dən böyük və ya bərabər, $D$-dən kiçik və ya bərabər olsun. Yəni, bütün $v$ üçün: $d\le deg(v)\le D$.

Dörd tam ədəd $n,m,d,D$ verildikdə, siz Şefə təsvir olunan xüsusiyyətə uyğun olan bir iki hissəli qrafik qurmağa kömək etməlisiniz. Əgər belə bir qrafik mövcud deyilsə, $-1$ çıxış edin.

Giriş verilənləri

Birinci sətir testlərin sayını $t$ ehtiva edir.

Hər bir giriş məlumat dəstinin bir sətiri dörd tam ədəd $n(1\le n\le 100)$, $m(0\le m\le n\cdot n)$, $d,D(1\le d\le D\le n)$ ehtiva edir.

Çıxış verilənləri

Hər bir giriş məlumat dəsti üçün, əgər verilən xüsusiyyətə uyğun iki hissəli qrafik mövcud deyilsə, $-1$ çıxış edin. Əks halda, $m$ sətir çıxış edin, hər biri sol hissədəki $u$ təpəsi ilə sağ hissədəki $v$ təpəsi arasında kənarın mövcudluğunu göstərən iki tam ədəd $u$ və $v$ ehtiva etməlidir. Əgər bir neçə mümkün cavab varsa, istənilən birini çıxış edin. Qeyd edin ki, iki hissəli qrafik təkrarlanan kənarlara malik olmamalıdır.

Nümunələr