Una sta camminando lungo un sentiero con $n$ alberi di ciliegio, mentre frammenti di primavera cadono dolcemente dal cielo. Sull'$i$-esimo albero di ciliegio ci sono $a_i$ fiori.
A Una manca tantissimo la sua migliore amica, Kamome. Ricorda che, il giorno in cui Kamome lasciò questa città, le diede una sequenza di interi $b_1, \dots, b_n$. Kamome disse a Una che, quando $a_i \equiv b_i \pmod 2$ per ogni $i \in [1, n]$, il potere magico negli alberi di ciliegio si attiverà e loro si incontreranno di nuovo.
Il desiderio di Una era così forte che la sua immaginazione divenne realtà. Ottenne il potere magico di far sbocciare i fiori. A ogni colpo della sua bacchetta, può scegliere una sottosequenza contigua di alberi di ciliegio $[l, r]$ e cambiare $a_i$ in $\sum_{j=l}^i a_j$ per ogni $i \in [l, r]$.
Dotata di magia, Una può eseguire incantesimi qualsiasi numero di volte ogni giorno, ma non deve eseguire incantesimi sullo stesso albero due o più volte nello stesso giorno, altrimenti l'albero morirà a causa di una quantità eccessiva di potere magico. (In altre parole, le sottosequenze scelte nello stesso giorno non devono intersecarsi.)
Una non vede Kamome da dieci anni e non vuole aspettare oltre. Una vuole sapere il numero minimo di giorni affinché possano incontrarsi (cioè rendere $a_i \equiv b_i \pmod 2$ per ogni $i \in [1, n]$), e la magia che dovrebbe eseguire in ciascun giorno per raggiungere questo minimo. Nota che ciò potrebbe essere impossibile, nel qual caso dovresti dirglielo. (Fai riferimento alla sezione Output per maggiori dettagli.)
Input
Ogni test contiene più casi di test. La prima riga contiene il numero di casi di test $t$ ($1 \le t \le 2.5 \times 10^4$). Segue la descrizione dei casi di test.
La prima riga di ogni caso di test contiene un singolo intero $n$ ($1 \le n \le 10^3$, $\sum n^2 \le 10^6$), il numero di alberi di ciliegio.
La seconda riga di ogni caso di test contiene $n$ interi $a_1, \dots, a_n$ ($0 \le a_i \le 1$), il numero di fiori attualmente presenti su ciascun albero.
La terza riga di ogni caso di test contiene $n$ interi $b_1, \dots, b_n$ ($0 \le b_i \le 1$), la sequenza che Kamome ha dato a Una.
Output
Per ogni caso di test, se è impossibile far incontrare Kamome e Una, stampa -1. Altrimenti, stampa un singolo intero, $k$, che rappresenta il numero minimo di giorni richiesti affinché Una incontri Kamome.
Sulla $i$-esima riga delle successive $k$ righe, devi dare istruzioni a Una sulla magia che dovrebbe eseguire nell'$i$-esimo giorno. Devi stampare $2c + 1$ interi $c_i, l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}, \dots, l_{i,c}, r_{i,c}$, dove $c$ è il numero di operazioni magiche che dovrebbe eseguire nell'$i$-esimo giorno, e $[l_{i,j}, r_{i,j}]$ rappresenta la $j$-esima sottosequenza contigua che dovrebbe scegliere nell'$i$-esimo giorno. Devi garantire che $r_i < l_{i+1}$ per ogni $1 \le i \le c - 1$ e $l_i \le r_i$ per ogni $1 \le i \le c$.
Se ci sono più soluzioni, puoi stamparne una qualsiasi.
Esempio
Input
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
Output
-1 1 1 2 3 2 2 1 4 6 9 2 1 2 6 7
Note
Nel terzo caso di test, alla fine del primo giorno, la sequenza $a$ è $[\underline{1, 1, 1, 2}, 0, \underline{1, 1, 1, 2}, 0]$.
Alla fine del secondo giorno, la sequenza $a$ è $[\underline{1, 2}, 1, 2, 0, \underline{1, 2}, 1, 2, 0]$.
È chiaro che dopo due giorni $a_i \equiv b_i \pmod 2$. Si può dimostrare che questo risultato non è ottenibile in un solo giorno.