How Many HouGong

There are N rooms in the palace of “Hou”. (Obviously Roba is the master!) There are Ai girls in the i-th room and their value of charm is 1, 2... Ai, respectively.
Roba will pick out one girl in one room (randomly). Obviously, only N girl could meet Roba in a single day! Every girl has her value of charm. Now Roba wants to know the number of grils whose value of charm is exactly x! So F(Girl_Selected, x) is defined as the number of grils whose value of charm is exactly x in Girl_Selected.
For example, when N = 3, and Roba pick out three grils whose value of charm is 2, 3, 2 respectively, that is to say, Girl_Selected = {2,3,2}, so F({2,3,2}, 2) = 2, F({2,3,2},3) = 1, F({2,3,2},1) = 0.
Now Roba has Q queries. Each query will be one of the following operations:
1 val : Output the sum of F(Girl_Selected _possible_way, val) for all possible combination. As we know, there must be different ways for Roba to pick out the N grils in a single day! Since the answer may be huge, you should output the answer mod P.
2 pos val : rearrange room pos from ( Apos ) to val, which means Roba maybe sometimes Friends Old and New! After arrangement, val grils in room pos and their value of charm is 1,2,… val respectively ! Note that 1<=val<=10⁹ and 0<=pos<N.

The first line is an integer T indicates the number of the test cases. (T <= 40)
Each case begins with one line containing three integers N (1<=N<=10⁵), P (2 <= P <= 10⁹, P is a prime) and Q(1<= Q <= 10⁵), representing the number of rooms of palace of “Hou”, the mod number and the number of queries respectively. Then one line contains N numbers, the i-th number indicating the initial Ai. In the next Q line, each line contains one operation fits the description. (1 <= Ai <= 10⁹)

Output one line for each type-1 query.

1
4 7 5
1 2 3 4
1 2
2 0 7
1 4
2 0 5
1 3

5
3
3

Hint: If you solve this problem, Roba will give you some grils in the palace of “Hou”!

code6 && yayamao

ACM-DIY Group Contest 2011 Spring