Problem C
Veður - Vegakerfi

Mynd fengin af vegagerdin.is

Vegagerðin hefur samband við þig aftur varðandi annað verkefni. Nú eru margir Íslendingar að ferðast um landið, þrátt fyrir slæma veðrið. Því koma oft inn fyrirspurnir til Vegagerðarinnar, til dæmis, hvort hægt sé að komast frá Kópavogi til Egilsstaða við núverandi aðstæður.

Vegagerðin gefur þér lýsingu á vegakerfi Íslands þar sem öllum vegum landsins er lýst. Sérhverjum vegi er lýst með tveimur endapunktum og vindstigsþröskuldi. Ef vindhraðinn er minni en eða jafn vindstigsþröskuldi vegarins þá er vegurinn opinn og þá má ferðast um veginn, annars er vegurinn lokaður.

Nú þarft þú að skrifa forrit sem getur svarað þessum fyrispurnum. Fyrirspurnir innihalda upplýsingar um upphafsstaðsetningu, endastaðsetningu og vindhraðann á landinu. Svarið skal vera Jebb ef til er leið frá upphafsstaðsetningu til endastaðsetningar sem notar einungis opna vegi. Annars skal svarið vera Neibb.

Inntak

Fyrsta línan í inntakinu inniheldur þrjár heiltölur $n$ ($1 \leq n \leq 10^5$), fjöldi gatnamóta, $m$ ($0 \leq m \leq 10^5)$, fjöldi vega, og $q$ ($1 \leq q \leq 10^5)$, fjöldi fyrirspurna.

Næst fylgja $m$ línur, þar sem $i$-ta línan lýsir vegi númer $i$. Hver lína inniheldur þrjár heiltölur $u_ i$ ($1 \leq u_ i \leq n$) og $v_ i$ ($1 \leq v_ i \leq n$), endapunkta vegarins, og $t_ i$ ($0 \leq t_ i \leq 10^9$), vindstigsþröskuld vegarins.

Að lokum koma $q$ línur, þar sem $j$-ta línan lýsir fyrirspurn númer $j$. Til að tryggja að fyrirspurnum sé svarað einni í einu þá eru þær dulkóðaðar. Hver lína inniheldur því þrjár dulkóðaðar heiltölur $a’_ j$, $b’_ j$ og $h’_ j$. Táknum fjölda fyrirspurna sem hafa verið svarað með Jebb upp að þessu með $x$. Til að fá rétt gildi á $a_ j, b_ j$ og $h_ j$ skal beita XOR aðgerðinni, táknuð með ${}^\wedge {}$ virkjanum í flestum forritunarmálum, og því er

• $a_ j = a’_ j {}^\wedge {} x$,

• $b_ j = b’_ j {}^\wedge {} x$,

• $h_ j = h’_ j {}^\wedge {} x$.

Hver fyrirspurn inniheldur því þrjár heiltölur $a_ j$ ($1 \leq a_ j \leq n$), upphafspunkt, $b_ j$ ($1 \leq b_ j \leq n)$, endapunkt og $h_ j$ ($0 \leq h_ j \leq 10^9$), vindhraðann.

Úttak

Fyrir hverja fyrirspurn skal svara annaðhvort Jebb, ef til er leið frá gefna byrjunarpunktinum til gefna endapunktsins sem hefur engan lokaðan veg, eða Neibb ef ekki er til leið.

Stigagjöf

4 4 2
1 2 7
2 3 5
3 4 4
4 1 3
2 4 6
1 4 4

Neibb
Jebb