Пироголяндiя

Як відомо, Пироголяндія "— країна, жителі якої дуже полюбляють пироги. Саме тому в ній побудовано $n$ пекарень, кожна з яких має унікальний цілий номер від $1$ до $n$. У кожної пекарні є свій склад, що зберігає певну кількість пирогів, зокрема пекарня з номером $i$ зберігає $a_i$ пирогів на своєму складі.

Також між деякими пекарнями було прокладено дороги, по яких можна перевозити пироги від однієї пекарні до іншої. Усього було прокладено $n-1$ доріг, кожна з яких має свій унікальний цілий номер від $1$ до $n-1$. $i$-а дорога була прокладена між пекарнями $u_i$ та $v_i$, тобто можна перевозити будь-яку кількість пирогів зі складу пекарні $u_i$ до складу пекарні $v_i$ та навпаки.

Шляхом між пекарнями $u$ та $v$ будемо називати послідовність унікальних номерів пекарень $p_1,p_2,...,p_k$, таку, що існує дорога між кожною парою пекарень $p_i$ та $p_{i+1}$, для будь-якого $i$ від $1$ до $k-1$, а також $p_1=u$ та $p_k=v$. Відомо, що між кожною парою пекарень існує рівно один шлях, що не відвідує жодну пекарню двічі.

Іноді у Пироголяндії трапляються землетруси, через що деякі дороги можуть ставати перекритими, а тому по них не можна перевозити пироги. Також іноді служба ремонту доріг може ремонтувати деякі з доріг, після чого вони стають знову доступними для перевезень. Отже, кожна дорога має мати один із двох станів "— вона має бути або неперекритою, або перекритою.

Компонентою пекарні $u$ будемо називати множину всіх пекарень, до яких є шлях від пекарні з номером $u$, що не проходить через жодну перекриту дорогу. Сама пекарня $u$ також входить до своєї компоненти.

Одним із найвідоміших жителів Пироголяндії є Козак Вус, який отримав свою популярність на тому, що з'їв більше всіх пирогів на щорічному святі пироголюбів.

Іноді у Пироголяндії відбуваються різні події, що пов'язані з пекарнями, дорогами та нашим другом Козаком Вусом. Вам потрібно вміти оброблювати $m$ подій, що будуть подані у вигляді запитів різних типів, та вміти відповідати на деякі з них.

Усього є $7$ типів запитів:

1. Змінити стан дороги з номером $p$ на протилежний. Тобто якщо до цього запиту дорога з номером $p$ була перекритою, то після нього вона стає неперекритою, і навпаки, якщо дорога була неперекритою то вона стає перекритою.

2. До складу кожної пекарні, що належить компоненті пекарні із номером $p$, завезли $w$ пирогів. Тобто якщо пекарня з номером $u$ належить компоненті пекарні $p$, то треба збільшити значення $a_u$ на $w$.

3. Усі пекарні з компоненти пекарні з номером $p$ перевозять усі свої пироги до складу пекарні з номером $p$. Тобто після цього запиту на складі пекарні із номером $p$ будуть зберігатись усі пироги з усіх пекарень, що знаходяться в компоненті пекарні $p$, а в усіх інших пекарнях цієї компоненти склади будуть пусті.

4. Козак Вус хоче дізнатись, скільки пирогів зберігається на складі пекарні з номером $p$, тобто значення $a_p$.

5. Козак Вус хоче дізнатися сумарну кількість пирогів, що зберігаються на складах пекарень із компоненти пекарні з номером $p$.

6. Козак Вус з'їдає всі пироги зі складу кожної пекарні з компоненти пекарні з номером $p$. Тобто після цього запиту для кожної пекарні $u$, що належить компоненті пекарні $p$, значення $a_u$ повинно бути рівним 0.

7. Козак Вус хоче дізнатись, яку мінімальну кількість доріг треба відремонтувати, щоб він міг з'їсти всі пироги, що зберігаються на складах пекарень Пироголяндії, якщо він може почати свій шлях із будь-якої пекарні та пересуватись лише по неперекритих дорогах.

Зауважте, що запити типів $4,5$ та $7$ ніяк не впливають на пекарні та дороги, вони лиш повинні знаходити відповідь.

Вхідні дані

Перший рядок містить три цілі числа $n$, $m$ та $g$ ($1\le n,m\le 250000$, $0\le g\le 11$) "— кількість пекарень у Пироголяндії, кількість подій та номер блока відповідно.

$i$-й з наступних $n-1$ рядків містить по два цілі числа $u_i$ та $v_i$ ($1\le u_i,v_i\le n$) "— пара пекарень між якими прокладено дорогу із номером $i$. Гарантується, що між кожною парою пекарень є рівно один шлях.

Наступний рядок містить рядок з $n-1$ символів $0$ або $1$. $i$-й з цих символів рівний $1$, якщо дорога з номером $i$ перекрита, та $0$, якщо вона не перекрита.

Наступний рядок містить послідовність з $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($0\le a_i\le 10^5$) "— кількість пирогів на складі кожної пекарні.

Кожен із наступних $m$ рядків містить опис відповідного запиту. Перше число в рядку задає тип запиту. У випадку, якщо запит $2$-го типу, то рядок містить ще два параметри $p$ ($1\le p\le n$) та $w$ ($0\le w\le 10^5$). Якщо тип запиту рівний $1$, то рядок містить один додатковий параметр $p$ $(1\le p\le n-1)$. Якщо тип запиту рівний від $3$ до $6$, то рядок містить лише один додатковий параметр $p$ ($1\le p\le n$). В іншому випадку, якщо запит $7$-го типу, рядок не містить додаткових параметрів.

Протокол взаємодії

Вам потрібно реалізувати вісім функцій:

void init(integer n, array of integers u, array of integers v, array of integers b, 
          array of integers a, integer g)

• $n$ — кількість пекарень у Пироголяндії;

• $u_i$ та $v_i$ ($|u|=|v|=n-1$) — номери пекарень, між якими прокладено $i$-ту дорогу;

• $b_i$ ($|b|=n-1$) рівне $1$, якщо $i$-та дорога перекрита, та $0$ інакше;

• $a_i$ ($|a|=n$) — кількість пирогів в $i$-ій пекарні;

• $g$ — номер блока;

• ця функція викликається першою лише один раз. Вона потрібна для того, щоб повідомити вам кількість пекарень у Пироголяндії, пари пекарень, між якими є дороги, стан кожної дороги, початкову кількість пирогів на складі кожної пекарні та номер блоку. Лише після виклику цієї функції будуть викликатись інші сім.

void query_1(integer p)

• $p$ — номер дороги, стан якої треба змінити;

• ця функція викликається, коли потрібно задати запит першого типу.

void query_2(integer p, integer w)

• $p$ — номер пекарні;

• $w$ — кількість пирогів, які завезли до кожної пекарні компоненти пекарні з номером $p$;

• ця функція викликається, коли потрібно задати запит другого типу.

void query_3(integer p)

• $p$ — номер пекарні;

• ця функція викликається, коли потрібно задати запит третього типу.

integer query_4(integer p)

• $p$ — номер пекарні;

• ця функція викликається, коли потрібно задати запит четвертого типу;

• функція має повернути ціле число — відповідь на запит.

integer query_5(integer p)

• $p$ — номер пекарні;

• ця функція викликається, коли потрібно задати запит п'ятого типу;

• функція має повернути ціле число — відповідь на запит.

void query_6(integer p)

• $p$ — номер пекарні;

• ця функція викликається, коли потрібно задати запит шостого типу.

integer query_7()

• ця функція викликається, коли потрібно задати запит сьомого типу;

• функція має повернути ціле число — відповідь на запит.

Вихідні дані

На кожний запит типу $4$, $5$ та $7$ виведіть відповідь в окремому рядку.

Приклади

5 11 0
1 2
1 3
3 4
3 5
0100
1 0 6 1 3
5 3
3 4
2 5 4
4 3
7
6 4
1 2
5 4
2 2 1
1 3
5 2

10
4
1
1
5

Примітка

На малюнках пекарні зображені у вигляді кола, всередині якого задано два цілі числа "— номер пекарні та кількість пирогів на складі цієї пекарні. Неперекриті дороги між пекарнями зображено суцільною лінією, а перекриті пунктирною.

На малюнку $0$ зображено Пироголяндію до всіх змін. Дорога з номером $2$ між пекарнями з номерами $1$ та $3$ перекрита. У компоненті пекарні з номером $1$, так само як для пекарні з номером $2$, знаходяться пекарні з номерами $1$ та $2$. У компоненті пекарень із номерами $3$, $4$ та $5$ знаходяться пекарні з номерами $3$, $4$ та $5$, отже, кількість пирогів у пекарнях із компоненти пекарні $3$ рівна $6+1+3=10$.

Після другого запиту (Мал. $1$) пекарні з номерами $3$ та $5$ перевозять свої пироги до складу пекарні з номером $4$.

Після третього запиту (Мал. $2$) до складу пекарень з номерами $3$, $4$ та $5$ завезли по $4$ пироги, отже, кількість пирогів на складі пекарні з номером $3$ тепер рівна $4$. На складі кожної пекарні, окрім пекарні з номером $2$, є хоча б $1$ пиріг. Якщо Козак Вус почне свій шлях із пекарні з номером $1$ або $2$, то йому доведеться відремонтувати дорогу з номером $2$, щоб він міг дістатись пекарні з номером $3$. Якщо він почне свій шлях з пекарні з номером $3$ або $4$, або $5$, то йому доведеться відремонтувати ту ж саму дорогу з номером $2$, щоб дістатись до пекарні з номером $1$. Тому відповідь на запит з номером $5$ рівна $1$.

Після шостого запиту (Мал. $3$) Козак Вус з'їдає всі пироги зі складу пекарень з номерами $3$, $4$ та $5$.

Після сьомого запиту (Мал. $4$) служба ремонту доріг відремонтує дорогу з номером $2$, тому тепер вона стає неперекритою. Тепер у компоненті пекарні з номером $1$, так само як і для всіх інших пекарень, знаходяться всі пекарні Пироголяндії. Тому відповідь на восьмий запит рівна $0+1+0+0+0=1$.

Після дев'ятого запиту (Мал. $5$) до складу кожної пекарні завезли по $1$ пирогу.

Після десятого запиту (Мал. $6$) через землетрус руйнується дорога з номером $3$, тому вона стає перекритою. Тепер у компоненті пекарні з номером $1$ знаходяться всі пекарні, окрім пекарні з номером $4$, а в компоненті пекарні з номером $4$ знаходиться лише вона сама. Тому відповідь на останній запит рівна $2+1+1+1=5$.

Оцінювання

1. ($2$ балів) $n\le 3000$; $m\le 3000$; немає запитів типу $1$ та $7$; усі дороги спочатку перекриті;

2. ($3$ балів) $n\le 3000$; $m\le 3000$; немає запитів типу $1$ та $7$; усі дороги спочатку неперекриті;

3. ($5$ балів) $n\le 3000$; $m\le 3000$; немає запитів типу $1$ та $7$;

4. ($6$ балів) $n\le 3000$; $m\le 3000$; немає запитів типу $7$;

5. ($8$ балів) $n\le 3000$; $m\le 3000$;

6. ($10$ балів) немає запитів типу $1$ та $7$;

7. ($16$ балів) немає запитів типу $7$; у запитах типу $1$ дороги завжди змінюються лише з перекритих на неперекриті;

8. ($15$ балів) немає запитів типу $1$;

9. ($9$ балів) немає запитів типу $7$;

10. ($17$ балів) кожна пекарня поєднана дорогою не більше ніж з двома іншими пекарнями;

11. ($9$ балів) без додаткових обмежень;