Octagoon

Octa și Goon au inventat un joc nou.

Cerință

Se dau două șiruri de numere naturale $A$ și $B$ de lungime $N$, respectiv $M$. Pentru fiecare $i$ de la $1$ la $N$. Trebuie să spuneți câte valori $j$, unde $1 \leq j \leq M$ există astfel încât șirul format din primele $i$ elemente ale lui $A$, urmat de primele $j$ elemente ale lui $B$ să conțină element majoritar. Mai exact, șirul $[A_1, A_2, A_3, \dots, A_i, B_1, B_2, B_3, \dots , B_j]$ sa conțină element majoritar.

Spunem că un șir $x_1, x_2, \dots x_k$ conține element majoritar dacă există o valoare $V$ astfel încât $V$ apare de cel puțin $\lfloor \frac{K}{2} \rfloor + 1$ ori în șirul $x$.

Date de intrare

Pe prima linie se găsesc numerele $N, M$.

Pe a doua linie se află $N$ numere naturale, reprezentând șirul $A$.

Pe a treia linie se află $M$ numere naturale, reprezentând șirul $B$.

Date de ieșire

Pe prima linie se vor afișa $N$ numere. Al $i$-lea număr fiind răspunsul pentru prefixul de lungime $i$ din șirul $A$.

Restricții și precizări

$\textcolor{red}{Atenție!}$ Din cauza numărului mare de date de intrare, respectiv ieșire, vă recomandăm să adăugați următoarele linii de cod la începutul funcției main().

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

• $1 \leq N, M \leq 300 \ 000$
• $1 \leq A_i, B_i \leq N + M$

Exemplu

stdin

7 10
2 2 1 3 1 1 1
1 2 3 3 3 1 1 1 2 1

stdout

1 3 1 0 0 1 4 

Explicație

Pentru $i = 1$, singurul $j$ care este bun este $j = 2$. Pentru $i = 1$ și $j = 2$, șirul obținut este $[2, 1, 2]$, unde $2$ este element majoritar. În schimb, pentru $i = 1$ și $j = 1$, șirul obținut este $[2, 1]$ unde nici $1$, nici $2$ nu sunt elemente majoritare deoarece ele apar o singură dată, când ar trebui să apară de $2$ ori.