ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1560. Elementary Symmetric Functions

Time limit: 4.0 second
Memory limit: 64 MB
In this task, you are to read an array of integer numbers (A[1..N]) and a sequence of M queries of two types:
  1. Increase A[i] by D.
  2. 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:
Problem illustration
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 ≤ 109 (prime)).
The second line contains N integer numbers not exceeding 105 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 index-th value by delta (1 ≤ index ≤ N; −105 ≤ delta ≤ 105).
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

inputoutput
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