Na proplanku se nalazi N mrava i M mravinjaka. Pozicija svakog mrava i mravinjaka se može predstaviti tačkom na X-osi.
U jednom trenutku, naišao je mravojed Žika. Mravi su se uplašili, i svaki mrav je krenuo ka svom najbližem mravinjaku. Pomozite mravima tako što ćete odrediti koliko će vremena biti potrebno da se svi mravi sakriju, ako se jedan mrav pomeri za jedan podeok na X-osi za jednu sekundu. Mrave takođe zanima koliko će im biti potrebno vremena da se sakriju ako se na livadi pojave još neki mravi.

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se prirodni brojevi ~N~ i ~M~ koji označava broj mrava i mravinjaka.
U drugoj liniji standardnog ulaza nalazi se ~N~ prirodnih brojeva sortiranih neopadajuće koji predstavljaju koordinate mrava.
U trećoj liniji standardnog ulaza nalazi se ~M~ prirodnih brojava sortiranih neopadajuće koji predstavljaju koordinate mravinjaka.
U četvrtoj liniji standardnog ulaza nalazi se broj ~T~ - koliko će se još mrava pojaviti na livadi.
U narednih ~T~ linjija nalazi se po jedan ceo broj koji predstavlja koordinatu novog mrava.

Opis izlaza

Potrebno je ispisati ~T+1~ brojeva svaki u novoj liniji.
U prvoj liniji ispisati koliko će sekundi mravima biti potrebno da se sakriju pre nego što se pojave novi mravi.
Zatim u narednih ~T~ linija ispisati koliko će im vremena biti potrebno nakon što se pojavi svaki od novih mrava.

Primer 1

Ulaz

5 4
1 3 15 23 35
2 7 20 47
0

Izlaz

12

Primer 2

Ulaz

5 4
1 3 15 23 35
2 7 20 47
2
10
34

Izlaz

12
12
13

Objašnjenje test primera:

U prvom test primeru mrav na poziciji 35 će poslednji ući u mravinjak i za to mu je potrebno 12 sekundi.
U drugom test primeru kada se pojavi mrav na poziciji 10 on stiže do mravinjaka za 3 sekunde, pa je potrebno vreme idalje 12, dok će mravu na poziciji 34 biti potrebno 13 sekundi.

Ograničenja i podzadaci

~A_i~ - koordinate mrava
~B_i~ - koordinate mravinjaka
~1 \le A_i, B_i \le 10^9~

Test primeri su podeljeni u 3 disjunktne grupe:

• U test primerima vrednim 30 poena: ~N,M \le 1000, T=0~
  
• U test primerima vrednim 30 poena: ~N,M \le 100000, T=0~
  
• U test primerima vrednim 40 poena: ~N,M,T \le 100000~