Una spaziert auf einem Pfad mit $n$ Kirschbäumen, während Frühlingsfragmente sanft vom Himmel fallen. Auf dem $i$-ten Kirschbaum befinden sich $a_i$ Blüten.
Una vermisst ihre beste Freundin Kamome sehr. Sie erinnert sich daran, dass Kamome ihr an dem Tag, an dem sie diese Stadt verließ, eine ganzzahlige Folge $b_1, \dots, b_n$ gab. Kamome sagte Una, dass die magische Kraft in den Kirschbäumen aktiviert wird und sie sich wiedersehen werden, sobald $a_i \equiv b_i \pmod 2$ für jedes $i \in [1, n]$ gilt.
Unas Wunsch war so stark, dass ihre Vorstellungskraft Wirklichkeit wurde. Sie erlangte die magische Kraft, Blumen zum Blühen zu bringen. Bei jedem Schwung ihres Zauberstabs kann sie eine zusammenhängende Teilfolge von Kirschbäumen $[l, r]$ auswählen und $a_i$ für jedes $i \in [l, r]$ gleichzeitig zu $\sum_{j=l}^i a_j$ ändern.
Mit Magie begabt, kann Una jeden Tag beliebig oft Magie wirken, darf jedoch am selben Tag nicht zweimal oder öfter Magie auf denselben Baum wirken, da der Baum sonst durch die übermäßige Menge an magischer Kraft abstirbt. (Mit anderen Worten: Die am selben Tag gewählten Teilfolgen dürfen sich nicht überschneiden.)
Una hat Kamome seit zehn Jahren nicht mehr gesehen und möchte nicht länger warten. Una möchte die minimale Anzahl an Tagen wissen, bis sie sich wiedersehen können (d. h. $a_i \equiv b_i \pmod 2$ für jedes $i \in [1, n]$ zu erreichen), sowie welche Magie sie an jedem Tag wirken soll, um dieses Minimum zu erreichen. Beachte, dass dies unmöglich sein kann; in diesem Fall solltest du ihr das mitteilen. (Weitere Einzelheiten findest du im Abschnitt „Ausgabe“.)
Eingabe
Jeder Test enthält mehrere Testfälle. Die erste Zeile enthält die Anzahl der Testfälle $t$ ($1 \le t \le 2.5 \times 10^4$). Es folgt die Beschreibung der Testfälle.
Die erste Zeile jedes Testfalls enthält eine einzelne ganze Zahl $n$ ($1 \le n \le 10^3$, $\sum n^2 \le 10^6$), die Anzahl der Kirschbäume.
Die zweite Zeile jedes Testfalls enthält $n$ ganze Zahlen $a_1, \dots, a_n$ ($0 \le a_i \le 1$), die aktuelle Anzahl der Blüten auf jedem Baum.
Die dritte Zeile jedes Testfalls enthält $n$ ganze Zahlen $b_1, \dots, b_n$ ($0 \le b_i \le 1$), die Folge, die Kamome Una gegeben hat.
Ausgabe
Gib für jeden Testfall -1 aus, wenn es unmöglich ist, dass Kamome und Una sich wiedersehen. Andernfalls gib eine einzelne ganze Zahl $k$ aus, die die minimale Anzahl an Tagen darstellt, die Una benötigt, um Kamome wiederzusehen.
In der $i$-ten Zeile der nächsten $k$ Zeilen sollst du Una Anweisungen geben, welche Magie sie am $i$-ten Tag wirken soll. Gib $2c + 1$ ganze Zahlen $c_i, l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}, \dots, l_{i,c}, r_{i,c}$ aus, wobei $c$ die Anzahl der magischen Operationen ist, die sie am $i$-ten Tag ausführen soll, und $[l_{i,j}, r_{i,j}]$ die $j$-te zusammenhängende Teilfolge darstellt, die sie am $i$-ten Tag wählen soll. Du musst garantieren, dass $r_i < l_{i+1}$ für jedes $1 \le i \le c - 1$ und $l_i \le r_i$ für jedes $1 \le i \le c$ gilt.
Falls es mehrere Lösungen gibt, kannst du eine beliebige davon ausgeben.
Beispiel
Eingabe
3 5 1 0 1 0 1 0 1 0 1 0 3 1 1 0 1 1 1 10 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0
Ausgabe
-1 1 1 2 3 2 2 1 4 6 9 2 1 2 6 7
Hinweis
Im dritten Testfall lautet die Folge $a$ am Ende des ersten Tages $[\underline{1, 1, 1, 2}, 0, \underline{1, 1, 1, 2}, 0]$.
Am Ende des zweiten Tages lautet die Folge $a$ $[\underline{1, 2}, 1, 2, 0, \underline{1, 2}, 1, 2, 0]$.
Offensichtlich gilt nach zwei Tagen $a_i \equiv b_i \pmod 2$. Es lässt sich beweisen, dass dies nicht innerhalb eines Tages erreichbar ist.