Prieteni

Cerință

Bogdan are pe o foaie de hartie un șir de numere naturale nenule, numit $A$. El s-a gândit să transforme șirul în felul următor:

1. Mai întâi împarte toate elementele șirului $A$ în $3$ secvențe disjuncte pe care le notează $X$, $Y$, $Z$ ($X$ este secvența cu elementele de la început, $Z$ cea cu elementele de la final și $Y$ cea cu elementele rămase în interior; fiecare dintre cele $3$ secvențe trebuie să aibă cel puțin un element). Această împărțire o face astfel încât lungimea secvenței $Y$ să fie cel mult egală cu jumătate din lungimea șirului dat $A$.
2. Elimină secvența $Y$ din șir. Apoi, la acest pas, secvențele $X$ și $Z$ se alipesc, în această ordine, formând un nou șir.
3. Așează secvența $Y$ pe noul șir la o poziție aleasă astfel încât toate elementele secvenței $Y$ să se poată așeza unul câte unul, consecutiv, peste elemente ale șirului rămas, începând cu poziția aleasă.
4. La valorile elementelor peste care se suprapun elemente ale secvenței așezate se adună elementul corespunzător din secvență. Se obține astfel un nou șir $B$.

Un exemplu de transformare este:

Șirul A al lui Bogdan: $\boxed{1, 2, 3, 4} \boxed{1, 2, 3, 3, 1} \boxed{2, 3, 4, 5}$.

Pasul $1$: Alege să formeze secvențele astfel: $X$ cu primele $4$ elemente $(1, 2, 3, 4)$, $Y$ cu elementele de pe poziții de la $5$ la $9 \ (1, 2, 3, 3, 1)$ și $Z$ cu elementele de pe poziții de la $10$ la $13 \ (2, 3, 4, 5)$.

Pasul $2$: după ștergerea secvenței $Y$, obținem: $1, 2, 3, 4, 2, 3, 4, 5$.

Pasul $3$: Aplică secvența extrasă începând cu poziția $3$ (de exemplu nu ar fi putut aplica secvența pe poziții mai mari sau egale cu 5 deoarece aceasta nu s-ar fi putut suprapune cu toate elementele peste șirul rămas):

    1 2 3 3 1
1 2 3 4 2 3 4 5

Pasul 4: Șirul $B$ devine: $1, 2, \textbf{4, 6, 5, 6, 5}, 5$.

Bogdan îi explică lui Cosmin regula sa de transformare și îi propune următorul joc: îi arată perechi de câte două șiruri $A$ și $B$ și, pentru fiecare pereche, îl întreabă: poți decide dacă șirul dat $B$ chiar se poate obține din șirul dat $A$ aplicând exact o dată regula descrisă? În cazul în care acest lucru este posibil se cere să identificăm și modul de obținere.

Date de intrare

Fișierul prieteni.in conține pe prima linie un număr $t$ reprezentând numărul de perechi de șiruri pe care Bogdan i le dă ca test lui Cosmin. În continuare sunt descrise cele $t$ perechi de șiruri, pe câte $4$ linii fiecare.
Prima linie a unui grup conține valoarea n reprezentând numărul de elemente ale șirului $A$. Pe linia a doua se află cele $n$ elemente ale șirului $A$, în ordinea pozițiilor, de la $1$ la $n$. Pe linia a treia se află o valoare $m$ reprezentând numărul de elemente ale șirului $B$. Pe a patra linie se află elementele șirului $B$ în ordinea pozitiilor, de la $1$ la $m$. Elementele aceleiași linii se dau separate prin câte un spațiu.

Date de ieșire

Fișierul prieteni.out conține t linii, fiecare conținând rezultatul verificării unei perechi de șiruri date $A$ și $B$, în ordinea în care apar la intrare. Dacă șirul $B$ nu poate fi obținut din șirul $A$, linia va conține doar valoarea $0$. În caz contrar, linia va conține $4$ valori, separate prin spatiu, astfel: 1 P L I. Valoarea $1$ reprezintă codul de succes ($B$ se poate obține din $A$). $P$ reprezintă poziția din $A$ de unde se extrage secvența. $L$ reprezintă lungimea secvenței extrase. $I$ reprezintă poziția unde începe în $B$ aplicarea secvenței. Dacă sunt mai multe variante se va afișa cea cu $I$ minim și daca și aici avem mai multe variante, cea cu $P$ minim.

Restricții și precizări

• $1 \leq t \leq 10$;
• $3 \leq n \leq 2 \ 000$;
• $1 \leq m \leq 2 \ 000$;
• Elementele șirurilor date sunt naturale, nenule, cel mult egale cu $100$;
• Pentru $17$ puncte se garantează că toate perechile din fișierul de intrare pentru care $B$ se poate obține din $A$ au proprietatea că secvența extrasă $Y$ se aplică la aceeași poziție cu cea din care s-a extras.
• Pentru $31$ de puncte se garantează că toate perechile din fișierul de intrare pentru care $B$ se poate obține din $A$ au proprietatea că secvența extrasă $Y$ este formată dintr-un singur element.

Exemplu

prieteni.in

2
13
1 2 3 4 1 2 3 3 1 2 3 4 5
8
1 2 4 6 5 6 5 5
12
1 2 3 4 1 2 3 3 1 2 3 4
7
1 2 4 6 5 6 3

prieteni.out

1 5 5 3
0