ENG  RUSTimus 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:
Problem illustration
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