ENG  RUS Timus Online Judge Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

## 1560. Elementary Symmetric Functions

Ограничение времени: 4.0 секунды
Ограничение памяти: 64 МБ
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: You should compute their values modulo prime P.

### Исходные данные

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.

### Результат

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.

### Пример

исходные данныерезультат
```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
```
Источник задачи: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007