E. Шинэ жилийн мод

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Шинэ жилийн өдрүүд дууссан ч Рэша шинэ жилийн сүлд модоо буулгахыг хүссэнгүй. Тэр шинэ жилийнхээ модыг дахин чимэглэхээр түүний дотны найзууд болох Керим болон Гюралыг туслуулахаар дуудсан.

Шинэ жилийн мод нь чиглэлгүй $n$ оройтой ба үндэс нь $1$-р орой юм.

Та хоёр төрлийн үйлдлийг гүйцэтгэнэ:

  1. $v$ оройн дэд модонд байгаа бүх оройг $c$ өнгөтэй болгож соль.
  2. $v$ оройн дэд модонд байгаа ялгаатай өнгөнүүдийн тоог ол.

    Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n, m$ ($1 ≤ n, m ≤ 4*10^{5}$) -- Модон дахь оройн тоо болон үйлдлүүдийн тоо .

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $c_{i}$ ($1 ≤ c_{i} ≤ 60$) -- $i$ дахь оройн өнгө.

Дараагийн $n - 1$ мөр тус бүрт хоёр бүхэл тоон утга $x_{j}, y_{j}$ ($1 ≤ x_{j}, y_{j} ≤ n$) -- $j$-дэх ирмэгийн оройнууд. Энэ нь танд зөв чиглэлгүй мод өгөгдсөн гэсэн үг.

Сүүлийн $m$ мөр нь үйлдлүүдийн тодорхойлолтыг агуулсан. Тодорхойлолт бүр бүхэл тоон утга $t_{k}$ ($1 ≤ t_{k} ≤ 2$)-р эхлэдэг -- $k$-дэх асуултын төрөл. Эхний төрлийн үйлдлүүд нь дараах хоёр бүхэл тоон утгуудтай $v_{k}, c_{k}$ ($1 ≤ v_{k} ≤ n, 1 ≤ c_{k} ≤ 60$) – дэд мод нь $c_{k}$ өнгөөр будагдах оройн дугаар. Хоёр дахь төрлийн үйлдлүүд нь дараах бүхэл тоон утгатай $v_{k}$ ($1 ≤ v_{k} ≤ n$) – дэд модонд нь хэдэн ялгаатай өнгө орсныг олох оройн дугаар.

Гаралт

Хоёр дахь төрлийн үйлдэл бүрийн хувьд бүхэл тоон утга $a$-г хэвлэ – үйлдэлд өгөгдсөн оройн дэд модон дахь ялгаатай өнгөний тоо

Оролтонд байгаа үйлдлүүдийн дарааллаар тоо бүр тусдаа мөрөнд хэвлэгдсэн байх ёстой.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
7 10
1 1 1 1 1 1 1
1 2
1 3
1 4
3 5
3 6
3 7
1 3 2
2 1
1 4 3
2 1
1 2 5
2 1
1 6 4
2 1
2 2
2 3
Гаралт
2
3
4
5
1
2
Оролт
23 30
1 2 2 6 5 3 2 1 1 1 2 4 5 3 4 4 3 3 3 3 3 4 6
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
4 11
6 12
6 13
7 14
7 15
7 16
8 17
8 18
10 19
10 20
10 21
11 22
11 23
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
Гаралт
6
1
3
3
2
1
2
3
5
5
1
2
2
1
1
1
2
3
Орчуулгыг засах?
Сэтгэгдлүүдийг ачааллаж байна...