E. ...Хүлээгээрэй...

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

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

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

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

Барни өөрийн мөрөөдлийн охиноо хайж байв. Тэрээр NYC-д амьдардаг бөгөөд NYC нь $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг уулзвартай ба эдгээр уулзваруудыг хооронд нь $n - 1$ ширхэг зам холбодог байжээ. Бид NYC-г $1$-р уулзвар дээр үндэстэй нэгэн үндэстэй мод гэж үзнэ. NYC-д $m$ ширхэг охид амьдрах ба эдгээрийн $i$-дахь нь $c_{i}$ уулзварын дагуу амьдардаг бөгөөд түүний жин нь анхандаа $i$ паунд байх ажээ.

Барни $x$ дугаартай охин нь хэрэв дараах нөхцөл биелж байвал $y$ дугаартай охиноос илүү дээр гэж үзэх юм: $x$ дугаартай охин нь $y$ дугаартай охиноос эрс бага жинтэй эсвэл эдгээр охид нь тэнцүү жинтэй боловч $x$ дугаартай охины амьдардаг уулзварын дугаар нь $y$ дугаартай охины амьдардаг уулзварын дугаараас эрс бага(өөрөөр хэлбэл $c_{x} < c_{y}$). Түүнчлэн ямар ч 2 охины хувьд тэдгээрийн аль нэг нь заавал нөгөө охиноосоо илүү дээр байх юм.

Дараагийн $q$ өдрийн өдөр болгон нэг ширхэг үйл явдал болж өнгөрнө. Нийт 2 төрлийн үйл явдал байна:

  1. Барни $v$ уулзвараас $u$ уулзвар уруу явна. Үр дүнд нь тэрээр өөрийн явах уулзварууд дээр амьдардаг хараахан гэртээ уриагүй байсан охидоос хамгийн ихдээ $k$ ширхэг хамгийн дажгүй охидыг сонгох бөгөөд тэдгээрийг гэртээ урьж тэдгээрийн дунд өөрийнх нь мөрөөдлийн охин байгаа эсэхийг шалгах юм. Хэрэв түүний явах уулзварууд дээр $k$-аас бага тооны урьд нь уригдаж байгаагүй охид байвал тэрээр бүгдийн урих ажээ.
  2. $v$ уулзварын дэд модон дээр($v$ нь өөрөөр орно) байрлах уулзварууд дагуу амьдардаг охид нь тодорхой хэмжээний жин нэмнэ. Үр дүнд нь тэдгээрийн жин $k$ паундаар нэмэгдсэн байна.

Та эхний төрлийн үйл явдал бүрийн хувьд Барни-д гэртээ урих охидын дугааруудыг хэлж өгөх юм.

Оролт

Оролтын эхний мөрөнд 3 бүхэл тоо $n$, $m$ болон $q$ ($1 ≤ n, m, q ≤ 10^{5}$) өгөгдөх ба эдгээр нь харгалзан NYC-дахь уулзваруудын тоо, NYC-д амьдардаг охидын тоо болон нийт болох үйл явдлын тоог тус тус илэрхийлнэ.

Дараагийн $n - 1$ мөрөнд замуудыг дүрсэлнэ. Мөр болгонд 2 бүхэл тоо $v$ болон $u$ ($1 ≤ v, u ≤ n, v ≠ u$) өгөгдөх бөгөөд энэ нь $v$ болон $u$ гэсэн уулзваруудыг холбох зам оршин байгааг илэрхийлнэ.

Дараагийн мөрөнд $m$ ширхэг бүхэл тоо $c_{1}, c_{2}, ..., c_{m}$ ($1 ≤ c_{i} ≤ n$)-ууд өгөгдөх ба эдгээр нь охидын амьдарч буй уулзваруудын дугааруудыг илэрхийлнэ.

Дараагийн $q$ мөрөнд үйл явдлууд нь цаг хугацааны дарааллын дагуу өгөгдөнө. Мөр болгон нь бүхэл тоо $t$ ($1 ≤ t ≤ 2$)-аар эхлэх бөгөөд энэ нь уг үйл явдлын төрлийг илэрхийлнэ.

Хэрэв $t = 1$ бол энэ мөр нь эхний төрлийн үйл явдлыг дүрслэх бөгөөд үүний араас 3-н бүхэл тоо $v$, $u$ болон $k$ ($1 ≤ v, u, k ≤ n$) өгөгдөх ба эдгээр нь Барни-ын явах замын захын цэгүүд болон түүний урьж болох хамгийн олон охидын тоог тус тус илэрхийлэх юм.

Бусад тохиолдолд уг мөр нь 2-р төрлийн үйл явдлыг дүрслэх бөгөөд үүний араас 2 бүхэл тоо $v$ болон $k$ ($1 ≤ v ≤ n, 1 ≤ k ≤ 10^{9}$) өгөгдөх ба эдгээр нь дэд модны үндэс болон дэд мод дээр байрлах бүх охидын жингийн нэмэгдэх ёстой утгыг тус тус илэрхийлнэ.

Гаралт

Эхний төрлийн үйл явдал бүрийн хувьд $t$ тоог хэвлэх ба дараа нь $t$ ширхэг бүхэл тоо $g_{1}, g_{2}, ..., g_{t}$-уудыг нэг мөрөнд хэвлэнэ. Энэ нь уг үйл явдлын хувьд Барни өөрийн үзэл бодлоор сайнаас нь муу хүртэл дарааллаар эрэмбэлсэн $g_{1}, ..., g_{t}$ гэсэн дугаартай $t$ ширхэг охидыг гэртээ урина гэдгийг илэрхийлэх юм.

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

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

Оролт
5 7 11
3 5
2 3
4 3
1 4
4 1 4 5 4 1 4
2 4 3
1 2 1 2
1 4 2 1
2 2 10
2 1 10
1 2 4 1
1 2 3 4
2 5 2
2 4 9
1 3 5 2
1 1 2 3
Гаралт
2 2 1 
1 3 
1 5 
0 
1 4 
2 6 7 

Тэмдэглэл

Эхний жишээний хувьд:

Үйл явдлуудын тайлбар нь дараах байдалтай байна:

  1. $4$-р уулзварын дэд модон дээр байрлах охидын жин $3$-аар ихэснэ. Эдгээр охид нь $1, 3, 5, 4, 7$ гэсэн дугааруудтай байх юм.
  2. Барни $2$-р уулзвараас $1$-р уулзвар уруу явна. Түүний явах зам дээр байх охидын дугаарууд нь $1, 2, 3, 5, 6, 7$ байх бөгөөд тэдгээрийн жингүүд нь харгалзан $4, 2, 6, 8, 6, 10$ байх юм. Иймд тэрээр $2$ болон $1$ дугаартай охидыг урих юм.
  3. Барни $4$-р уулзвараас $2$-р уулзвар уруу явна. Түүний явах зам дээр байх охидын дугаарууд нь $3, 5, 7$ байх бөгөөд тэдгээрийн жингүүд нь харгалзан $6, 8, 10$ байх юм. Иймд тэрээр $3$ дугаартай охиныг урина.
  4. $2$-р уулзварын дэд модон дээр байрлах охидын жин $10$-аар ихэснэ. Энд ямар ч уригдаж байгаагүй охид байхгүй тул юу ч болохгүй байх юм.
  5. $1$-р уулзварын дэд модон дээр байрлах охидын жин $10$-аар ихэснэ. Эдгээр охидын(үлдсэн бүх охид) дугаарууд нь $4, 5, 6, 7$ байх юм.
  6. Барни $2$-р уулзвараас $4$-р уулзвар уруу явна. Түүний явах зам дээр байх охидын дугаарууд нь $5, 7$ байх бөгөөд тэдгээрийн жингүүд нь харгалзан $18, 20$ байх юм. Иймд тэрээр $5$ дугаартай охиныг урина.
  7. Барни $2$-р уулзвараас $3$-р уулзвар уруу явна. Түүний явах зам дээр ямар ч охин байхгүй байна.
  8. $5$-р уулзварын дэд модон дээр байрлах охидын жин $2$-оор ихэснэ. Энд байх цорын ганц охин нь $4$ дугаартай охин байна.
  9. $4$-р уулзварын дэд модон дээр байрлах охидын жин $9$-өөр ихэснэ. Эдгээр охидын дугаарууд нь $4, 6, 7$ байна.
  10. Барни $3$-р уулзвараас $5$-р уулзвар уруу явна. Түүний явах зам дээр байх цорын ганц охин нь $4$ гэсэн дугаартай байна.
  11. Барни $1$-р уулзвараас $2$-р уулзвар уруу явна. Түүний явах зам дээр байх охидын дугаарууд нь $6, 7$ байх бөгөөд тэдгээрийн жингүүд нь харгалзан $16, 29$ байна.
Сэтгэгдлүүдийг ачааллаж байна...