Сар бүр Блэйк "Блэйк Технологи" компанийн эдийн засгийн үндсэн үзүүлэлтүүдийг агуулсан тайлан хүлээн авдаг. Энд компаний гаргасан $n$ ширхэг бүтээгдэхүүн байна. Эдгээрийн нэг бүрийн хувьд эцсийн тайлан болох ганц бүхэл тоон утга байх ба харгалзах орлогыг илтгэнэ. Тайлан Блэйк-д ирэхээс өмнө $m$ менежерүүдийн гараар дамжсан. Тэдгээрийн нэг бүр элементүүдийг өөр дараалалтай болгож өөрчилсан байж магадгүй. Өөрөөр хэлбэл $i$-р менежер эхний $r_{i}$ тоог буурсан биш эсвэл өссөн биш дарааллаар дарааллуулаад тайланг $i+1$ менежерт эсвэл шууд Блэйкруу(хэрвээ менежерийн дугаар $i = m$ байвал) дамжуулна.

"Блэйк Технологи" компанийн ажилчид яг одоо тайлангаа бэлдэж байна. Та анхны дараалал болох $n$ урттай $a_{i}$-г мэдэх ба менежер бүрийн тайлбар болох $r_{i}$ утгыг мэдэх ба энэ нь түүний дуртай дараалал юм. Та үйл явцыг хурдасгаж эцсийн тайлангийн харагдах байдлыг тодорхойлох хэрэгтэй.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 200 000$) байх ба харгалзан тайланд байгаа бүтээгдэхүүний тоо ба менежерүүдийн тоо юм.

Хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{i}$ ($|a_{i}| ≤ 10^{9}$) байх ба менежерүүдэд очихоос өмнөх анхны тайлан.

Дараагийн $m$ мөрөнд менежерүүдийн хийх гэж буй үйлдлүүдийн тодорхойлолтууд байна. $i$-р мөр бүрт хоёр бүхэл тоон утга $t_{i}$ ба $r_{i}$ (, $1 ≤ r_{i} ≤ n$) байх ба $i$-р менежер эхний $r_{i}$ тоог буурсан биш(хэрвээ $t_{i} = 1$ байвал) эсвэл өссөн биш (хэрвээ $t_{i} = 2$ байвал) дарааллаар альнаар нь эрэмбэлэхийг заана.

Гаралт

Гаралтанд $n$ ширхэг бүхэл тоон утга буюу $m$ менежерээр дамжин Блэйкд очих тайлан юм.

Эхний жишээн дээр анхны тайлан: $1 2 3$ гэж харагдана. Эхний менежерийн дараа эхний хоёр тоо байраа сольсон байна: $2 1 3$. Блэйкд тайлан энэ хэлбэрээрээ ирнэ.

Хоёр дахь жишээн дээр анхны тайлан: $1 2 4 3$ хэлбэртэй байна. Эхний менежер тайланг $4 2 1 3$ болгож өөрчилнө. Хоёр дахь менежерийн өөрчлөлтийн дараа тайлан $2 4 1 3$ болно. Энэ тайлан Бдэйкт хүргэгдэнэ.