D. Хотхон

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

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

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

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

Осколково хотод $n$ оюутны байр, $n$ их сургууль, $n$ цэргийн оффис бүхий хотхон байдаг. Эхэндээ $i$-р оюутны байр $i$-р их сургуульд харьяалагдаж, $i$-р цэргийн оффист хуваарилагддаг байв.

Амьдрал өрнөсөөр хотхонд зарим нэг өөрчлөлтүүдийг хийжээ. Өөрчлөлтүүд нь дараах 4 төрөлтэй:

  1. $a_{j}$ их сургууль нь $b_{j}$ их сургуультэй нэгдэнэ. Үүний дараа $b_{j}$ их сургуульд харьяалагддаг бүх оюутны байр $a_{j}$ их сургууль руу хуваарилагдаж, $b_{j}$ их сургууль үгүй болно.
  2. $c_{j}$ цэргийн оффис нь $d_{j}$ цэргийн оффистой нэгдэнэ. Үүний дараа $d_{j}$ цэргийн оффист хуваарилагдаж байсан бүх оюутны байр $c_{j}$ цэргийн оффис руу хуваарилагдаж, $d_{j}$ үгүй болно.
  3. $x_{j}$ их сургуулийн оюутнууд оюутны байр руу нүүнэ. $k_{x_{j}}$-г оюутнууд нүүж ирэх үед их сургуульд харьяалагдаж байсан оюутны байрны тоо гэж үзье. Тэгвэл $x_{j}$ их сургуулийн оюутны байран дахь оюутны тоо $k_{x_{j}}$-ээр нэмэгдэнэ (их сургуулльд харьяалагдах оюутны байр их байх тусам их сургуулийн оюутны байр бүрт их оюутан нүүж ирнэ гэдгийг анхаараарай).
  4. $y_{j}$ дугаартай цэргийн оффис нь өөрт хуваарилагддаг бүх оюутны байрандаа довтолгоо хийж, тэндээс бүх оюутныг авдаг.

Түүнчлэн оюутны байр бүр нэг үед зөвхөн нэг их сургууль болон нэг цэргийн оффист л хуваарилагдсан байдаг. Эхэндээ оюутны байрууд бүгд хоосон байсан.

Таны даалгавар бол хотхонд явагдах өөрчлөлтийг хийж, яг одоо хэдэн хүн $q_{j}$ оюутны байранд амьдарч байна вэ гэх асуулгуудад хариулах явдал юм.

Оролт

Эхний мөр харгалзан оюутны байрны тоо болон асуулгын тоог харуулах $n$ ба $m$ $(1≤n, m≤5*10^{5})$ 2 бүхэл тоог агуулна.

Дараагийн $m$ мөрүүд нь асуулгуудыг агуулна. Асуулга бүр нь дараах хэлбэрүүдийн аль нэгээр өгөгдөнө.:

  • «$U$ $a_{j}$ $b_{j}$» -- их сургуулиуд нэгдэх;
  • «$M$ $c_{j}$ $d_{j}$» -- цэргийн оффисууд нэгдэх;
  • «$A$ $x_{j}$» -- $x_{j}$ их сургуулийн оюутнууд оюутны байр руу нүүх;
  • «$Z$ $y_{j}$» -- $y_{j}$ цэргийн оффис дахь довтолгоо;
  • «$Q$ $q_{j}$» -- $q_{j}$ оюутны байран дахь хүмүүсийн тоог асуух. Асуулга дахь бүх тоо нь эерэг бүхэл тоо байх ба $n$-ээс хэтрэхгүй. Асуулгад байгаа их сургууль болон цэргийн оффисууд нь тухайн үед оршин байдаг гэж үзнэ.

Гаралт

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

Орчуулсан: Солонго

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

Оролт
2 7
A 1
Q 1
U 1 2
A 1
Z 1
Q 1
Q 2
Гаралт
1
0
2
Оролт
5 12
U 1 2
M 4 5
A 1
Q 1
A 3
A 4
Q 3
Q 4
Z 4
Q 4
A 5
Q 5
Гаралт
2
1
1
0
1

Тэмдэглэл

Эхний жишээг авч үзье:

  • Эхний асуулгад 1 дэх их сургууль ганцхан 1 дэх оюутны хотхонг эзэмшинэ. Тиймээс 1 дэх оюутны хотхон 1 оюутантай.
  • 3 дахь асуулгын дараа 1 дэх их сургууль 1 болон 2 дахь оюутны хотхонг эзэмшинэ.
  • 4 дэх асуулга 1 дэх их сургуульд харьяалагдаж байгаа 1 болон 2 дахь оюутны хотхон дахь оюутны тоог 2-оор нэмнэ. Ингэснээр 1 дэх оюутны хотхонд 3 оюутан, 2 дахь оюутны хотхонд 2 оюутан амьдарна.
  • 5 дахь асуулга 1 дэх цэргийн оффист хуваарилагдсан 1 дэх оюутны хотхонд амьдарч буй оюутны тоог 0 болгоно.
Сэтгэгдлүүдийг ачааллаж байна...