Problem E
Vvvvvv

Plattformspel är en gammal dataspelgenre där du rör dig på plattformar som hänger i luften. Vvvvvv är en sorts plattformspel där du inte kan hoppa, men istället kan växla mellan vanlig gravitation, som gör att du faller nedåt, och antigravitation, som gör att du faller uppåt. Förutom gravitationsomkopplaren (G) så finns bara två knappar i spelet, gå till höger (H) och gå till vänster (V).

I den här uppgiften ska du hitta en sekvens av knapptryckningar som tar dig genom en labyrintliknande uppsättning av plattformar och väggar, från en startposition till en slutposition. För att få full poäng ska sekvensen dessutom vara så kort som möjligt.

Figure 1: Vägen som ges av knapptryckningssekvensen i det andra exemplet.

Input

Den första raden i indatan innehåller tre heltal $W$, $H$, och $N$: spelplanens bredd, spelplanens höjd samt antalet linjesegment. Därefter följer $N$ rader med fyra heltal $x_1$, $y_1$, $x_2$, $y_2$ på varje rad, där $0 \le x_1,x_2 \le W$ och $0 \le y_1,y_2 \le H$. Varje rad beskriver ett linjesegment med ändpunkterna ($x_1, y_1$) samt ($x_2, y_2$). Varje linjesegment är antingen vågrätt eller lodrätt, d.v.s. antingen gäller $y_1=y_2$ eller $x_1=x_2$. Heltalskoordinaterna kan sägas dela in den rektangulära spelplanen i ett rutnät, i vilket knappen V förflyttar dig en ruta åt vänster medan H förflyttar dig en ruta åt höger. Om du inte står på en plattform efter förflyttningen så faller du (uppåt eller nedåt) till närmsta plattform, och det finns ingen möjlighet att röra dig i sidled under fallets gång. Om du faller eller går ut ur spelplanen förlorar du spelet. Detsamma gäller om du försöker gå genom en vägg.

Startpositionen är rutan i nedre vänstra hörnet närmast punkten $(0,0)$ med gravitationen riktad neråt. Slutpositionen är rutan i övre högra hörnet, närmast punkten $(W,H)$. Det kommer alltid finnas ett linjesegment under startpositionen samt över slutpositionen.

Output

Om det finns en lösning ska programmet skriva ut en sträng innehållande en bokstav för varje knapptryckning, valda bland H, V och G. Sekvensen ska ta dig från startpositionen till slutpositionen och måste vara kortare än $10\, 000$ tecken. Du kan anlända till slutpositionen med valfri riktning på gravitationen, men du måste stå stilla, alltså ha "fallit färdigt" (se tredje exemplet nedan).

Om det inte finns en lösning ska programmet skriva ut strängen "Inte" (utan citationstecken).

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.

4 5 9
2 5 4 5
4 5 4 1
4 4 3 4
3 0 4 0
0 0 2 0
0 3 2 3
2 2 2 3
1 1 1 2
1 1 3 1

HGHHVH

10 9 22
0 0 2 0
2 0 2 2
1 1 1 4
0 3 1 3
1 5 4 5
3 2 3 3
3 4 3 5
4 5 4 6
4 4 4 3
4 3 6 3
6 1 8 1
5 4 7 4
7 4 7 3
7 3 8 3
8 3 8 5
8 5 7 5
6 5 6 7
6 7 4 7
0 8 5 8
8 8 8 6
8 6 10 6
7 9 10 9

HGVHHHHGHHVVHHHGHVHH

2 1 2
0 0 1 0
1 1 2 1

Inte