Поради сложността на задачата няма да има готино условие. Само ще кажем, че тази задача е за Ели.

Дадени са N на брой числа H₁, H₂, ..., H_N. След това се изпълняват Q заявки, които могат да са:

1. Добави ново число X_i в редицата.
2. Сортирай всички числа (първоначалните и добавените до сега) и намери сумата на тези с индекси S_i1, S_i2, S_i3, ..., S_iK.

Индексите, които трябва да влязат в сумата при заявка от тип B, се задават чрез псевдо-случайна редица, определена от четири цели числа К, F, A, B. Нека по време на заявката имаме M числа (това са началните и евентуално добавените на предходни заявки). Ще питаме за сумата на К индекса от сортираната редица (потенциално някои от тях могат да се повтарят). Първият индекс е остатъкът на F при деление на М. Всеки следващ се образува, като предходният се умножи по A, после се прибави B и се вземе остатъка на резултата, при деление на M. Тоест:

1. S_i1 = F % M
2. S_ik = (S_ik-1 * A + B) % M, за k = 2, 3, ..., K.

Забележете, че индексирането в сортираните числа започва от 0; тоест 0 ≤ S_ik < M. На първия ред на стандартния вход са зададени целите числа N и Q. Следва ред с N цели числа H₁, H₂, ..., H_N. Следват Q на брой реда. i-тият от тях започва с главна латинска буква: 'A' за заявкa от тип A и 'B' за заявкa от тип B. Ако заявката е от тип A, то на същия ред ще има само още едно цяло число X_i – новото число, което добавяме. Ако пък заявката е от тип B, на същия ред след типа ще бъдат зададени четирите цели числа K_i, F_i, A_i, B_i. На стандартния изход изведете по един ред за всяка заявка от тип B, съдържащ едно цяло число - търсената сума.

• 1 ≤ N, Q ≤ 100,000
• 1 ≤ K_i, F_i, A_i, B_i ≤ 1,000
• 1 ≤ H_i, X_i ≤ 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