G. Яаш ба моднууд

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

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

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

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

Яаш моднуудтай тоглох их дуртай ба тэдгээр моднууд нь анхны тоогоор ямар нэг зүйл хийх үед онцгой их баярладаг байжээ.Өөрийнхөө 20-дахь төрсөн өдрөөр тэрээр зангилааны цэгүүд дээрээ хариулах ёстой асуултуудтай үндэстэй мод бэлэг болгон авчээ.Модон дээрх анхны тоонуудыг сонсоод Яаш сэтгэл хөдлөлдөө бүр жолоогоо алдан танаас түүнд туслан модон дээрх асуултуудад түүний өмнөөс хариулж өгөхийг хүсжээ.Мод $1$ гэсэн зангилааны цэг дээр үндэстэй ба $i$ зангилааны цэг бүрийн хувьд ямар нэг $a_{i}$ утга тухайн цэг дээр байх юм.Мөн бүхэл тоо $m$ өгөгдөнө.

Асуултууд нь дараах 2 төрөлтэй байна:

  1. Өгөгдсөн зангилааны цэг $v$ болон бүхэл утга $x$-ын хувьд, зангилааны цэг $v$-ын бүх дэд моднууд дээрх $a_{i}$-ын утгыг $x$-ээр нэмэгдүүлнэ.
  2. Өгөгдсөн зангилааны цэг $v$-ын хувьд, $v$-ын дэд модон дээр орших $u$ зангилааны цэг болон сөрөг биш бүхэл утга $k$-ын хувьд $a_{u} = p + m*k$ байх $m$-ээс бага $p$ анхны тоонууд нийт хэдэн ширхэг байгааг олно.

Оролт

Эхний мөрөнд харгалзан модны зангилааны цэгийн тоо болон бодлогын нөхцөлд байх $m$-ын утгыг илэрхийлэх 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n ≤ 100 000, 1 ≤ m ≤ 1000$) өгөгдөнө.

2-дахь мөрөнд зангилааны цэгүүд дээр байх анхны утгуудыг илэрхийлэх $n$ ширхэг бүхэл тоо $a_{i}$ ($0 ≤ a_{i} ≤ 10^{9}$)-ууд өгөгдөнө.

Үүний дараагийн $n - 1$ мөрөнд модыг дүрсэлнэ.Мөр болгонд 2 бүхэл тоо $u_{i}$ болон $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) өгөгдөх ба энэ нь $i$-дахь ирмэгээр холбогдсон зангилааны цэгүүдийг илэрхийлэх юм.

Дараагийн мөрөнд асуултуудын тоог илэрхийлэх ганц бүхэл тоо $q$ ($1 ≤ q ≤ 100 000$) өгөгдөнө.

Сүүлийн $q$ мөрийн мөр болгонд харгалзан 1 болон 2-дугаар төрлийн асуултыг илэрхийлэх 1 v x эсвэл 2 v ($1 ≤ v ≤ n, 0 ≤ x ≤ 10^{9}$) өгөгдөнө.Мөн дор хаяж нэг ширхэг 2-дугаар төрлийн асуулт өгөгдөнө.

Гаралт

2-дугаар төрлийн асуулт бүрийн хувьд тохирох анхны тоонуудын тоог хэвлэнэ.

Орчуулсан: Баатархүү

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

Оролт
8 20
3 7 9 8 4 11 7 3
1 2
1 3
3 4
4 5
4 6
4 7
5 8
4
2 1
1 1 1
2 5
2 4
Гаралт
3
1
1
Оролт
5 10
8 7 5 1 0
1 2
2 3
1 5
2 4
3
1 1 0
1 1 2
2 2
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...