In this task, you are to read an array of integer numbers (
A[1..
N]) and a sequence
of
M queries of two types:
 Increase A[i] by D.
 Calculate first K + 1 elementary symmetric polynomials of the numbers of
the interval [L..R] (S(0), S(1), S(2), …, S(K)).
Elementary symmetric polynomials of the interval [
L..
R] are given by:
You should compute their values modulo prime P.
Input
The first line consists of three integer numbers: N (size of the array), M (number of queries) and P (prime number)
(1 ≤ N ≤ 80000; 1 ≤ M ≤ 100000; 1000 ≤ P ≤ 10^{9} (prime)).
The second line contains N integer numbers not exceeding 10^{5} by absolute value (the initial values in the array).
The next M lines contain queries. Each query can be either increase or calculation query.
I index delta — increase indexth value by delta (1 ≤ index ≤ N; −10^{5} ≤ delta ≤ 10^{5}).
C left right K — compute S(0), …, S(K) for the interval [left..right] (1 ≤ left ≤ right ≤ N;
1 ≤ K ≤ 4; K ≤ right − left + 1).
All fields in each line are separated by spaces.
Output
For each calculation query print a line consisting of K + 1 numbers — S(0) S(1) … S(K).
These numbers must be nonnegative and less than P.
Sample
input  output 

7 6 1237
0 0 1 1 1 1 1
C 3 3 1
C 1 6 4
I 1 1235
C 1 7 3
I 4 1
C 2 5 4
 1 1
1 4 6 4 1
1 7 20 30
1 4 5 2 0

Problem Source: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007