У деоници за разврставање делова у кутије познате крагујевачке фабрике аутомобила, одлучено је да се због повољности XOR-робота, они убаце на место неких стандардних робота додавача. XOR-роботи додају део у кутију ако се у њој налази паран број делова, а узимају део из ње уколико се у њој налази непаран број делова, док стандардни роботи додавачи увек додају део у кутију. Као што то обично бива у фабрикама аутомобила, ови роботи се налазе дуж покретне траке, има их \(N\) и нумерисани су редом од \(1\) до \(N\). Кутије се на покретну траку убацују и скидају са ње на произвољним местима и са произвољним бројем делова који су већ у њој. Пре замене неких од старих робота са новим роботима, било је лако предвидети са колико делова ће кутија изаћи са траке ако је убацимо на позицији \(L\) а скинемо након позиције \(R\), али сада то није толико лако, што управницима фабрике представља значајан проблем, па су вас замолили да напишете програм који решава њигов проблем.

Опис улаза

У првом реду се уносе бројеви \(N\) и \(Q\), број робота на покретној траци као и број упита. У следећем реду се уноси низ \(s\) од \(N\) карактера. У овом низу се налазе искључиво карактери ‘+’ и ‘^’, који редом представљају роботе додаваче и XOR-роботе. У наредних \(Q\) редова се налазе по три броја: \(L\), \(R\) и \(X\), који представљају упит следећег типа: ако ставимо кутију која иницијално има \(X\) делова у себи на позицију пре робота нумерисаног са \(L\), а скинемо је након робота нумерисаног са \(R\) (дакле кутија ће проћи поред \(R - L + 1\) робота), колико делова ће бити у њој након тога?

Опис излаза

Исписати \(Q\) бројева који представљају одговоре на задате упите.

Пример

Улаз

11 3
^^++^+^+++^
2 3 5
2 3 6
1 11 3

Излаз

5
8
6

Ограничења

\[N, Q \le 2 \times 10^5\]

\[1 \le L \le R \le N\]

\[X \le 10^9\]

Подзадаци

• (10 поена): На покретној траци се налазе само роботи додавачи (у низу се налазе само карактери ‘+’).
• (10 поена): \(N, Q \le 2000\).
• (20 поена): На покретној траци се налазе само XOR-роботи (у низу се налазе само карактери ‘^’).
• (30 поена): На покретној траци се налази највише \(500\) XOR-робота.
• (30 поена): Нема додатних ограничења.