Í mörgum hlutum Rússlands snjóar á veturna. Það eru $N$ borgir í Rússlandi, númeraðar frá $0$ til $N-1$. Það eru $N-1$ vegir, númeraðir frá $0$ til $N-2$. Vegur $i$ ($0 \le i \le N-2$) tengir tvær ólíkar borgir $A_i$ og $B_i$ ($0 \le A_i < B_i \le N-1$) í báðar áttir. Hægt er að ferðast á milli hvaða tveggja ólíkra borga sem er í Rússlandi með því að fara eftir einhverri runu af vegum.

Snjóalög á hverjum vegi breytast frá degi til dags. Á hverjum gefnum degi er hver vegur annaðhvort snæþakinn eða ekki snæþakinn. Snjóalög á vegi breytast ekki á meðan á einum og sama deginum stendur.

Anya og Boris vinna hjá rússneska samgönguráðuneytinu. Anya vinnur í upplýsingadeild vegamála og Boris vinnur í deildinni sem svarar spurningum frá borgurum. Spurning borgara er: „Hver er lágmarksfjöldi snæþakinna vega sem ég þarf að fara um til að ferðast frá höfuðborginni, borg 0, til tiltekinnar annarrar borgar?“ Boris svarar venjulega borgurum eftir að hafa fengið spurningu og haft samband við Önyu.

Nýlega er haldin heimsmeistarakeppni í forritun í Rússlandi í $Q$ daga. Á meðan á keppninni stendur er búist við miklu álagi á fjarskiptalínum, sem gerir Önyu og Boris erfitt fyrir að eiga í beinum samskiptum. Þess vegna hafa Anya og Boris ákveðið að eiga samskipti á eftirfarandi hátt:

• Í upphafi hvers dags fær Anya upplýsingar um snæþakta vegi fyrir þann dag og sendir gögn á miðlara (relay server).
• Þegar Boris fær spurningu frá borgara svarar hann henni með því að eiga samskipti við miðlarann.

Hins vegar eru eftirfarandi takmarkanir á samskiptum milli Önyu og Boris:

• Rýmd miðlarans er $L = 1000$ bitar. Anya getur geymt í mesta lagi $L$ bita af upplýsingum á miðlaranum.
• Gögnin sem geymd eru á miðlaranum eru frumstillt á eintóm 0 í upphafi hvers dags.
• Boris getur lesið 1 tiltekinn bita af upplýsingum með því að eiga samskipti við miðlarann einu sinni.
• Til að svara spurningu getur Boris átt samskipti við miðlarann í mesta lagi 20 sinnum fyrir hverja spurningu.

Þú, kunningi forstjóra samgönguráðuneytisins, hefur verið beðinn um að finna upp áætlun fyrir Önyu og Boris.

Skrifið forrit sem útfærir áætlun fyrir Önyu og Boris sem getur svarað spurningum borgaranna rétt.

Útfærsluatriði

Þú verður að skila inn tveimur skrám í sama forritunarmáli.

Fyrri skráin heitir Anya.c eða Anya.cpp. Þessi skrá útfærir áætlun Önyu og verður að útfæra eftirfarandi tvö föll. Forritið verður að innihalda Anyalib.h.

• void InitAnya(int N, int A[], int B[]) Kallað er á þetta fall nákvæmlega einu sinni fyrir hvert prófunartilvik.

  • Viðfangið N táknar fjölda borga.
  • Viðföngin A[] og B[] eru fylki af lengd $N-1$, sem tákna upplýsingar um vegatengingar. Stökin A[i] og B[i] ($0 \le i \le N-2$) eru heiltölur sem tákna að vegur $i$ tengi borgir A[i] og B[i] í báðar áttir, og uppfylla $0 \le A[i] < B[i] \le N-1$.

• void Anya(int C[]) Kallað er á þetta fall $Q$ sinnum eftir að kallað er á InitAnya. Þetta fall samsvarar því að Anya ákveði bitastrenginn sem á að geyma á miðlaranum eftir að upplýsingar um snæþakta vegi hafa verið uppfærðar í upphafi dags.

  • Viðfangið C[] er fylki af lengd $N-1$, sem táknar upplýsingar um snæþakta vegi. Stakið C[i] ($0 \le i \le N-2$) er heiltala, 0 eða 1, þar sem C[i] = 1 þýðir að vegur $i$ sé snæþakinn, og C[i] = 0 þýðir að vegur $i$ sé ekki snæþakinn.

Innan fallsins Anya geturðu kallað á eftirfarandi fall:

• void Save(int place, int bit) Þetta fall táknar þá aðgerð þegar Anya vistar bita á miðlarann.

  • Viðfangið place táknar staðsetninguna þar sem á að skrifa bitann. place verður að vera heiltala á bilinu $0$ til $L-1$ (bæði meðtalin). Ef gildi utan þessa bils er tilgreint er það dæmt sem Wrong Answer [1]. Einnig, í hverju kalli á fallið Anya, máttu ekki kalla á þetta fall með sama place viðfanginu oftar en einu sinni. Ef kallað er tvisvar með sama viðfanginu er það dæmt sem Wrong Answer [2].
  • Viðfangið bit er heiltala sem táknar bitann sem á að skrifa, sem verður að vera 0 eða 1. Ef eitthvert annað gildi er tilgreint er það dæmt sem Wrong Answer [3].

Eftir kallið á Save verður innihald place-ta bitans á miðlaranum bit. Ef kall á Save er dæmt sem Wrong Answer hættir forritið keyrslu á þeim tímapunkti.

Rétt áður en kallað er á fallið Anya eru bitarnir á miðlaranum alltaf frumstilltir á eintóm 0. Það er að segja, í lok fallsins Anya innihalda staðsetningar þar sem engin vistunaraðgerð var framkvæmd með fallinu Save gildið 0.

Seinni skráin heitir Boris.c eða Boris.cpp. Þessi skrá útfærir áætlun Boris og verður að útfæra eftirfarandi tvö föll. Forritið verður að innihalda Borislib.h.

• void InitBoris(int N, int A[], int B[]) Kallað er á þetta fall nákvæmlega einu sinni fyrir hvert prófunartilvik.

  • Viðfangið N táknar fjölda borga.
  • Viðföngin A[] og B[] eru fylki af lengd $N-1$, sem tákna upplýsingar um vegatengingar. Stökin A[i] og B[i] ($0 \le i \le N-2$) eru heiltölur sem tákna að vegur $i$ tengi borgir A[i] og B[i] í báðar áttir, og uppfylla $0 \le A[i] < B[i] \le N-1$.

• int Boris(int city) Kallað er á þetta fall nokkrum sinnum eftir að kallað er á InitBoris. Þetta fall samsvarar aðgerð Boris sem svar við spurningu borgara.

  • Viðfangið city táknar spurningu borgarans. city er heiltala á bilinu $1$ til $N-1$ (bæði meðtalin). Þetta táknar að borgarinn spyrji um lágmarksfjölda snæþakinna vega sem hann þarf að fara um til að ferðast frá borg 0 til city.
  • Fallið Boris verður að skila heiltölu á bilinu $0$ til $N-1$ (bæði meðtalin), sem er svarið við spurningu borgarans. Ef heiltölu utan þessa bils er skilað er það dæmt sem Wrong Answer [4]. Ef svarið er rangt er það dæmt sem Wrong Answer [7].

Innan fallsins Boris geturðu kallað á eftirfarandi fall:

• int Ask(int place) Þetta fall táknar þá aðgerð þegar Boris les bita af miðlaranum.

  • Viðfangið place táknar staðsetninguna þaðan sem á að lesa bitann. place verður að vera heiltala á bilinu $0$ til $L-1$ (bæði meðtalin). Ef gildi utan þessa bils er tilgreint er það dæmt sem Wrong Answer [5].

  Skilagildi fallsins Ask er heiltala sem táknar innihald place-ta bitans á miðlaranum, sem er 0 eða 1. Einnig má kalla á fallið Ask í mesta lagi 20 sinnum í hverju kalli á fallið Boris. Ef kallað er á það oftar en 20 sinnum er það dæmt sem Wrong Answer [6].

Ef kall á Ask er dæmt sem Wrong Answer hættir forritið keyrslu á þeim tímapunkti.

Takmarkanir

• $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$.
• Hægt er að ferðast á milli hvaða tveggja ólíkra borga sem er með því að fara eftir einhverri runu af vegum.

Undirverkefni

1. (15 stig) $N \le 20$.
2. (5 stig) $N \le 100$.
3. (35 stig) $A_i = i$ og $B_i = i + 1$ fyrir öll $0 \le i \le N-2$.
4. (45 stig) Engar frekari takmarkanir.

Dæmi

Inntak 1

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

Úttak 1

1 0 2
2

Athugasemd

Dæmið hér að ofan sýnir samskiptaferlið. Fyrsta línan í inntakinu er $N=5$. Næstu 4 línur skilgreina leggina. Næsta lína er $Q=2$. Línurnar þar á eftir lýsa snæþöktu vegunum og fyrirspurnunum fyrir hvern dag. Úttakið sýnir svörin sem Boris gefur við fyrirspurnunum á hverjum degi.