AT_abc410_c [ABC410C] Rotatable Array

There is an integer sequence $ A $ of length $ N $ , initially $ A_i = i $ . Process a total of $ Q $ queries of the following types: - Type $ 1 $ : Change $ A_p $ to $ x $ . - Type $ 2 $ : Output $ A_p $ . - Type $ 3 $ : Repeat the operation "move the first element of $ A $ to the end" $ k $ times. - Formally, replace $ A $ with $ (A_2,A_3,\dots,A_N,A_1) $ $ k $ times.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ \rm{Query} $ $ _1 $ $ \rm{Query} $ $ _2 $ $ \vdots $ $ \rm{Query} $ $ _Q $ Here, $ \rm{Query} $ $ _i $ represents the $ i $ -th query. Type $ 1 $ queries are given in the following format: > 1 $ p $ $ x $ Type $ 2 $ queries are given in the following format: > 2 $ p $ Type $ 3 $ queries are given in the following format: > 3 $ k $

For each Type $ 2 $ query, output the answer on a line.

### Sample Explanation 1 This input contains $ 5 $ queries. - Initially, $ A=(1,2,3,4,5) $ . - The $ 1 $ st query is Type $ 2 $ : output $ A_3=3 $ . - The $ 2 $ nd query is Type $ 1 $ : replace $ A_2 $ with $ 1000000 $ . - After the query, $ A=(1,1000000,3,4,5) $ . - The $ 3 $ rd query is Type $ 3 $ : repeat the operation "move the first element of $ A $ to the end" $ 4 $ times. - After the query, $ A=(5,1,1000000,3,4) $ . - The $ 4 $ th query is Type $ 2 $ : output $ A_2=1 $ . - The $ 5 $ th query is Type $ 2 $ : output $ A_3=1000000 $ . ### Sample Explanation 2 The output may be empty. ### Constraints - All input values are integers. - $ 1 \le N \le 10^6 $ - $ 1 \le Q \le 3 \times 10^5 $ - All queries satisfy the following constraints: - $ 1 \le p \le N $ - $ 1 \le x \le 10^6 $ - $ 1 \le k \le 10^9 $