題目描述

在Kinda國裡有N棟樓，每棟樓都有其價錢及編號，編號依次為1~N。

Kinda Sir為了防止樓價太貴，于是他把樓價都模一個質數 P。

現在Kinda國會對这些楼進行不定期的进行翻新。

• 每一個小翻新會對所有樓價乘上M，
• 每一次大翻新都會把所有樓價變成其的M次方
• 由于kinda国的人们认为某些数会带来好运，所以在大翻新的时候，M和P-1互素

Kinda Sir有时候也会建造一些楼也会拆除一些楼。現在，Kinda Sir想要不定时地询问這些樓的樓價，请你帮助Kinda sir写一条这样的程序吧！

輸入格式

第一行為一個正整數N和一個正整數P，分別表示有N棟樓及要模的質數P。
接下來的一行有N個正整數，分別表示每棟樓的樓價。
接下來為一個正整數K，表示有K次操作。
接下來有K行，第一個整數op，表示:

op=0，输入一个整数y，表示建造一栋樓價为y的楼。
op=1，表示拆除编号最大的楼
op=2，輸入一個整數m，表示進行小翻新。
op=3，輸入一個整數m，表示進行大翻新。
op=4，輸入一個整數x，表示詢問第x棟樓的樓價。

輸出格式

對於每一次詢問，應該輸出第x棟樓的樓價除以P的余数。

數據範圍:
$ 1 \le x < N \le 10^6 $
$ P \le 10^6 $
$ m, y \le 10^9 $
$ K \le 10^5 $

Samples

5 17
1 3 6 9 10
6
2 7
3 19
4 5
0 8
3 23
4 6

8
15

原始資料

• Zero1 題號：b282
• Hydro 題號：Z1282
• Locale：zh_TW
• Display：deprecated