Лимак баавгай асуултуудад хариулахдаа сайн биш ажээ. Иймд тэрээр танаас тусламж хүсжээ.

Бид $42$-ын зэрэгтүүдийг муу гэж үзэх юм ($1, 42, 1764, ...$ гэх мэтчилэн тоонууд). Харин бусад тоонуудыг сайн гэж үзнэ.

Танд $n$ ширхэг сайн бүхэл тоонууд $t_{1}, t_{2}, ..., t_{n}$-уудын дараалал өгөгджээ. Таны даалгавар бол дараах 3-н төрлийн $q$ ширхэг асуултуудад хариулах явдал юм:

• "1 i" -- $t_{i}$-г тусдаа мөрөнд хэвлэнэ.
• "2 a b x" -- бүх -ын хувьд $t_{i}$-г $x$ утгатай болгоно. Мөн энд $x$ нь сайн тоо байх юм.
• "3 a b x" -- бүх -ын хувьд $t_{i}$-ын утгыг $x$-ээр ихэсгэнэ. Үүний дараа дараалал дотор дор хаяж нэг ширхэг $t_{i}$ нь муу тоо байвал уг үйлдлийг давтан хийх бөгөөд дараалал дотор ямар ч муу тоо байхгүй бол уг үйлдлийг зогсоох юм.

Асуулт болгоны дараа бүх $t_{i}$-ууд нь сайн тоонууд байгааг анхаарна уу.

Оролт

Эхний мөрөнд харгалзан Лимак-ийн дарааллын хэмжээ болон асуултуудын тоог илэрхийлэх 2 бүхэл тоо $n$ болон $q$ ($1 ≤ n, q ≤ 100 000$) өгөгдөнө.

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

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

2 болон 3-р төрлийн асуултуудын хувьд $1 ≤ a ≤ b ≤ n$ байх юм.

Мөн 2-р төрлийн асуултын бүхэл тоо $x$ ($2 ≤ x ≤ 10^{9}$) нь сайн тоо байна.

3-р төрлийн асуултын бүхэл тоо $x$ ($1 ≤ x ≤ 10^{9}$) нь магадгүй муу тоо байж болох юм.

Гаралт

Эхний төрлийн асуулт бүрийн хувьд хариултыг тусдаа мөрөнд хэвлэнэ үү.

3 2 4 42 гэсэн асуултын дараах дараалал нь $40, 1742, 49, 1714, 4, 1722$ байх юм.

3 2 6 50 гэсэн асуултын дараах дараалал нь $40, 1842, 149, 1814, 104, 1822$ байх юм.

2 3 4 41 гэсэн асуултын дараах дараалал нь $40, 1842, 41, 41, 104, 1822$ байх юм.

3 1 5 1 гэсэн асуултын дараах дараалал нь $43, 1845, 44, 44, 107, 1822$ байх юм.