B. Сургууль

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

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

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

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

Берландын ахлах сургуулийн "B" группын 6-р ангид $n$ ширхэг сурагч сурдаг байжээ. Тэдгээрийн сурагчдын тус бүр нь ямар нэгэн шинэ мэдээ олж сонсмогцоо дууддаг яг нэг ширхэг найзтай байв. Бид $i$ дугаартай сурагчийн найзын дугаарыг $g(i)$-аар тэмдэглэе. Уг нөхөрлөл нь харилцан нөхөрлөл биш юм. Өөрөөр хэлбэл $g(g(i))$ нь заавал $i$ байх албагүй.

$i$-дахь өдөр $a_{i}$ дугаартай сурагч $b_{i}$ ($b_{i} ≥ 1$) зэрэглэлийн мэдээ сонсдог байв. Мэдээ сонсмогцоо тэрээр өөрийн найз уруугаа утсаар залган энэ талаараа хэлэх юм. Тэрээр уг мэдээллийг найздаа хэлэхэд тухай мэдээлэл нь хуучин мэдээлэл болох ба зэрэглэл нь бага зэрэг буурах буюу $b_{i} - 1$ болно. Түүний найз нь мөн ижил энэ үйлдлийг хийх буюу өөрийн найз уруугаа залган мэдээг дуулгах ажээ. Иймд найзын найз нь аль хэдийн $b_{i} - 2$ зэрэглэлтэй болсон мэдээллийг сонсох юм. Хэн ч 0 зэрэглэлтэй мэдээ хүнд хэлэхийг хүсэхгүй учраас уг үйл явц нь мэдээллийн зэрэглэл нь 0 болох хүртэл үргэлжилнэ.

Илүү дэлгэрэнгүй тайлбарлавал, хүн болгон дараах байдлаар уг үйл явдалд хандах юм: хэрэв тухайн хүн $x$ нь 0-ээс ялгаатай $y$ зэрэглэл бүхий мэдээлэл олж сонсвол өөрийн найз $g(i)$ уруугаа залгаж хэлнэ. Түүний найз нь $y - 1$ зэрэглэлтэй мэдээ сонсох ба хэрэв зэрэглэл нь 0-ээс их байвал уг үйл явц нь цааш үргэлжлэх юм.

Эдгээр өдрүүдийн турш нэг хүн өөрийн найздаа өөр өөр зэрэглэлтэй ижилхэн мэдээлэл хэлж болохыг анхаарна уу. Түүнчлэн $b_{i}$ зэрэглэлтэй мэдээлэл нь $b_{i}$ удаа утасны шугамаар яригдах юм. Өөрөөр хэлбэл $b_{i}$ удаа хүмүүс цааш найздаа дуулгана.

Таны даалгавар бол $i$-дахь өдөр анхны мэдээгээ сонссон сурагчдын тоо болох $res_{i}$-ын утгуудыг олох юм.

$b_{i}$-ын утгууд нь анхандаа мэдэгдэж байх бөгөөд $a_{i}$-ын утгыг дараах томьёоноос олно:

энд mod гэдэг нь модуль-ын үйлдлийг илэрхийлэх ба $res_{0}$-ыг 0-тэй тэнцүү гэж үзнэ. Харин $v_{i}$-ууд нь өгөгдсөн бүхэл тоонууд байна.

Оролт

Эхний мөрөнд сурагчдын тоо болон өдрийн тоог илэрхийлэх зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n, m ≤ 10^{5}$) өгөгдөнө. 2-дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоо $g(i)$ ($1 ≤ g(i) ≤ n, g(i) ≠ i$)-ууд өгөгдөх ба эдгээр нь $i$-р сурагчийн найзын дугаарыг илэрхийлнэ. 3-дахь мөрөнд $m$ ширхэг зайгаар тусгаарлагдсан бүхэл тоонууд $v_{i}$ ($1 ≤ v_{i} ≤ 10^{7}$)-ууд өгөгдөнө. 4-дэх мөрөнд $m$ ширхэг зайгаар тусгаарлагдсан бүхэл тоонууд $b_{i}$ ($1 ≤ b_{i} ≤ 10^{7}$)-ууд өгөгдөнө.

Гаралт

Тус бүр нь нэг тоо агуулсан $m$ ширхэг мөр хэвлэнэ үү. $i$-р мөрөнд $res_{i}$ тоо хэвлэгдэх ба энэ нь $m$ өдрийн турш сонссон мэдээллүүдийн хамгийн анх сонссон мэдээ нь $i$ дугаартай мэдээлэл байх сурагчдын тоог илэрхийлэх юм. Мэдээллийн дугаар гэдэг нь уг мэдээллийг сонсох өдрийн дугаартай тэнцүү байна. Өдрүүд нь оролтод өгөгдсөн дарааллаараа нэгээс эхлэн дугаарлагдсан байх бөгөөд $res_{0}$-ыг хэвлэх хэрэггүй.

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

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

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