小红有一条长度为$n×10^{{{{{10}^{10}}^{10}}^{10}}^{10}}$的彩带，彩带的每一个位置都有一个价值，用$a_i$表示。

小红的彩带是由一条长度为$n$的彩带一直循环得到的，因此当$i=n$时，$a_i=a_i-n$。

小红每次会从左往后或从右往左剪一段长度为$x$的彩带，他想知道她每次的下来的彩带的价值之和是多少。

输入描述

第$1$行输入$2$个正整数$n,q(1≤n,q≤2×10^5)$，表示彩带长度，剪彩带次数。

第$2$行输入$n$个正整数$a_i(1≤a_i≤ 10^9)$，表示彩带每一个位置的价值。

接下来$q$行，每行先输入$1$个字符$c$，$c$为‘$L$’说明从左往右剪，$c$为‘$R$’说明从右往左剪，再输入$1$个正整数$x(1≤x≤10^9)$。

输出描述

输出$q$行，每行输出$1$个整数表示答案。

示例 1

输入

6 3
1 1 3 5 1 4
L 2
L 3
R 12

输出

2
10
32

说明

第$1$次剪彩带，剪下来的是$[1,1]$，价值之和为$2$，

第$2$次剪彩带，剪下来的是$[4,5,1]$，价值之和为$10$，

第$1$次剪彩带，剪下来的是$[1,1,4,5,1,4,1,1,4,5,1,4]$，价值之和为$32$。