«Ол заңнан тыс қарақшы әрі атақты, Ержүрек Andrii Popa.

Күндіз-түні ат үстінде жортады, Үлкен жолдан өз алымын жинайды, Ал елдің түкпір-түкпірінде Ұры ұстаушылар жанұшыра қашып барады»

— «Andrii Popa», Phoenix

Ghiță-да $N$ оң бүтін салмақтан тұратын, индекстелуі $0$-ден басталатын $S$ тізбегі бар. Ол Карпат патшасы болғандықтан, төбелерінің индекстері $0, 1, \ldots, N - 1$ болатын келесі шарттарды қанағаттандыратын екілік ағаш құрастырғысы келеді:

• Ағашты симметриялы (inorder) аралап шығу төбелерді индекстерінің өсу ретімен береді. Екілік ағашты симметриялы аралап шығу түбірдің сол жақ баласында түбірленген ішкі ағашты симметриялы аралап шығудан (егер ондай бала бар болса), одан кейін түбірдің индексінен, одан кейін түбірдің оң жақ баласында түбірленген ішкі ағашты симметриялы аралап шығудан (егер ондай бала бар болса) құралады.
• Егер $x$ төбесі $y$ төбесінің ата-анасы болса, онда $S_x$ саны $S_y$ санын бөледі.

Екілік ағаш дегеніміз — әрбір төбесінің ең көп дегенде екі баласы (олар сол жақ бала және оң жақ бала деп аталады) болатын ағаш тәрізді деректер құрылымы екенін еске саламыз.

Өкінішке қарай, атақты қарақшы Andrii Popa $S$ тізбегін ұрлап кетті де, Ghiță енді оған тікелей қол жеткізе алмайды. Озық технологияны (өзінің ұялы телефонын) пайдаланып, ол $S$ тізбегінің кез келген екі тұтас ішкі тізбегі $[a, b]$ мен $[c, d]$ үшін $\gcd[a, b]$ мәні $\gcd[c, d]$ мәніне тең бе, соны біле алады; мұндағы $\gcd[x, y]$ — $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$ сандарының ең үлкен ортақ бөлгіші. Өкінішке қарай, бұл технология өте қымбат — егер Ghiță оны $Q$ реттен артық қолданса, үлкен айыппұл төлеуге мәжбүр болады. Қажетті ағашты құру үшін осы технологияны ең көп дегенде $Q$ рет қолданып, оған көмектесіңіз. Бұлай істеу мүмкін екеніне кепілдік беріледі. Кез келген дұрыс шешім қабылданады.

Өзара әрекеттесу

Қатысушы popa.h тақырыптық файлын (C / C++) қосуы немесе popa.pas модулін (Pascal) жүзеге асыруы керек. Қатысушы келесі функцияны жүзеге асыруы қажет:

int solve(int N, int* Left, int* Right);

function solve(N: LongInt, var Left, Right: array of LongInt): LongInt;

Бұл функция ағаштың түбірін қайтаруы тиіс, сондай-ақ $\text{Left}_i$ мен $\text{Right}_i$ мәндерін сәйкесінше $i$ төбесінің сол жақ және оң жақ баласына теңестіруі керек. Егер $i$ төбесінің сол жақ баласы болмаса, $\text{Left}_i$ мәні $-1$ болуы тиіс. Егер $i$ төбесінің оң жақ баласы болмаса, $\text{Right}_i$ мәні $-1$ болуы тиіс. Left және Right алдын ала жады бөлінген, өлшемі дәл $N$ болатын екі массивті көрсетеді.

solve функциясы бір іске қосу барысында ең көп дегенде $5$ рет шақырылуы мүмкін. Жаһандық айнымалыларды қолданғанда абай болуды ұсынамыз.

Қатысушы келесі функцияны пайдалана алады:

int query(int a, int b, int c, int d);

function query(a, b, c, d: LongInt): LongInt;

Бұл функция $0 \le a \le b < N$ және $0 \le c \le d < N$ болғанда, тек $\gcd[a, b]$ мәні $\gcd[c, d]$ мәніне тең болса ғана $1$ мәнін, ал басқа жағдайда $0$ мәнін қайтарады.

Ішкі есептер

Ішкі есеп 1 (37 ұпай)

• $N = 100$
• $Q = 10000$

Ішкі есеп 2 (24 ұпай)

• $N = 1000$
• $Q = 20000$

Ішкі есеп 3 (39 ұпай)

• $N = 1000$
• $Q = 2000$

Мысалдар

$S = [12, 4, 16, 2, 2, 20]$ үшін өзара әрекеттесу мысалы:

Ескертпе

Алдыңғы мысал үшін Ghiță алғысы келетін түрдегі ағаштың бір мысалы: