2077年，康陶公司准备在zufe举行Kangtao程序设计竞赛。
参赛的候选人有$n$人，编号为$1,2,...n$，第$i(1 \le i \le n)$个人的程序设计能力为$a_i$,且对任意$1 \le i < j \le n$ ,有$a_i < a_j$。
已知参赛选手是候选人的一个子串$[l,r]$,即$l,l+1,...,r$。zufe最强程序员zjh的编号为$k$，由于zjh被入选为参赛选手，因此$l \le k \le r$。但是zjh觉得自己太菜了，因此他首先随机选择了一个整数$m(0 \le m\le \lfloor (r-l)/2 \rfloor)$ ,然后在参赛选手中随机选择$2m$个人来当自己的队友(加上自己有$2m+1$个人)。但是zjh不希望自己显得太菜，因此他要求自己的能力在$2m+1$个人中是中位数。现在zjh想知道自己与队友能力之和的期望。
遗憾的是，$l,r,k$有$q$种可能的情况，需要你一一帮助zjh求出。答案可能很大，请对$998244353$取模。
第一行给出$n,q(1 \le n,q \le 10^5)$
第二行给出$n$个正整数,$a_1,a_2,...,a_n$ ,($1 \le a_i \le 10^9$),保证$a_i$是个递增数组。
之后的$q$行,每行包含三个整数$l,r,k(1\le l \le k \le r \le n)$
5 2
2 3 5 7 8
1 5 3
2 4 215
499122178
第一个询问，$m$可以为0或1或2
$m$=0时，zjh此时没有队友,期望为$a_k$=5
$m$=1时，zjh可以选择编号为(1,4),(1,5),(2,4),(2,5)作为自己队友，此时期望为(14+15+15+16)/4=15
$m$=2时，zjh只能全选，期望为25
综上 总的期望为(5+15+25)/3=15
第二个询问，m可以为0或1
$m$=0时，zjh没有队友，期望为3
$m$=1时，zjh无法选择，期望为0
综上,总的期望为(3+0)/2=3/2 , 而3在乘以2在模$998244353$意义下的乘法逆元后得到499122178。