Клеофасийн амьдардаг хотод нэгэн алдартай музей байдаг. Музейд удаан хугацаанд тавигдаж буй $n$ үзвэр ($1$-c $n$ хүртэл дугаарлагдсан) байх ба эдгээр үзвэрүүдийн $i$-р үзвэр нь $v_{i}$ утга болон $w_{i}$ масстай.

Ингээд музейг санхүүгийн том групп худалдаж авсан ба үзвэрүүдийг өөрчилж эхэлсэн. Энэ үед Клеофас музейг сонирхож эхэлсэн ба дараах зүйлсийг хэлж байна.

Та гурван төрлийн $q$ үйл явдлыг гүйцэтгэх ёстой:

• төрөл $1$ нь музей $v$ утга болон $w$ масстай үзвэр гарган тавина; энэ төрлийн $i$-р үйл явдалд гаргаж тавьсан үзвэр нь $n + i$ гэж дугаарлагдана (нарийн зүйлсийг жишээний тайлбараас харна уу)
• төрөл $2$ нь музей $x$ дугаартай үзвэрийг гаргах ба агуулахдаа аюулгүйгээр хадгална
• төрөл $3$ нь Клеофас музейд очих ба хэрвээ энд дээрэмчин байсан ба хулгайлсан үзвэрүүдийн нийт масс нь хамгийн ихдээ $m$ масстай байсан бол тэдгээрийн нийт утга нь хамгийн ихдээ хэд байж болох вэ? гэж бодно (мэдээж түүнд өөр чухал шалтгаан байхгүй).

3-р төрлийн үйл явдал бүрийн хувьд $s(m)$-г нийт масс нь $ ≤ m$ байх хулгайлагдсан үзвэрүүдийн боломжит хамгийн их утга гэе.

Илүү дэлгэрэнгүйгээр $D$-г одоо үзвэрт байгаа бүх үзвэрүүдийн дугааруудын бүрдэл гэе (анх $D$ = {1, ..., n} байна). $P(D)$ нь $D$-н бүх дэд бүрдлүүдийн бүрдэл байг мөн

байг.

Ингээд $s(m)$ нь

гэж тодорхойлогдоно.

бүрийн хувьд $s(m)$-г тооцоол. Гаралт нь тусгай форматтай байна.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n ≤ 5000$, $1 ≤ k ≤ 1000$) байх буюу музейн анхны үзвэрүүдийн тоо болон хулгайлагдсан үзвэрүүдийн хамгийн их масс байна.

Тэгээд $n$ мөр байна. Эдгээрийн $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр эерэг бүхэл тоо $v_{i}$ ба $w_{i}$ ($1 ≤ v_{i} ≤ 1 000 000$, $1 ≤ w_{i} ≤ 1000$) байх ба $i$-р үзвэрийн утга болон масс юм.

Дараагийн мөрөнд нэг бүхэл тоон утга $q$ ($1 ≤ q ≤ 30 000$) байх буюу үйл явдлуудын тоо юм.

Дараагийн $q$ мөр бүрт үйл явдлын тайлбар дараах форматтай байна:

• $1 v w$ нь 1 төрлийн үйл явдал бөгөөд $v$ утга $m$ масстай шинэ үзвэр нэмэгдсэн гэсэн үг ($1 ≤ v ≤ 1 000 000$, $1 ≤ w ≤ 1000$)
• $2 x$ нь 2 төрлийн үйл явдал бөгөөд $x$ дугаартай үзвэр хасагдсан гэсэн үг; хасагдсан үзвэр нь тухайн үед музейд тавигдсан үзвэр байна
• $3$ нь 3 төрлийн үйл явдал ба Клеофас музейд очих ба өөрийн асуултаа асууна

Энд хамгийн ихдээ $10 000$ ширхэг 1 төрлийн үйл явдал байх ба ядаж нэг ширхэг 3 төрлийн үйл явдал байна.

Гаралт

$s(m)$ утгын тоо нь их болж болох учир 3 төрлийн үйл явдлуудын хариултыг тусгай форматаар гарга.

3 төрлийн үйл явдал бүрийн хувьд $s(m)$-г уг үйл явдлын хувьд Клеофасийн асуултын хариулт гэж үзье; нэг мөрөнд нэг тоо -г хэвлэ. Энд $p = 10^{7} + 19$ ба $q = 10^{9} + 7$.

3 төрлийн үйл явдлуудын хариултуудыг оролтонд өгсөн дарааллаар хэвлэ.

Эхний жишээн дээр 3 төрлийн үйл явдлуудын хувьд дэлгэгдсэн үзвэрүүдийн дугаар болон $s(1), ..., s(10)$ утгууд нь дараах дараалалтай байна:

Үзвэр тус бүрийн утгууд нь $v_{1} = 30, v_{2} = 60, v_{3} = 5, v_{4} = 42, v_{5} = 20, v_{6} = 40$ ба массууд нь $w_{1} = 4, w_{2} = 6, w_{3} = 1, w_{4} = 5, w_{5} = 3, w_{6} = 6$ байна.

Хоёр дахь жишээн дээр бүх үзвэр хасагдсаны дураа ганц асуулт асуугдсан ба дурын $m$-н хувьд $s(m) = 0$ байна.