给定一个由 $$$N$$$ 整数组成的从 1 开始的数组:$$$A_1、A_2、\cdots、A_N$$$。最初,每个元素的值设置为$$$0$$$。
有 $$$M$$$ 操作(编号从 $$$1$$$ 到 $$$M$$$)。操作$$$i$$$由$$$\langle L_i, R_i, X_i \rangle$$$表示。如果执行$$$i$$$操作,则$$$L_i \leq j \leq R_i$$$的所有元素$$$A_j$$$将增加$$$X_i$$$。
您必须回答 $$$Q$$$ 独立查询。每个查询由 $$$\langle K, S, T \rangle$$$ 表示,它表示以下任务。选择满足$$$S \leq l \leq r \leq T$$$的范围$$$[l, r]$$$,并执行操作$$$l, l + 1, \dots, r$$$。查询的答案是$$$l$$$和$$$r$$$所有可能选择中执行完操作后$$$A_K$$$的最大值。
输入
第一行由两个整数 $$$N$$$ $$$M$$$ ($$$1 \leq N, M \leq 100\,000$$$) 组成。
接下来的 $$$M$$$ 行由三个整数 $$$L_i$$$ $$$R_i$$$ $$$X_i$$$ ($$$1 \leq L_i \leq R_i \leq N; -100\,000 \leq X_i \leq 100\,000$$$) 组成。
以下行由整数 $$$Q$$$ ($$$1 \leq Q \leq 100\,000$$$) 组成。
接下来的 $$$Q$$$ 行由三个整数 $$$K$$$ $$$S$$$ $$$T$$$ ($$$1 \leq K \leq N; 1 \leq S \leq T \leq M$$$) 组成。
输出
对于每个查询,在一行中输出一个整数,表示查询的答案。
示例
输入 #1
2 6 1 1 -50 1 2 -20 2 2 -30 1 1 60 1 2 40 2 2 10 5 1 1 6 2 1 6 1 1 3 2 1 3 1 1 2
输出 #1
100 50 0 0 -20
输入 #2
5 3 1 3 3 2 4 -2 3 5 3 6 1 1 3 2 1 3 3 1 3 3 2 3 2 2 3 2 2 2
输出 #2
3 3 4 3 0 -2
注意
示例输入/输出#1 的说明
对于查询$$$1$$$,解决方案之一是执行操作$$$4$$$ 和$$$5$$$。
对于查询$$$2$$$,解决方案之一是执行操作$$$4$$$、$$$5$$$ 和$$$6$$$。
对于查询$$$3$$$,唯一的解决方案是执行操作$$$3$$$。
对于查询$$$4$$$,唯一的解决方案是执行操作$$$1$$$。
对于查询$$$6$$$,唯一的解决方案是执行操作$$$2$$$。