Fişierul intrare/ieşire:	cars.in, cars.out	Sursă	Grigore Moisil 2018, 9
Autor	Bereczki Norbert Cristian, Mircea Popoveniuc, Sergiu Puscas	Adăugată de	Grigore Moisil •grigore.moisil
Timp execuţie pe test	1.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cars

Pentru a ajunge la cea de-a XXXIII-a ediţie a concursului Grigore Moisil, cei N+M membri ai comisiei au decis să profite de noua autostradă Cluj-Napoca - Târgu Mureş. Fiecare membru al comisiei conduce maşina proprie, reprezentată sub forma unui punct. Maşinile se clasifică în două categorii:

• N dintre ele sunt maşini rapide, cu viteza constantă egală cu A m/s.
• M dintre ele sunt maşini lente, cu viteza constantă egală cu B m/s.

Fiecare maşină porneşte de la o anumită poziţie întreagă, reprezentând distanţa faţă de Cluj-Napoca, măsurată în metri.
Autostrada are lungimea de L metri şi, din păcate, oferă o singură bandă de circulaţie. În schimb, este partiţionată în două tipuri de segmente:

• Segmente cu linie întreruptă, pe care se pot efectua depăşiri. Dacă o maşină mai rapidă ajunge din urmă o maşină mai lentă pe un astfel de segment, maşina rapidă va efectua o depăşire. Depăşirea are loc instantaneu, fără ca maşinile implicate să îşi schimbe vitezele. Depăşirile se pot efectua inclusiv în capetele unui segment cu linie întreruptă.
• Segmente cu linie continuă, pe care nu se pot efectua depăşiri. Dacă o maşină mai rapidă ajunge din urmă o maşină mai lentă pe un astfel de segment, maşina rapidă va încetini instantaneu astfel încât va avea aceeaşi viteză ca maşina lentă. Până la finalul segmentului, cele două maşini îşi vor continua drumul concomitent, având aceeaşi poziţie şi aceeaşi viteză. În cazul în care urmează un segment cu linie întreruptă, maşina rapidă va efectua depăşirea în primul punct al segmentului şi va reveni instantaneu la viteza iniţială.

Se garantează că toate întâlnirile dintre oricare două maşini vor avea loc la poziţii întregi.

Să se determine pentru fiecare din cele N+M maşini numărul de secunde necesare pentru a ajunge la destinaţie.

Date de intrare

Fişierul de intrare cars.in conţine pe prima linie valorile întregi N, M, K, L, A şi B.
Următoarea linie conţine N valori întregi separate prin spaţii, reprezentând poziţiile celor N maşini rapide, în ordine crescătoare.
Următoarea linie conţine M valori întregi separate prin spaţii, reprezentând poziţiile celor M maşini lente, în ordine crescătoare.
Fiecare din următoarele K linii conţine câte o pereche de numere întregi l_i r_i, reprezentând capetele unui segment de drum cu linie continuă. Segmentele nu se suprapun şi nu au capete comune. Orice punct al autostrăzii care nu face parte dintr-un segment cu linie continuă, face parte dintr-un segment cu linie întreruptă.

Date de ieşire

Fişierul de ieşire cars.out trebuie să conţină N+M valori reale, fiecare pe o linie nouă. Fiecare din primele N valori reprezintă durata călătoriei unei maşini rapide, în aceeaşi ordine ca în datele de intrare. Fiecare din următoarele M valori reprezintă durata călătoriei unei maşini lente, în aceeaşi ordine ca în datele de intrare.

Restricţii

• 1 ≤ N, M ≤ 20 000
• 1 ≤ K ≤ 100
• N + M < L ≤ 1 000 000 000
• 1 ≤ B < A ≤ 1 000
• 0 ≤ poziţia oricărei maşini < L
• 0 ≤ l₁ < r₁ < … < l_i < r_i < … l_k < r_k ≤ L
• Nu există maşini care pornesc de la aceeaşi poziţie.
• Timpul fiecărei maşini va fi considerat corect dacă diferă prin cel mult 10^-4 de răspunsul corect.
• Pentru unele teste în valoare de 5 puncte, N = M = 1.
• Pentru alte teste în valoare de 5 puncte, K = 1, l₁ = 0, r₁ = L.
• Pentru alte teste în valoare de 10 puncte, N, M ≤ 100, L ≤ 1 000.
• Pentru alte teste în valoare de 30 de puncte, N, M ≤ 1 000, L ≤ 500 000.
• Problema va fi evaluată pe teste în valoare de 90 de puncte.
• Exemplul va reprezenta teste în valoare de 10 puncte "din oficiu".
• Admin update: A se considera ca daca o masina rapida prinde din urma o masina lenta fix la inceputul unui segment cu linie continua, nu o poate depasi atunci

Exemplu

Explicaţie

Există o singură maşină rapidă şi o singură maşină lentă. Maşina rapidă porneşte de la poziţia 18 şi are viteza egală cu 12 m/s. Maşina lentă porneşte de la poziţia 25 şi are viteza egală cu 8 m/s.
Cele două segmente de drum cu linie continuă se desfăşoară pe intervalele (0, 20) şi (25, 50). Implicit, segmentele cu linie întreruptă se desfăşoară pe intervalele [20, 25] şi [50, 100].
Maşinile se întâlnesc la poziţia 39 (după 1.75 secunde), într-un punct de pe un segment cu linie continuă. Ca urmare, vor continua drumul împreună cu viteza de 8 m/s până la poziţia 50, unde începe un segment cu linie întreruptă.
În acest punct, maşina rapidă o depăşeşte instantaneu pe cea lentă, şi revine la viteza iniţială de 12 m/s. Ajunge la destinaţie după 7.291667 secunde de la începutul călătoriei.
Maşina lentă ajunge la destinaţie după 9.375 secunde de la începutul călătoriei.

Cum se trimit solutii?