小青鱼走在重（zhòng）庆市的街上，突然人群中钻出一个火星人，他要求重庆市选出一支队伍参加 UOI。

重庆市有 $n$ 名 OI 选手，他们都是重量级的。第 $i$ 名选手有攻击力 $a_i$，防御力 $b_i$ 和实力 $c_i$，满足 $a_i\ge b_i$，保证任意两名选手防御力不同。

火星人规定的选拔方式，自然和地球人的传统选拔方式不一样。在火星人的要求下，队伍要按如下方式选拔：

• 首先，确定三个数 $l,r,k$，队伍将从第 $l$ 到第 $r$ 个人中选出 $k$ 个组成。

• 排在前 $k$ 个的选手为初始的队伍，即第 $l,l+1,\dots ,l+k-1$ 名选手。

• 接下来，后面的选手按照 $l+k,l+k+1,\dots ,r$ 的顺序依次考虑，对于每名选手 $i$：

  • 若存在一个当前在队伍中的选手 $j$ 满足 $b_j\le a_i$，则 $i$ 会把 $j$ 放逐，使得 $j$ 退出队伍，$i$ 进入队伍。若有多个符合条件的 $j$，则 $b_j$ 最小者会被放逐。

  • 否则，$i$ 会放逐自己，什么也不会发生。

• 所有人考虑完后，就得到了最终的队伍成员名单。

选拔一共进行了 $q$ 轮，每轮给定不同的 $l,r,k$，求按照上述规则选 $k$ 名选手组成队伍，队伍成员的实力 $c_i$ 之和。

输入格式

第一行：两个整数 $n,q$。

第二行：$n$ 个整数 $a_1,\dots ,a_n$。

第三行：$n$ 个整数 $b_1,\dots ,b_n$。

第四行：$n$ 个整数 $c_1,\dots ,c_n$。

接下来 $q$ 行：每行三个整数 $l,r,k$。

输出格式

对于每轮选拔，输出一行一个整数表示答案。

样例一

input

5 3
4 4 3 5 5
4 2 3 1 5
1 10 100 1000 10000
1 4 2
2 5 2
1 5 3

output

1001
10100
10101

explanation

第一次询问：最开始 $1,2$ 在队伍，$3$ 放逐了 $2$，然后 $4$ 放逐了 $3$。

第二次询问：最开始 $2,3$ 在队伍，$4$ 放逐了 $2$，然后 $5$ 放逐了 $4$。

第三次询问：最开始 $1,2,3$ 在队伍，$4$ 放逐了 $2$，然后 $5$ 放逐了 $4$。

样例二/三/四

见附件下载，它们分别对应子任务 1,3,5

数据范围

对于全部数据：$1\le n,q\le 5\times {10}^5,1\le a_i,b_i\le n,1\le c_i\le {10}^9,1\le l\le r\le n,1\le k\le r-l+1$，保证任意两名选手防御力不同。

时间限制：$3\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$