D. Баавгайн фэн хуудсууд

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

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

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

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

$1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг фэн хуудас бүхий нэгэн олон нийтийн вэб сайт байжээ. Мөн $n$ ширхэг компани байх бөгөөд $i$-дахь компани нь $i$-р фэн хуудсыг эзэмшдэг байв.

Саяхан уг вэб сайт нь дагах буюу following хэмээх нэгэн шинэ үйлдэл нэвтрүүлжээ. Түүнчлэн фэн хуудас болгон нь яг нэг ширхэг өөр фэн хуудсыг дагах ёстой байв.

Вэб сайт нь $i$-р хуудас нь $j$-р хуудсыг дагах бөгөөд үүний зэрэгцээ $j$-р хуудас нь $i$-р хуудсыг дагадаг байхыг зөвшөөрөхгүй ба ямар нэгэн фэн хуудас нь өөрийгөө дагасан байж болохгүй ажээ.

$i$-р фэн хуудас өөр ямар нэгэн $j_{0}$-р фэн хуудсыг дагасан байна гэж үзье. Түүнчлэн $i$-р фэн хуудас нь өөр $k$ ширхэг фэн хуудсууд буюу $j_{1}, j_{2}, ..., j_{k}$-уудаар дагагдсан байна гэж үзье. Тэгвэл $i$-р фэн хуудас уруу зочлох хүмүүс нь $k + 2$ ширхэг ялгаатай компаниудыг зар сурталчилгаануудыг харах бөгөөд тодруулбал $i, j_{0}, j_{1}, ..., j_{k}$-р компаниудын зар сурталчилгаануудыг харах юм. Яг $t_{i}$ ширхэг хүн $i$-р фэн хуудас дээр лайк(like буюу subscribe) дарах бөгөөд эдгээр хүмүүс тус бүр нь яг нэг ширхэг зар сурталчилгаан дээр дарж үзэх ажээ. $j_{0}, j_{1}, ..., j_{k}$ гэсэн $k + 1$ ширхэг компаниудын тус бүрийн хувьд яг ширхэг хүмүүс тэдгээрийн зар сурталчилгаан дээр дарж үзэх бөгөөд үлдсэн ширхэг хүмүүс нь $i$-р компанийн (уг фэн хуудсыг эзэмшигч компани) зар сурталчилгаан дээр дарж үзэх ажээ.

Түүнчлэн ямар нэгэн компанийн нийт ашиг нь уг компанийн зар сурталчилгаанууд дээр дарж үзсэн хүмүүсийн тоотой тэнцүү байна.

Лимак болон Рэйдвүүш нар таны тусламжийг хүсжээ. Анхандаа $i$-р фэн хуудас нь $f_{i}$-р хуудсыг дагасан байх юм. Таны даалгавар бол дараах 3-н төрлийн $q$ ширхэг асуултуудыг гүйцэтгэх явдал байв:

  • 1 i j -- $i$-р фэн хуудас нь одооноос эхлэн $j$-р фэн хуудсыг дагана. Түүнчлэн энэ асуултын өмнө нь $i$-р фэн хуудас нь $j$-р фэн хуудсыг дагаагүй байх нь баттай бөгөөд энэ төрлийн асуултуудын хувьд бодлогын оролтын хэсэгт нэмэлт нөхцөл зааж өгсөн байгааг анхаарна уу.
  • 2 i -- $i$-р компанийн нийт орлогын хэмжээг хэвлэнэ.
  • 3 -- 2 бүхэл тоо хэвлэнэ: компаниудын олж буй хамгийн бага нийт орлогын хэмжээ болон хамгийн их нийт орлогын хэмжээг хэвлэнэ.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $q$ ($3 ≤ n ≤ 100 000$, $1 ≤ q ≤ 100 000$) өгөгдөх ба эдгээр нь харгалзан нийт фэн хуудаснуудын тоо болон асуултуудын тоог тус тус илэрхийлнэ.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $t_{1}, t_{2}, ..., t_{n}$ ($1 ≤ t_{i} ≤ 10^{12}$)-ууд өгөгдөх ба энд $t_{i}$-аар $i$-р фэн хуудас дээр лайк дарах хүмүүсийн тоог тэмдэглэнэ.

3-дахь мөрөнд $n$ ширхэг бүхэл тоо $f_{1}, f_{2}, ..., f_{n}$ ($1 ≤ f_{i} ≤ n$)-ууд өгөгдөнө. Анхандаа $i$-р фэн хуудас нь $f_{i}$-р фэн хуудсыг дагасан байх юм.

Дараа нь $q$ ширхэг мөр өгөгдөнө. Эдгээрийн $i$-дахь мөрөнд $i$-р асуултыг дүрсэлнэ. Уг мөрийн эхний тоо нь $type_{i}$ ($1 ≤ type_{i} ≤ 3$) гэсэн бүхэл тоо байх бөгөөд энэ нь уг асуултын төрлийг илэрхийлнэ.

Эхний төрлийн асуултууд нь хамгийн ихдээ $50 000$ удаа өгөгдөнө. Түүнчлэн оролтод 2 эсвэл 3-р төрлийн дор хаяж нэг ширхэг асуулт өгөгдөх бөгөөд иймд бодлогын гаралт нь яасан ч хоосон байхгүй байна.

Мөн хугацааны ямар ч мөчид ямар нэгэн фэн хуудас нь өөрийгөө дагасан байж болохгүй бөгөөд ямар ч 2 фэн хуудсууд нь нэг нэгнээ дагасан байж болохгүй байх юм.

Гаралт

2-р төрлийн асуулт бүрийн хувьд тусдаа мөрөнд өгөгдсөн компанийн нийт орлогын хэмжээг илэрхийлэх ганц бүхэл тоог хэвлэнэ үү. 3-р төрлийн асуулт бүрийн хувьд тусдаа мөрөнд харгалзан хамгийн бага болон хамгийн их нийт орлогын хэмжээг илэрхийлэх 2 бүхэл тоог хэвлэнэ үү.

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

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

Оролт
5 12
10 20 30 40 50
2 3 4 5 2
2 1
2 2
2 3
2 4
2 5
1 4 2
2 1
2 2
2 3
2 4
2 5
3
Гаралт
10
36
28
40
36
9
57
27
28
29
9 57

Тэмдэглэл

Өгөгдсөн жишээнд нийтдээ $5$ ширхэг фэн хуудас байх бөгөөд эдгээрийн $i$-дахь хуудас дээр $i*10$ ширхэг хүн лайк дарсан байх юм.

Дээрх зураг дээр лайк дарсан хүмүүсийн тоог тойргууд дотор бичсэн байна. $A$-аас $B$ хүртэлх сум нь $A$ фэн хуудас нь $B$ фэн хуудсыг дагаж байгааг илэрхийлэх юм.

Зүүн талд байрлах зураг нь анхны нөхцөл байдлыг үзүүлнэ. Эхний компани хэмжээний орлогыг өөрийн эзэмшдэг фэн хуудаснаас олох бөгөөд хэмжээний орлогыг $2$-р фэн хуудаснаас олох юм. Ингэснээр түүний нийт орлого нь $5 + 5 = 10$ болно. Иймд та ("2 1") гэсэн эхний асуултын дараа $10$ гэж хэвлэх ёстой юм.

Баруун талд байрлах зураг нь "1 4 2" гэсэн асуултын дараах($4$-р фэн хуудас нь $2$-р фэн хуудсыг дагасны дараах) нөхцөл байдлыг үзүүлнэ. Дараа нь эхний компани нь өөрийн эзэмшдэг фэн хуудаснаас олох орлого нь $5$ хэвээр байх бөгөөд одоо тэрээр $2$-р фэн хуудаснаас хэмжээний орлогыг олох юм. Ингэснээр одоо уг компанийн нийт орлого нь $5 + 4 = 9$ болно.

Сэтгэгдлүүдийг ачааллаж байна...