Programmeringsolympiadens final 2018

Start

2018-02-04 08:00 UTC

Programmeringsolympiadens final 2018

End

2018-02-04 13:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -649 days 11:03:10

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Vilse i tidtabellen

Rakso är på semester i Duln för att titta på dyk-makron. Hon står vid en busshållplats och ska åka till sitt hotell "de nio". Det brukar alltid regna i Duln men idag är det isande kallt.

I glädjen att vara på semester, långt borta från sitt hem i den bedrövliga staden Stomholck, har Rakso totalt tappat tidsuppfattningen – hon vet inte vad klockan är. När hon tar upp sin jättesmarta fickdator för att ta reda på saken dör den – det är för kallt ute för att den ska fungera!

Men Rakso ger inte upp. Hon bestämmer sig för att ta reda på vad klockan är ändå. Till sin hjälp har hon:

  1. En tidtabell på väggen. Den visar vid vilka tider en buss anländer till hållplatsen hon står vid. Samma tidtabell gäller för alla dagar, och enbart en busslinje passerar stationen.

  2. En display som visar hur snart de kommande $N$ bussarna anländer till hållplatsen.

Bussar kommer alltid exakt när de lovar (detta är ju inte Stomholck), och anländer bara vid hela sekunder. Just nu när Rakso observerar tidtabellerna och displayen är det också vid en hel sekund. Om en buss anländer precis just nu kommer den synas på displayen med värde $0$.

Kan du hjälpa Rakso att skriva ett program som svarar på vad klockan är? Om det finns flera möjliga svar, så skriv ut alla. Om det inte finns någon giltig lösning (d.v.s. displayen måste visa fel), skriv ut "fel".

(Baserat på en verklig händelse. Rakso heter egentligen något annat.)

Indata

Den första raden innehåller två heltal $N$ och $M$ ($1 \leq N \leq 10^6$ , $1 \leq M \leq 3\, 000$). Den andra raden innehåller $N$ tal: tiderna $t_ i$ till nästkommande bussar som visas på displayen, i sekunder ($0 \le t_ i \le 10^9$). Dessa garanteras komma i stigande ordning, och inga tider är samma.

De följande $M$ raderna innehåller tiderna i tidtabellen i stigande ordning, på formatet hh:mm:ss (mellan 00:00:00 och 23:59:59). Tidtabellen kommer inte att innehålla några upprepade tider.

Utdata

Skriv ut en enda rad: möjligheterna för vad klockan kan vara, separerade med mellanslag. Tiderna ska vara sorterade i ökande ordning, och formateras på samma sätt som i indata.

Om det inte finns någon möjlighet alls för vad klockan kan vara, skriv ut "fel" (utan citattecken).

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

1

28

$N = 3$, $3 \le M \le 10$, ingen hänsyn behöver tas till att tolvslaget kan passeras

2

35

$3 \le N \le M \le 1000$

3

37

Inga ytterligare begränsningar

Sample Input 1 Sample Output 1
3 4
17559 19562 27399
04:57:18
05:30:41
07:41:18
08:36:03
00:04:39
Sample Input 2 Sample Output 2
2 3
1 2
00:00:02
00:00:03
00:00:04
00:00:01
Sample Input 3 Sample Output 3
4 3
2 28802 57602 86402
00:00:01
08:00:01
16:00:01
07:59:59 15:59:59 23:59:59
Sample Input 4 Sample Output 4
2 1
0 172800
01:23:45
fel