33546번 - 셋이 한 팀

문제

Note: 이 문제는 C. 둘이 한 팀 문제의 어려운 버전입니다. 두 문제를 모두 읽어보는 것을 권장합니다.

Alice, Bob, Charlie 세 명이 한 팀을 이루어 프로그래밍 대회에 참가하려고 한다.

프로그래밍 대회에 관련된 능력치는 총 $N$개가 있으며, 1ドル$부터 $N$까지의 정수 번호가 붙어 있다. 각 사람의 능력치는 길이 $N$의 정수 수열로 표현할 수 있으며, “팀의 능력치”는 $N$개의 능력치 각각에 대해 개인 능력치의 최댓값을 모두 합한 값이다.

Alice, Bob, Charlie의 $i$번 능력치 값을 각각 $A_i,ドル $B_i,ドル $C_i$ 라고 하면, “팀의 능력치”는 $\sum_{i=1}^{N}{\max(A_i,B_i,C_i)}$ 가 된다.

대회에서 좋은 성적을 거두기 위해, 셋이서 각자 훈련을 진행하려고 한다. 훈련은 총 $Q$번에 걸쳐 진행하는데, 이중 $j$번째 훈련에서는 세 사람 중 한 명의 모든 능력치가 $X_j$ 만큼 증가하게 된다.

각 훈련이 끝난 후 팀의 능력치 값이 얼마인지를 알고 싶다. 이 값을 구하여 보자.

입력

첫 번째 줄에 능력치의 개수 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐, 이 중 $i$번째 줄에는 Alice, Bob, Charlie의 $i$번 능력치의 초깃값을 나타내는 정수 $A_i,ドル $B_i,ドル $C_i$가 공백으로 구분되어 주어진다.

$N+2$번째 줄에 훈련을 한 횟수 $Q$가 주어진다.

$N+3$번째 줄부터 $Q$개의 줄에 걸쳐, 이 중 $j$번째 줄에는 $j$번째 훈련에 대한 정보를 나타내는 문자와 정수 $X_j$가 공백으로 구분되어 주어진다. 아래 세 가지 형식 중 하나로 주어진다.

• A $X_j$: Alice의 모든 능력치 값이 $X_j$만큼 증가한다.
• B $X_j$: Bob의 모든 능력치 값이 $X_j$만큼 증가한다.
• C $X_j$: Charlie의 모든 능력치 값이 $X_j$만큼 증가한다.

출력

총 $Q$개의 줄에 걸쳐, 각 훈련 이후 팀의 능력치 값을 줄마다 정수 하나로 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\le N\le 250,円 000$
• 1ドル\le A_i,B_i,C_i\le 10^6$
• 1ドル\le Q\le 250,円 000$
• 1ドル\le X\le 10^6$

힌트