Kxorbonacci

kxorbonacci

== include(page="template/taskheader" task_id="kxorbonacci") ==

$Tyrant's eye$ a găsit, explorând nişte ruine magice, definiţia unui nou tip de şir, numit şirul mistic! Valorile şirului sunt $a[1],...$, iar şirul se consideră a fi infinit. Şirul mistic este determinat de primele $K$ elemente $a[1], ..., a[K]$. Următoarele numere sunt egale cu $xor$-ul ultimelor $K$ numere din şir. Astfel $a[K+1] = a[1] xor ... xor a[K]$, şi $a[K+2] = a[2] xor ... xor a[K+1]$, şi aşa mai departe.

Komi a găsit, explorând nişte ruine magice, definiţia unui nou tip de şir, numit şirul mistic! Valorile şirului sunt $a[1],...$, iar şirul se consideră a fi infinit. Şirul mistic este determinat de primele $K$ elemente $a[1], ..., a[K]$. Următoarele numere sunt egale cu $xor$-ul ultimelor $K$ numere din şir. Astfel $a[K+1] = a[1] xor ... xor a[K]$, şi $a[K+2] = a[2] xor ... xor a[K+1]$, şi aşa mai departe.

$Tyrant's eye$ a reuşit până la urmă să găsească, adânc în ruină, un şir de $N$ numere $v[1], ..., v[N]$. Ea ghiceşte că acest şir este o subsecvenţă a şirului mistic; adică, pentru o poziţie $P$, $v[1] = a[P], v[2] = a[P+1], ..., v[N] = a[P+N-1]$. Ea vrea acum să găsească pe $K$ şi pe $P$. În cazul în care sunt mai multe soluţii posibile, să se găsească cea cu $K$ minim; dacă tot sunt mai multe soluţii posibile, să se găsească cea cu $P$ minim.

Komi a reuşit până la urmă să găsească, adânc în ruină, un şir de $N$ numere $v[1], ..., v[N]$. Ea ghiceşte că acest şir este o subsecvenţă a şirului mistic; adică, pentru o poziţie $P$, $v[1] = a[P], v[2] = a[P+1], ..., v[N] = a[P+N-1]$. Ea vrea acum să găsească pe $K$ şi pe $P$. În cazul în care sunt mai multe soluţii posibile, să se găsească cea cu $K$ minim; dacă tot sunt mai multe soluţii posibile, să se găsească cea cu $P$ minim.

h2. Date de intrare

Fişierul de intrare $kxorbonacci.in$ conţine, pe primul rând, numărul $T$ de teste in fişier. Urmează $T$ perechi de rânduri, fiecare descriind câte un scenariu de test. Primul rând conţine numărul $N$, al doilea rând conţine valorile $v[1], ..., v[N]$.

Fişierul de intrare $kxorbonacci.in$ conţine două rânduri. Primul rând conţine numărul $N$, al doilea rând conţine valorile $v[1], ..., v[N]$.

h2. Date de ieşire

În fişierul de ieşire $kxorbonacci.out$ se vor afişa $T$ rânduri. Fiecare rând va conţine răspunsul pentru un test, mai exact valorile $K$ şi $P$ cerute.

În fişierul de ieşire $kxorbonacci.out$ se vor afişa valorile $K$ şi $P$ cerute.

h2. Restricţii

* $1 ≤ N ≤ 300.000$.
* $0 ≤ v[i] ≤ 10^9^$.
* $1 ≤ T ≤ 10$.
* Suma valorilor lui $N$ într-un fişier este cel mult $300.000$.

* $1 ≤ N ≤ 1.000.000$.
* $1 ≤ v[i] ≤ 10^9^$.

* Pentru $10$ puncte, $K = 1$.
* Pentru alte $10$ puncte, $K ≤ 2$.
* Pentru alte $10$ puncte, $K ≤ 15, v[i] ≤ 1$.

h2. Exemplu
table(example). |_. kxorbonacci.in |_. kxorbonacci.out |

| 3
5

| 5

1 0 1 1 0

5
1 2 3 1 2
5
0 0 0 0 0
| 2 1
2 1
1 1|

| 2 1 |

h3. Explicaţie

Pentru primul test, $K = 2$ şi $a[1] = 1, a[2] = 0$. Dacă aplicam regula din enunţ pentru a calcula următorile valori din $a$, deducem că $a[3] = a[1] xor a[2] = 1 xor 0 = 1$, $a[4] = a[2] xor a[3] = 0 xor 1 = 1$, $a[5] = a[3] xor a[4] = 1 xor 1 = 0$. Astfel vedem că $v$ se regăseşte în $a$ începând la poziţia $P = 1$.

Pentru acest test, $K = 2$ şi $a[1] = 1, a[2] = 0$. Dacă aplicam regula din enunţ pentru a calcula următorile valori din $a$, deducem că $a[3] = a[1] xor a[&#50] = 1 xor 0 = 1$, $a[&#52] = a[&#50] xor a[&#51] = 0 xor 1 = 1$, $a[&#53] = a[&#51] xor a[&#52] = 1 xor 1 = 0$. Astfel vedem că $v$ se regăseşte în $a$ începând la poziţia $P = 1$.

== include(page="template/taskfooter" task_id="kxorbonacci") ==