CF1906F Maximize The Value

You are given a one-based array consisting of $ N $ integers: $ A_1, A_2, \cdots, A_N $ . Initially, the value of each element is set to $ 0 $ . There are $ M $ operations (numbered from $ 1 $ to $ M $ ). Operation $ i $ is represented by $ \langle L_i, R_i, X_i \rangle $ . If operation $ i $ is executed, all elements $ A_j $ for $ L_i \leq j \leq R_i $ will be increased by $ X_i $ . You have to answer $ Q $ independent queries. Each query is represented by $ \langle K, S, T \rangle $ which represents the following task. Choose a range $ [l, r] $ satisfying $ S \leq l \leq r \leq T $ , and execute operations $ l, l + 1, \dots, r $ . The answer to the query is the maximum value of $ A_K $ after the operations are executed among all possible choices of $ l $ and $ r $ .

The first line consists of two integers $ N $ $ M $ ( $ 1 \leq N, M \leq 100\,000 $ ). Each of the next $ M $ lines consists of three integers $ L_i $ $ R_i $ $ X_i $ ( $ 1 \leq L_i \leq R_i \leq N; -100\,000 \leq X_i \leq 100\,000 $ ). The following line consists of an integer $ Q $ ( $ 1 \leq Q \leq 100\,000 $ ). Each of the next $ Q $ lines consists of three integers $ K $ $ S $ $ T $ ( $ 1 \leq K \leq N; 1 \leq S \leq T \leq M $ ).

For each query, output in a single line, an integer which represent the answer of the query.

Explanation for the sample input/output #1 For query $ 1 $ , one of the solutions is to execute operation $ 4 $ and $ 5 $ . For query $ 2 $ , one of the solutions is to execute operation $ 4 $ , $ 5 $ , and $ 6 $ . For query $ 3 $ , the only solution is to execute operation $ 3 $ . For query $ 4 $ , the only solution is to execute operation $ 1 $ . For query $ 6 $ , the only solution is to execute operation $ 2 $ .