셋이 한 팀

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$