SP28632 COUNT1IT - Ghost Town

You are given **n** numbers initially. You have to maintain a **multiset** for those **n** numbers. Then you are given **q** queries. Qeuries will be one of the following types - 1\) **1 x** : Let **a** be the count of elements smaller than or equal to **x**. Add **x+a** into the multiset. 2\) **2 y** : report the number of numbers in the multiset that are smaller than or equal to **y**. 3\) ****3 z**** : report the **z**th smallest number of the multiset. Note that if any number **d** appears more than once, it is to be counted as many times it appears! Also, if z exceeds the number of elements in the **multiset**, that is answer for this query doesn't exist, print "**invalid".** Look at the sample input for clarification.

The first line will contain two integers, n and q, denoting the number of initially members of the multiset and the number of queries. Next q lines will be of he form - **Type D :** That is, the queries will be of the one of given 3 types and accordingly, you will be given and integer D. 10 20

You have to print the output for query numbers **2** and **3.**