Random Sums
Турнир за Купата на Декана, 2011
Time Limit: 2s, Memory Limit: 64MiB
Поради сложността на задачата няма да има готино условие. Само ще кажем, че тази задача е за Ели.

Дадени са N на брой числа H1, H2, ..., HN. След това се изпълняват Q заявки, които могат да са:
  1. Добави ново число Xi в редицата.
  2. Сортирай всички числа (първоначалните и добавените до сега) и намери сумата на тези с индекси Si1, Si2, Si3, ..., SiK.
Индексите, които трябва да влязат в сумата при заявка от тип B, се задават чрез псевдо-случайна редица, определена от четири цели числа К, F, A, B. Нека по време на заявката имаме M числа (това са началните и евентуално добавените на предходни заявки). Ще питаме за сумата на К индекса от сортираната редица (потенциално някои от тях могат да се повтарят). Първият индекс е остатъкът на F при деление на М. Всеки следващ се образува, като предходният се умножи по A, после се прибави B и се вземе остатъка на резултата, при деление на M. Тоест:
  1. Si1 = F % M
  2. Sik = (Sik-1 * A + B) % M, за k = 2, 3, ..., K.
Забележете, че индексирането в сортираните числа започва от 0; тоест 0 ≤ Sik < M.
Вход
На първия ред на стандартния вход са зададени целите числа N и Q. Следва ред с N цели числа H1, H2, ..., HN. Следват Q на брой реда. i-тият от тях започва с главна латинска буква: 'A' за заявкa от тип A и 'B' за заявкa от тип B. Ако заявката е от тип A, то на същия ред ще има само още едно цяло число Xi – новото число, което добавяме. Ако пък заявката е от тип B, на същия ред след типа ще бъдат зададени четирите цели числа Ki, Fi, Ai, Bi.
Изход
На стандартния изход изведете по един ред за всяка заявка от тип B, съдържащ едно цяло число - търсената сума.
Ограничения
  • 1 ≤ N, Q ≤ 100,000
  • 1 ≤ Ki, Fi, Ai, Bi ≤ 1,000
  • 1 ≤ Hi, Xi ≤ 1,000,000,000
Примерен Вход Примерен Изход
2 3 42 13 B 2 2 1 1 A 17 B 5 2 5 6 55 160
10 13 42 13 7 11 5 666 13 17 20 6 B 3 6 7 8 B 13 1 11 9 A 23 B 13 1 11 9 A 23 A 8 B 3 3 3 3 B 7 17 9 11 A 12 B 1 8 3 5 A 31 A 28 B 77 17 11 13 64 1477 510 679 99 17 1236
В първия пример първата заявка пита за сумата на числата с индекси 0 и 1, която е 13 + 42 = 55. След втората заявка числата са {13, 17, 42}. Третата заявка пита за сумата на числата с индекси 2, 1, 2, 1, и 2, която е 42 + 17 + 42 + 17 + 42 = 160.
Мрън!