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

$Kokalaru47$ a intrat într-o nouă încurcătură! Prietenul său, $Marele Anonim$, şi-a cumpărat de curând o permutare $p$ de o frumuseţe nemaiauzită. Curios din fire, $Kokalaru47$ vrea să afle permutarea. $Marele Anonim$ i-a zis doar că are lungimea $N$ şi că $1$ apare înaintea lui $2$ în permutarea $p$, şi a decis să nu dezvăluie în mod direct alte informaţii. În schimb, îi va răspunde la mai multe întrebări.

$Kokalaru47$ a intrat într-o nouă încurcătură! Prietenul său, $Marele Anonim$, şi-a cumpărat de curând o permutare $p$ de o frumuseţe nemaiauzită. Curios din fire, $Kokalaru47$ vrea să afle permutarea. $Marele Anonim$ i-a zis doar că are lungimea $N$ şi că *$1$ apare înaintea lui $2$* în permutarea $p$, şi a decis să nu dezvăluie în mod direct alte informaţii. În schimb, îi va răspunde la mai multe întrebări.

Într-o întrebare, $Kokalaru47$ îi dă $Marelui Anonim$ două stringuri $A$ şi $B$ de lungime $N$. $Marele Anonim$ creează apoi alte două stringuri $C$ şi $D$ astfel încât $A=C{~p{~1~}~}C{~p{~2~}~}C{~p{~3~}~}...C{~p{~N~}~}$ şi $B=D{~p{~1~}~}D{~p{~2~}~}D{~p{~3~}~}...D{~p{~N~}~}$. În final, $Marele Anonim$ răspunde la întrebare cu lungimea prefixului maximal comun dintre $C$ şi $D$ în care există *cel mult o nepotrivire*.

| 1
| 5
| 8

| $10^9^$
| 10

| $10^1000^$
| 10p

|
| 2
| 5
| 50

| $10^9^$
| 10

| $10^1000^$
| 10p

|
| 3
| 5
| 200
| 2000

| 30

| 30p

|
| 4
| 5
| 200
| 840

| 20

| 20p

|
| 5
| 5
| 200
| 440

| 30

| 30p

|
h2. Exemplu