I många delar av Ryssland snöar det under vintern. Det finns $N$ städer i Ryssland, numrerade från $0$ till $N-1$. Det finns $N-1$ vägar, numrerade från $0$ till $N-2$. Väg $i$ ($0 \le i \le N-2$) förbinder två olika städer $A_i$ och $B_i$ ($0 \le A_i < B_i \le N-1$) i båda riktningarna. Det är möjligt att resa mellan vilka två olika städer som helst i Ryssland genom att färdas längs någon följd av vägar.

Snöförhållandena på varje väg varierar från dag till dag. Under en given dag är varje väg antingen snöig eller inte snöig. Snöförhållandet på en väg ändras inte under loppet av en och samma dag.

Anya och Boris arbetar på det ryska transportdepartementet. Anya arbetar på avdelningen för väginformationshantering, och Boris arbetar på avdelningen som svarar på frågor från medborgare. En medborgares fråga lyder: "Vilket är det minsta antalet snöiga vägar jag måste passera för att resa från huvudstaden, stad 0, till en viss annan stad?" Boris svarar vanligtvis medborgarna efter att ha tagit emot en fråga och kommunicerat med Anya.

Nyligen hålls en världstävling i programmering i Ryssland under $Q$ dagar. Under tävlingen förväntas kommunikationslinjerna vara överbelastade, vilket gör det svårt för Anya och Boris att kommunicera direkt. Därför har Anya och Boris bestämt sig för att kommunicera på följande sätt:

• I början av varje dag tar Anya emot informationen om snöiga vägar för den dagen och skickar data till en reläserver.
• När Boris får en fråga från en medborgare besvarar han den genom att kommunicera med reläservern.

Det finns dock följande begränsningar för kommunikationen mellan Anya och Boris:

• Reläserverns kapacitet är $L = 1000$ bitar. Anya kan lagra högst $L$ bitar information i reläservern.
• Datan som lagras i reläservern initieras till enbart 0:or i början av varje dag.
• Boris kan läsa 1 specifik bit information genom att interagera med reläservern en gång.
• För att svara på en fråga kan Boris interagera med reläservern högst 20 gånger per fråga.

Du, en bekant till chefen för transportdepartementet, har blivit ombedd att ta fram en strategi för Anya och Boris.

Skriv ett program som implementerar en strategi för Anya och Boris som korrekt kan svara på medborgarnas frågor.

Implementeringsdetaljer

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

Den första filen heter Anya.c eller Anya.cpp. Denna fil implementerar Anyas strategi och måste implementera följande två rutiner. Programmet måste inkludera Anyalib.h.

• void InitAnya(int N, int A[], int B[]) Denna funktion anropas exakt en gång för varje testfall.

  • Argumentet N anger antalet städer.
  • Argumenten A[] och B[] är arrayer med längden $N-1$, som representerar informationen om vägförbindelserna. Elementen A[i] och B[i] ($0 \le i \le N-2$) är heltal som anger att väg $i$ förbinder städerna A[i] och B[i] i båda riktningarna, och uppfyller $0 \le A[i] < B[i] \le N-1$.

• void Anya(int C[]) Denna funktion anropas $Q$ gånger efter att InitAnya har anropats. Denna funktion motsvarar att Anya bestämmer bitsträngen som ska lagras i reläservern efter att informationen om snöiga vägar har uppdaterats i början av dagen.

  • Argumentet C[] är en array med längden $N-1$, som representerar informationen om snöiga vägar. Elementet C[i] ($0 \le i \le N-2$) är ett heltal 0 eller 1, där C[i] = 1 betyder att väg $i$ är snöig, och C[i] = 0 betyder att väg $i$ inte är snöig.

Inuti funktionen Anya kan du anropa följande funktion:

• void Save(int place, int bit) Denna funktion representerar operationen där Anya sparar en bit till reläservern.

  • Argumentet place anger platsen där biten ska skrivas. place måste vara ett heltal mellan $0$ och $L-1$ inklusive. Om ett värde utanför detta intervall anges bedöms det som Wrong Answer [1]. Vid varje anrop till funktionen Anya får du inte heller anropa denna funktion med samma place-argument mer än en gång. Om den anropas två gånger med samma argument bedöms det som Wrong Answer [2].
  • Argumentet bit är ett heltal som anger biten som ska skrivas, vilket måste vara 0 eller 1. Om något annat värde anges bedöms det som Wrong Answer [3].

Efter anropet till Save blir innehållet i den place-te biten på reläservern bit. Om ett anrop till Save bedöms som Wrong Answer avslutas programmet vid den tidpunkten.

Omedelbart innan funktionen Anya anropas initieras bitarna i reläservern alltid till enbart 0:or. Det vill säga, i slutet av funktionen Anya innehåller platser där ingen sparoperation utfördes av funktionen Save värdet 0.

Den andra filen heter Boris.c eller Boris.cpp. Denna fil implementerar Boris strategi och måste implementera följande två rutiner. Programmet måste inkludera Borislib.h.

• void InitBoris(int N, int A[], int B[]) Denna funktion anropas exakt en gång för varje testfall.

  • Argumentet N anger antalet städer.
  • Argumenten A[] och B[] är arrayer med längden $N-1$, som representerar informationen om vägförbindelserna. Elementen A[i] och B[i] ($0 \le i \le N-2$) är heltal som anger att väg $i$ förbinder städerna A[i] och B[i] i båda riktningarna, och uppfyller $0 \le A[i] < B[i] \le N-1$.

• int Boris(int city) Denna funktion anropas flera gånger efter att InitBoris har anropats. Denna funktion motsvarar Boris agerande som svar på en medborgares fråga.

  • Argumentet city representerar medborgarens fråga. city är ett heltal mellan $1$ och $N-1$ inklusive. Detta representerar att medborgaren frågar efter det minsta antalet snöiga vägar man måste passera för att resa från stad 0 till city.
  • Funktionen Boris måste returnera ett heltal mellan $0$ och $N-1$ inklusive, vilket är svaret på medborgarens fråga. Om ett heltal utanför detta intervall returneras bedöms det som Wrong Answer [4]. Om svaret är felaktigt bedöms det som Wrong Answer [7].

Inuti funktionen Boris kan du anropa följande funktion:

• int Ask(int place) Denna funktion representerar operationen där Boris läser en bit från reläservern.

  • Argumentet place anger platsen som biten ska läsas från. place måste vara ett heltal mellan $0$ och $L-1$ inklusive. Om ett värde utanför detta intervall anges bedöms det som Wrong Answer [5].

  Returvärdet från funktionen Ask är ett heltal som representerar innehållet i den place-te biten på reläservern, vilket är 0 eller 1. Dessutom kan funktionen Ask anropas högst 20 gånger vid varje anrop till funktionen Boris. Om den anropas mer än 20 gånger bedöms det som Wrong Answer [6].

Om ett anrop till Ask bedöms som Wrong Answer avslutas programmet vid den tidpunkten.

Begränsningar

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1 + \dots + D_Q \le 500$.
• Det är möjligt att resa mellan vilka två olika städer som helst genom att färdas längs någon följd av vägar.

Deluppgifter

1. (15 poäng) $N \le 20$.
2. (5 poäng) $N \le 100$.
3. (35 poäng) $A_i = i$ och $B_i = i + 1$ för alla $0 \le i \le N-2$.
4. (45 poäng) Inga ytterligare begränsningar.

Exempel

Indata 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Utdata 1

1 0 2
2

Förklaring

Exemplet ovan visar interaktionsflödet. Den första raden i indata är $N=5$. De följande 4 raderna definierar kanterna. Nästa rad är $Q=2$. De följande raderna beskriver de snöiga vägarna och frågorna för varje dag. Utdata visar svaren som Boris ger på frågorna för varje dag.