A och B, som har valts ut som Japans representanter till Internationella informatikolympiaden, har bestämt sig för att spela "Budbärarspelet" med direktör K från Japanska kommittén för Internationella informatikolympiaden för att förbättra sin förmåga att bearbeta information. Reglerna för detta spel förklaras nedan.

A och B är isolerade i rum som visas i figuren. Även om det finns interntelefoner i rummen hos A, B och direktör K, kan endast direktör K ringa ett samtal. Andra kommunikationsmedel är avskurna, och A och B får inte lämna sina rum om de inte blir tillsagda.

A:s rum | Lång korridor | Direktör K:s rum | Lång korridor | B:s rum

I början av spelet berättar direktör K ett positivt heltal $X$ för A via telefon. Målet med spelet är att A korrekt ska förmedla värdet på $X$ till B utan direkt kommunikation mellan dem.

I direktör K:s rum finns ett $4 \times 4$-rutnät. Låt $(i, j)$ representera rutan på den $i$-te raden och den $j$-te kolumnen ($1 \le i \le 4, 1 \le j \le 4$). Ruta $(1, 1)$ är det övre vänstra hörnet, $(1, 4)$ är det övre högra hörnet, $(4, 1)$ är det nedre vänstra hörnet och $(4, 4)$ är det nedre högra hörnet. I början av spelet placeras en pjäs i en av rutorna. Därefter kommer direktör K inte att ändra vilken ruta pjäsen står i.

Från och med nu ringer direktör K upprepade gånger in antingen A eller B till rummet per telefon. Varje gång A eller B kommer till direktör K:s rum måste de flytta pjäsen till en intilliggande ruta (upp, ner, vänster eller höger). Efter att ha flyttat pjäsen återvänder A eller B till sitt eget rum. Om B känner till värdet på $X$ när B kommer till direktör K:s rum kan B svara det till direktör K istället för att flytta pjäsen. Om rätt värde på $X$ ges som svar är det ett korrekt svar; annars är det ett felaktigt svar.

Tidpunkterna då direktör K kallar in A eller B till rummet är oregelbundna, och A och B vet inte i vilken ordning direktör K kallar in dem till rummet. Direktör K bestämmer dock i vilken ordning de två ska kallas in i början av spelet, och det garanteras att direktör K inte kommer att kalla in vare sig A eller B mer än 100 gånger i rad. Om B inte har svarat värdet på $X$ efter att A eller B har återvänt till sitt rum efter att direktör K har kallat in A och B totalt 10,000 gånger, slutar spelet med ett felaktigt svar.

Uppgift

Implementera strategierna för A och B, och skapa ett program som kan svara rätt i "Budbärarspelet" som beskrivs ovan.

Implementeringsdetaljer

Du måste skicka in två filer i samma programmeringsspråk.

Den första filen heter playerA.c eller playerA.cpp. Denna fil implementerar A:s strategi och måste implementera följande rutiner:

• void InitA(int T, int X) Denna rutin anropas exakt en gång i början. Argumentet T är deluppgiftsnumret. Argumentet X är det positiva heltal som A måste förmedla till B.

• int GameA(int I, int J) Denna rutin anropas när A kommer till direktör K:s rum. Argumenten I och J är heltalen som representerar rutan $(I, J)$ där pjäsen befinner sig när A anländer till direktör K:s rum, och de uppfyller $1 \le I \le 4$ och $1 \le J \le 4$. Denna rutin måste returnera ett av heltalen $-1, -2, -3, -4$. Om något annat värde returneras bedöms det som Wrong Answer [1] och programkörningen avbryts. Dessa representerar följande handlingar av A:

  • $-1$: Flytta pjäsen till rutan ovanför $(I - 1, J)$.
  • $-2$: Flytta pjäsen till rutan nedanför $(I + 1, J)$.
  • $-3$: Flytta pjäsen till rutan till vänster $(I, J - 1)$.
  • $-4$: Flytta pjäsen till rutan till höger $(I, J + 1)$. Om ett drag som flyttar pjäsen utanför brädet anges bedöms det som Wrong Answer [2] och programkörningen avbryts.

Den andra filen heter playerB.c eller playerB.cpp. Denna fil implementerar B:s strategi och måste implementera följande rutiner:

• void InitB(int T) Denna rutin anropas exakt en gång i början. Argumentet T är deluppgiftsnumret.

• int GameB(int I, int J) Denna rutin anropas när B kommer till direktör K:s rum. Argumenten I och J är heltalen som representerar rutan $(I, J)$ där pjäsen befinner sig när B anländer till direktör K:s rum, och de uppfyller $1 \le I \le 4$ och $1 \le J \le 4$. Denna rutin måste returnera ett av heltalen $-1, -2, -3, -4$, eller ett positivt heltal $Y$. Om något annat värde returneras bedöms det som Wrong Answer [3] och programkörningen avbryts. Dessa representerar följande handlingar av B:

  • $-1$: Flytta pjäsen till rutan ovanför $(I - 1, J)$.
  • $-2$: Flytta pjäsen till rutan nedanför $(I + 1, J)$.
  • $-3$: Flytta pjäsen till rutan till vänster $(I, J - 1)$.
  • $-4$: Flytta pjäsen till rutan till höger $(I, J + 1)$. Om ett drag som flyttar pjäsen utanför brädet anges bedöms det som Wrong Answer [4] och programkörningen avbryts.
  • Positivt heltal $Y$: Svara direktör K att värdet på $X$ är $Y$. Om $X = Y$ är det ett korrekt svar; annars bedöms det som Wrong Answer [5] och programkörningen avbryts.

Rutinerna GameA och GameB kommer inte att anropas mer än 100 gånger i rad för någondera. Vidare, om GameB inte har returnerat ett positivt heltal när GameA och GameB har anropats totalt 10,000 gånger, bedöms det som Wrong Answer [6] och programkörningen avbryts.

Det står dig fritt att implementera andra rutiner eller deklarera globala variabler för internt bruk. Eftersom de två inskickade programmen länkas samman med bedömarprogrammet till en enda körbar fil måste du dock deklarera alla globala variabler och interna rutiner i varje fil som static för att undvika konflikter med andra filer. Vid bedömningen körs detta program som två separata processer, en för A och en för B, så globala variabler kan inte delas mellan A-sidan och B-sidan. Din inlämning får inte interagera med standard in/ut eller några andra filer på något sätt.

Indata

Exempelbedömaren läser följande indata från standard in:

• Den första raden innehåller heltalen $T, X, I_0, J_0$ separerade med mellanslag, vilka representerar deluppgiftsnumret $T$, heltalet $X$ som A måste förmedla till B, samt pjäsens startposition $(I_0, J_0)$ i början av spelet.
• Den andra raden innehåller en sträng med längd exakt 10,000 som består av två typer av tecken, 'A' och 'B'. Om det $k$-te tecknet ($1 \le k \le 10,000$) är 'A' eller 'B' betyder det att den $k$-te rutinen som anropas efter att InitA och InitB har anropats är GameA respektive GameB.

Utdata

Om programmet avslutas normalt skriver exempelbedömaren ut följande information till standard ut på en rad:

• Om det är rätt skrivs "Accepted" ut (citattecken skrivs inte ut i verkligheten; detsamma gäller nedan).
• Om det är fel skrivs typen av felaktigt svar ut som "Wrong Answer [1]" baserat på numren i avsnittet "Implementeringsdetaljer". Vidare, för Wrong Answer [5], skrivs det korrekta värdet på $X$ och det positiva heltalet $Y$ som returnerades av rutinen GameB ut som Wrong Answer [5] : X = 2, Y = 3.

Begränsningar

All indata uppfyller följande villkor:

• $1 \le X \le 1,000,000,000$.

Deluppgifter

Deluppgift 1 [20 poäng]

• Uppfyller $T = 1$.
• A kallas till direktör K:s rum först, och A och B kallas växelvis till direktör K:s rum. Det vill säga, efter att InitA och InitB har anropats, anropas rutinerna i ordningen GameA, GameB, GameA, GameB, ...

Deluppgift 2 [20 poäng]

• Uppfyller $T = 2$.
• Pjäsens position i början av spelet är $(I_0, J_0) = (1, 1)$. Det vill säga, efter att InitA och InitB har anropats, anropas först rutinen GameA eller GameB med $I = 1, J = 1$ som argument.

Deluppgift 3 [60 poäng]

• Uppfyller $T = 3$.

Anmärkning

Ett exempel på indata som läses av exempelbedömaren och ett exempel på motsvarande rutinanrop visas nedan.

Observera att detta exempel inte nödvändigtvis beskriver en meningsfull interaktion.