题目描述

西瓜王 xgw 最近喜欢上了玩星际争霸，很神的他尤其喜欢玩神族。有一天他生产了非常多的高阶圣堂和黑暗圣堂，并把他们排成了一条直线。

但是他觉得这些东西奇形怪状的很不好看，于是他想把他们全都变成末日执政官和黑暗执政官那样的圆圆的像西瓜一样的东西。但是他的人口上限不够了……他只能从中选出一些来变成执政官。

但是他玩的星际争霸有点特别，每一个圣堂有一个值 $x_i$，若 $x_i$ 为奇数则他为高阶圣堂，否则为黑暗圣堂。而 $x$ 值越大会使得合成以后的执政官更圆（TAT 实在没啥好说的了）。xgw 自然是想使得 $x$ 值的和最大啦。

xgw 毕竟也是一个王，所以他很任性。他每次会在屏幕上随便框一下（也就是搞一个区间），然后问你这个区间要合成 $k$ 个执政官选出的圣堂的 $x$ 值之和最大值是多少。

P.S. 两个高阶圣堂可以合成一个末日执政官，两个黑暗圣堂可以合成一个黑暗执政官。

输入格式

第一行一个整数 $n$ 表示圣堂的个数。

第二行 $n$ 个整数，表示每个圣堂的 $x$ 值。

第三行一个整数 $T$ 表示 xgw 框了多少次。

接下来 $T$ 行每行三个整数 $l,r,k$ 代表要从 $[l,r]$ 这段区间里选出 $k$ 个圣堂去合成 $\frac{k}{2}$ 个执政官，保证 $k$ 是偶数。

输出格式

输出 $T$ 行，对于 xgw 每框一次输出选出的圣堂的 $x$ 值之和最大值。若没有可行的选择方案则输出 -1。

样例

5
7 5 3 4 2
1
1 5 4

18

数据规模与约定

对于 $100\%$ 的数据：$N,M\le 3\times 10^5$，$x_i\le 10^9$。