题目描述

DX3906星系，Melancholy星上，我在勘测这里的地质情况。 我把这些天来已探测到的区域分为$N$组，并用二元组$(D,V)$对每一组进行标记：其中$D$为区域的相对距离，$V$为内部地质元素的相对丰富程度。 在我的日程安排表上有$Q$项指派的计划。每项计划的形式是类似的，都是“对相对距离$D$在$[L,R]$之间的区域进行进一步的勘测，并在其中有次序地挑出K块区域的样本进行研究。”采集这K块的样品后，在实验中它们的研究价值即为这$K$块区域地质相对丰富程度$V$的乘积。 我对这$Q$项计划都进行了评估：一项计划的评估值$P$为所有可能选取情况的研究价值之和。 但是由于仪器的原因，在一次勘测中，这其中V最小的区域永远不会被选取。 现在我只想知道这$Q$项计划的评估值对$2^{32}$取模后的值。特殊地，如果没有$K$块区域可供选择，评估值为$0$。

输入

第一行给出两个整数，区域数$N$与计划数$Q$。 第二行给出$N$个整数，代表每一块区域的相对距离$D$。 第三行给出$N$个整数，代表每一块区域的内部地质元素的相对丰富程度$V$。 接下来的$Q$行，每一行$3$个整数，代表相对距离的限制$L,R$，以及选取的块数$K$。

输出

输出包括$Q$行，每一行一个整数，代表这项计划的评估值对$2^{32}$取模后的值。

输入样例

5 3
5 4 7 2 6
1 4 5 3 2
6 7 1
2 6 2
1 8 3

输出样例

5
52
924

提示

【样例解释】 第一次被勘测区域的$V$值有$\{2,5\}$，而能够被选取只有$\{5\}$。 第二次被勘测区域的$V$值有$\{1,2,3,4\}$，能够被选取的有$\{2,3,4\}$，评估值为$2!*(2*3+3*4+2*4)=52$。 第三次被勘测区域的$V$值有$\{1,2,3,4,5\}$，能够被选取的有$\{2,3,4,5\}$，评估值为$3!*(2*3*4+2*3*5+2*4*5+3*4*5)=924$。 【数据规模】 对于30%的数据，$K=1$。 对于60%的数据，$1≤K≤2$。 对于80%的数据，$1≤K≤3$。 对于100%的数据，$1≤K≤6，1≤N,Q≤10^5，1≤D,V≤10^9，1≤L≤R≤10^9$。 数据保证所有区域的$D$与$V$互不相等。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。