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$互不相等。