Ресейдің көптеген аймақтарында қыста қар жауады. Ресейде $0$-ден $N-1$-ге дейін нөмірленген $N$ қала бар. Сондай-ақ $0$-ден $N-2$-ге дейін нөмірленген $N-1$ жол бар. $i$ жолы ($0 \le i \le N-2$) әртүрлі екі $A_i$ және $B_i$ ($0 \le A_i < B_i \le N-1$) қалаларын екі бағытта да байланыстырады. Ресейдегі кез келген екі түрлі қаланың арасында қандай да бір жолдар тізбегі арқылы жүріп өтуге болады.

Әр жолдың қар басу жағдайы күн сайын өзгеріп отырады. Кез келген күні әрбір жол не қар басқан, не қар баспаған күйде болады. Бір күннің ішінде жолдың қар басу жағдайы өзгермейді.

Аня мен Борис Ресей Көлік министрлігінде жұмыс істейді. Аня жол ақпаратын басқару бөлімінде, ал Борис азаматтардың сұрақтарына жауап беретін бөлімде жұмыс істейді. Азаматтың сұрағы мынадай: «Астанадан, яғни 0-қаладан белгілі бір басқа қалаға бару үшін кем дегенде қанша қар басқан жолмен жүріп өтуім керек?» Әдетте Борис сұрақты қабылдап, Анямен хабарласқаннан кейін азаматтарға жауап береді.

Жақында Ресейде $Q$ күн бойы программалаудан әлем чемпионаты өткізілуде. Жарыс кезінде байланыс желілері шамадан тыс жүктеліп, Аня мен Бористің тікелей байланысуы қиындайды деп күтілуде. Сондықтан Аня мен Борис келесі тәсілмен байланысуды ұйғарды:

• Әр күннің басында Аня сол күнгі қар басқан жолдар туралы ақпаратты алып, деректерді ретранслятор серверіне (relay server) жібереді.
• Борис азаматтан сұрақ алған кезде ретранслятор серверімен байланысу арқылы оған жауап береді.

Алайда Аня мен Бористің арасындағы байланысқа келесідей шектеулер қойылған:

• Ретранслятор серверінің сыйымдылығы — $L = 1000$ бит. Аня ретранслятор серверінде ең көбі $L$ бит ақпарат сақтай алады.
• Ретранслятор серверінде сақталған деректер әр күннің басында түгелдей 0-ге теңестіріліп инициализацияланады.
• Борис ретранслятор серверімен бір рет әрекеттесу арқылы көрсетілген 1 бит ақпаратты оқи алады.
• Сұраққа жауап беру үшін Борис әр сұраққа ретранслятор серверімен ең көбі 20 рет әрекеттесе алады.

Көлік министрлігі директорының танысы ретінде сізден Аня мен Бориске арналған стратегия ойлап табу сұралды.

Азаматтардың сұрақтарына дұрыс жауап бере алатын Аня мен Бористің стратегиясын іске асыратын программа жазыңыз.

Іске асыру мәліметтері

Сіз бір программалау тілінде екі файл жіберуіңіз керек.

Бірінші файл Anya.c немесе Anya.cpp деп аталады. Бұл файл Аняның стратегиясын іске асырады және келесі екі процедураны іске асыруы керек. Программа Anyalib.h файлын қосуы тиіс.

• void InitAnya(int N, int A[], int B[]) Бұл функция әр тест жағдайы үшін дәл бір рет шақырылады.

  • N аргументі қалалар санын білдіреді.
  • A[] және B[] аргументтері — жолдардың байланысу ақпаратын білдіретін ұзындығы $N-1$ болатын массивтер. A[i] және B[i] элементтері ($0 \le i \le N-2$) $i$ жолы A[i] мен B[i] қалаларын екі бағытта да байланыстыратынын білдіретін бүтін сандар, мұндағы $0 \le A[i] < B[i] \le N-1$.

• void Anya(int C[]) Бұл функция InitAnya шақырылғаннан кейін $Q$ рет шақырылады. Бұл функция күннің басында қар басқан жолдар туралы ақпарат жаңартылғаннан кейін Аняның ретранслятор серверінде сақталатын биттер тізбегін шешуіне сәйкес келеді.

  • C[] аргументі — қар басқан жолдар туралы ақпаратты білдіретін ұзындығы $N-1$ болатын массив. C[i] элементі ($0 \le i \le N-2$) — 0 немесе 1 бүтін саны, мұндағы C[i] = 1 болса $i$ жолын қар басқанын, ал C[i] = 0 болса $i$ жолын қар баспағанын білдіреді.

Anya функциясының ішінде келесі функцияны шақыра аласыз:

• void Save(int place, int bit) Бұл функция Аняның ретранслятор серверіне бит сақтау операциясын білдіреді.

  • place аргументі битті жазатын орынды білдіреді. place мәні $0$ мен $L-1$ аралығындағы (қоса алғанда) бүтін сан болуы керек. Егер осы ауқымнан тыс мән көрсетілсе, ол Wrong Answer [1] ретінде бағаланады. Сондай-ақ, Anya функциясының әрбір шақырылуында бұл функцияны бірдей place аргументімен бір реттен артық шақыруға болмайды. Егер бірдей аргументпен екі рет шақырылса, ол Wrong Answer [2] ретінде бағаланады.
  • bit аргументі — жазылатын битті білдіретін бүтін сан, ол 0 немесе 1 болуы керек. Егер басқа мән көрсетілсе, ол Wrong Answer [3] ретінде бағаланады.

Save шақырылғаннан кейін ретранслятор серверінің place-ші битінің мәні bit болады. Егер Save шақырылуы Wrong Answer ретінде бағаланса, программа сол мезетте жұмысын тоқтатады.

Anya функциясы шақырылар алдында ретранслятор серверіндегі биттер әрқашан түгелдей 0-ге теңестіріледі. Яғни, Anya функциясының соңында Save функциясы арқылы сақтау операциясы орындалмаған орындарда 0 сақталады.

Екінші файл Boris.c немесе Boris.cpp деп аталады. Бұл файл Бористің стратегиясын іске асырады және келесі екі процедураны іске асыруы керек. Программа Borislib.h файлын қосуы тиіс.

• void InitBoris(int N, int A[], int B[]) Бұл функция әр тест жағдайы үшін дәл бір рет шақырылады.

  • N аргументі қалалар санын білдіреді.
  • A[] және B[] аргументтері — жолдардың байланысу ақпаратын білдіретін ұзындығы $N-1$ болатын массивтер. A[i] және B[i] элементтері ($0 \le i \le N-2$) $i$ жолы A[i] мен B[i] қалаларын екі бағытта да байланыстыратынын білдіретін бүтін сандар, мұндағы $0 \le A[i] < B[i] \le N-1$.

• int Boris(int city) Бұл функция InitBoris шақырылғаннан кейін бірнеше рет шақырылады. Бұл функция Бористің азаматтың сұрағына жауап беру әрекетіне сәйкес келеді.

  • city аргументі азаматтың сұрағын білдіреді. city — $1$ мен $N-1$ аралығындағы (қоса алғанда) бүтін сан. Бұл азаматтың 0-қаладан city қаласына бару үшін кем дегенде қанша қар басқан жолмен жүріп өту керектігін сұрағанын білдіреді.
  • Boris функциясы азаматтың сұрағына жауап болатын $0$ мен $N-1$ аралығындағы (қоса алғанда) бүтін санды қайтаруы керек. Егер осы ауқымнан тыс бүтін сан қайтарылса, ол Wrong Answer [4] ретінде бағаланады. Егер жауап қате болса, ол Wrong Answer [7] ретінде бағаланады.

Boris функциясының ішінде келесі функцияны шақыра аласыз:

• int Ask(int place) Бұл функция Бористің ретранслятор серверінен бит оқу операциясын білдіреді.

  • place аргументі битті оқитын орынды білдіреді. place мәні $0$ мен $L-1$ аралығындағы (қоса алғанда) бүтін сан болуы керек. Егер осы ауқымнан тыс мән көрсетілсе, ол Wrong Answer [5] ретінде бағаланады.

  Ask функциясының қайтаратын мәні — ретранслятор серверінің place-ші битінің мазмұнын білдіретін 0 немесе 1 бүтін саны. Сондай-ақ, Ask функциясын Boris функциясының әрбір шақырылуында ең көбі 20 рет шақыруға болады. Егер 20 реттен артық шақырылса, ол Wrong Answer [6] ретінде бағаланады.

Егер Ask шақырылуы Wrong Answer ретінде бағаланса, программа сол мезетте жұмысын тоқтатады.

Шектеулер

• $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$.
• Кез келген екі түрлі қаланың арасында қандай да бір жолдар тізбегі арқылы жүріп өтуге болады.

Ішкі тапсырмалар

1. (15 ұпай) $N \le 20$.
2. (5 ұпай) $N \le 100$.
3. (35 ұпай) Барлық $0 \le i \le N-2$ үшін $A_i = i$ және $B_i = i + 1$.
4. (45 ұпай) Қосымша шектеулер жоқ.

Мысалдар

Кіріс 1

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

Шығыс 1

1 0 2
2

Ескертпе

Жоғарыдағы мысал өзара әрекеттесу барысын көрсетеді. Кірістің бірінші жолы — $N=5$. Келесі 4 жол қабырғаларды (жолдарды) анықтайды. Келесі жол — $Q=2$. Одан кейінгі жолдар әр күн үшін қар басқан жолдар мен сұраныстарды сипаттайды. Шығыста әр күнгі сұраныстарға Бористің берген жауаптары көрсетілген.