만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

가치 최대화

시간 제한2초메모리 제한1024 MB

요약
위치 K에 대해, 구간 [S, T] 안의 연속된 연산 l부터 r까지 중 K를 포함하는 연산의 X 합이 가장 큰 값을 구합니다.
난이도

보통10점 중 7점

유형
세그먼트 트리, 누적 합, 구간
정답자
아직 제출이 없습니다

문제

길이가 NN인 1-based 정수 배열 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 주어진다. 처음에 모든 원소의 값은 00이다.

MM개의 연산이 있으며 1번부터 MM번까지 번호가 붙어 있다. 연산 ii는 ⟨Li,Ri,Xi⟩\langle L_i, R_i, X_i \rangle로 표현된다. 연산 ii를 실행하면 Li≤j≤RiL_i \le j \le R_i인 모든 AjA_j에 XiX_i가 더해진다.

QQ개의 질의에 답해야 하며, 각 질의는 서로 독립이다. 질의는 ⟨K,S,T⟩\langle K, S, T \rangle로 표현되며, S≤l≤r≤TS \le l \le r \le T를 만족하는 구간 [l,r][l, r]을 고른 뒤 연산 l,l+1,…,rl, l+1, \dots, r을 순서대로 실행하는 작업을 뜻한다. 답은 가능한 모든 ll, rr의 선택에 대해 연산을 실행한 후 AKA_K 값의 최댓값이다.

입력

첫 줄에 두 정수 NN과 MM이 주어진다 (1≤N,M≤100 0001 \le N, M \le 100\,000).

다음 MM개의 줄에는 세 정수 LiL_i, RiR_i, XiX_i가 주어진다 (1≤Li≤Ri≤N1 \le L_i \le R_i \le N; −100 000≤Xi≤100 000-100\,000 \le X_i \le 100\,000).

다음 줄에는 정수 QQ가 주어진다 (1≤Q≤100 0001 \le Q \le 100\,000).

다음 QQ개의 줄에는 세 정수 KK, SS, TT가 주어진다 (1≤K≤N1 \le K \le N; 1≤S≤T≤M1 \le S \le T \le M).

출력

각 질의의 답을 한 줄에 하나씩 출력한다.

예제2

  1. 예제 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
    예상 출력
    100
50
0
0
-20

  2. 예제 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
    예상 출력
    3
3
4
3
0
-2