Помогите с задачей по информатике

В далеком королевстве существовало два агентства — агентство пополнения казны и агентство улучшения условий бизнеса. Как видно из названия, эти агентства находятся в вечном противостоянии.

Структура королевства — дерево, т.е. королевство состоит из
n
городов, которые соединены
n
−
1
дорогами, так, что от любого города можно попасть в любой другой город. Каждый город
i
обязан отдавать королевству налог, который описывается целым числом
p
i
. В течение следующих
q
дней проходит одно из следующих событий (пусть сейчас день
s
):

1
. Агентство пополнения казны идет по пути от города
a
s
до города
b
s
, и в каждом городе повышает налог до
c
s
, если он меньше
c
s
(формально, пусть путь от
a
s
до
b
s
=

{
m
1
=
a
s
,
m
2
,
.
.
.
,
m
k
=
b
s
}
; тогда для любого
1
≤
i
≤
k
агентство пополнения казны делает
p
m
i
=
max
(
p
m
i
,
c
s
).

2
. Агентство улучшения условий бизнеса идет по пути от города
a
s
до города
b
s
, и в каждом городе понижает налог до
c
s
, если он больше
c
s
(формально, пусть путь от
a
s
до
b
s
=

{
m
1
=
a
s
,
m
2
,
.
.
.
,
m
k
=
b
s
}
; тогда для любого
1
≤
i
≤
k
агентство пополнения казны делает
p
m
i
=
min
(
p
m
i
,
c
s
).

3
. Король хочет узнать, какая сумма налогов на пути от
a
s
до
b
s
.

Пожалуйста, помогите ответить на все запросы.

Входные данные
В первой строке дано
2
числа
n
и
q

(
1
≤
n
≤
10
5
,
1
≤
q
≤
10
5
)
— количество городов в королевстве и количество запросов, на которое вы должны ответить.

Далее следует
n
−
1
строк,
i
-я из них содержит
2
числа
a
i
,
b
i
(
1
≤
a
i
≤
n
,
1
≤
b
i
≤
n
)
— они означают, что есть ребро между вершинами
a
i
и
b
i
. Гарантируется, что эти ребра задают дерево на
n
вершинах.

В следующей строке следует
n
чисел
p
1
,
p
2
,
…
,
p
n
(
∀
i
:

1
≤
i
≤
n

1
≤
p
i
≤
10
9
)
— начальные налоги в каждом городе.

Далее следует
q
строк,
i
-я из них описывает
i
-й запрос.

В начале каждого запроса следует одно целое число
t
i

(
1
≤
t
i
≤
3
)
, описывающее тип запроса.

Если
t
i
=
1
, далее следует
3
целых числа
a
i
,
b
i
,
c
i
(
1
≤
a
i
≤
n
,
1
≤
b
i
≤
n
,
1
≤
c
i
≤
10
9
)
, которые означают, что агентство пополнения казны идет по пути от города
a
i
до
b
i
, и повышает налог в каждом городе до
c
i
, если налог меньше.

Если
t
i
=
2
, далее следует
3
целых числа
a
i
,
b
i
,
c
i
(
1
≤
a
i
≤
n
,
1
≤
b
i
≤
n
,
1
≤
c
i
≤
10
9
)
, которые означают, что агентство улучшения условий бизнеса идет по пути от города
a
i
до
b
i
, и понижает налог в каждом городе до
c
i
, если налог больше.

Если
t
i
=
3
, далее следует
2
целых числа
a
i
,
b
i
(
1
≤
a
i
≤
n
,
1
≤
b
i
≤
n
)
, которые означают, что короля интересует сумма налогов на пути от
a
i
до
b
i
.

Дополнительное ограничение: гарантируется, что есть хотя бы
1
запрос типа
3
.