Fisierul bac.in contine numere naturale: pe prima linie doua numere din intervalul [1,10^6], m si n, pe a doua linie un sir de m numere din intervalul [1,10^9], iar pe a treia linie un sir de n numere din intervalul [1,10^9]. Numerele aflate pe aceeasi linie a fisierului sunt separate prin cate un spatiu, si ambele siruri sunt ordonate crescator.
Se cere sa se afiseze pe ecran, in ordine strict crescatoare, un sir format dintr-un numar maxim de termeni care apartin cel putin unuia dintre cele doua siruri, astfel incat oricare doua elemente aflate pe pozitii consecutive sa fie de paritate diferita. Numerele afisate sunt separate prin cate un spatiu. Proiectati un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: daca fisierul are continutul m=8, n=5, sirul1=2 4 5 8 8 11 14 14, sirul2=3 4 5 5 10, se afiseaza pe ecran 2 3 4 5 8 11 14 sau 2 3 4 5 10 11 14
- Date de intrare
- Fisierul bac.in: m n pe prima linie, sirul1 pe a doua, sirul2 pe a treia.
- Date de iesire
- Cel mai lung sir alternant de paritate obtinut din reuniunea celor doua siruri, crescator.
- Restrictii
- 1 <= m, n <= 10^6
Exemple
Exemplul 1
Intrare
8 5 2 4 5 8 8 11 14 14 3 4 5 5 10
Iesire
2 3 4 5 8 11 14
Exemplul 2
Intrare
1 1 2 3
Iesire
2 3