Ilinca şi verişoara ei Daria, merg la un curs de gătit. Ilinca a făcut o prăjitură cu N straturi, iar Daria a făcut o prăjitură cu M straturi, straturile prăjiturilor fiind aşezate unul după altul pe orizontală şi având diverse culori. E posibil ca unele straturi din prăjitură să aibă aceeaşi culoare.
Ilinca a observat că dacă ar tăia prăjitura ei la capete ar putea obţine o prăjitură la fel ca prăjitura Dariei. Ilinca spune că astfel „extrage” din prăjitura ei prăjitura Dariei. La o extragere, Ilinca taie întotdeauna un număr minim de straturi din partea stângă (straturi pe care le mănâncă imediat) şi câte straturi sunt necesare în partea dreaptă pentru a obţine o prăjitură identică cu prăjitura Dariei. Prăjitura extrasă o aşază pe o farfurie şi continuă „extragerile” din bucata rămasă în partea dreaptă.
Cerinţă
Scrieţi un program care să citească numerele naturale N şi M (reprezentând numărul de straturi din prăjitura Ilincăi respectiv Dariei) şi a1,a2,...,aN şi b1,b2,...,bM (reprezentând culorile straturilor din prăjitura Ilincăi respectiv din prăjitura Dariei) şi care să determine:
a) numărul de straturi pe care le taie Ilinca din capătul din stânga şi numărul de straturi pe care le taie din capătul din dreapta la prima extragere;
b) numărul de prăjituri identice cu prăjitura Dariei care se vor afla pe farfurie, după efectuarea tuturor extragerilor;
c) numărul maxim de prăjituri la fel ca prăjitura Dariei care pot fi obţinute din prăjitura Ilincăi dacă aceasta ar rearanja straturile prăjiturii ei într-o ordine convenabilă.
Date de intrare
Fişierul de intrare prajituri.in conţine pe prima linie numerele naturale N M reprezentând numărul de straturi din prăjitura Ilincăi, respectiv a Dariei. A doua linie a fişierului conţine, în ordine, cele N numere a1,a2,...,aN, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Ilincăi. A treia linie a fişierului conţine, în ordine, cele M numere b1,b2,...,bM, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Dariei.
Date de ieşire
Fişierul de ieşire prajituri.out va conţine pe prima linie două numere, separate printr-un spaţiu, reprezentând numărul de straturi tăiate din stânga, respectiv numărul de straturi tăiate din dreapta din prăjitura Ilincăi la prima extragere, separate prin spaţiu. A doua linie va conţine un număr natural reprezentând numărul de prăjituri aflate pe farfurie după efectuarea tuturor extragerilor. A treia linie va conţine un număr natural reprezentând numărul maxim de prăjituri la fel ca prăjitura Dariei care se pot obţine din prăjitura Ilincăi dacă aceasta ar rearanja convenabil straturile prăjiturii ei.
Restricţii
• 1 ≤ M ≤ N ≤ 10000
• 1 ≤ ai ≤ 100, (1≤i≤N)
• 1 ≤ bi ≤ 100, (1≤i≤M)
• N, M, a1, a2, ..., aN, b1, b2, ..., bMsunt numere naturale;
• Întotdeauna se poate obţine din prăjitura Ilincăi cel puţin o prăjitură la fel ca prăjitura Dariei
Exemple
prajituri.in
prajituri.out
Explicaţii
5 3
6 2 2 2 2
6 2 2
0 2
1
1
Prăjitura Ilincăi are 5 straturi, iar a Dariei 3 straturi, pentru a obţine prăjitura Dariei, Ilinca trebuie să taie din stânga 0 straturi şi din dreapta 2 straturi, se poate obţine doar o prăjitură ca a Dariei indiferent de procedeul folosit
10 2
5 6 8 8 6 8 6 8 6 6
6 8
1 7
3
4
Prăjitura Ilincăi are 10 straturi, iar a Dariei 2 straturi, pentru a obţine prăjitura Dariei, Ilinca trebuie să taie din stânga 1 strat şi din dreapta 7 straturi. Prin procedeul de tăiere se pot obţine 3 prăjituri la fel ca prăjitura Dariei. Prin rearanjarea straturilor se pot obţine maxim 4 prăjituri la fel ca prăjitura Dariei