굿즈 마켓

굿즈 마켓이라는 시장이 새로 문을 열었다. 문을 열 때 상점은 $N$개이고, 그 뒤로 새로운 상점이 계속 들어온다. 시장이 넓어서 상점 수에는 제한이 없다.

시장 주인은 임대료를 올릴 수 있다. 한 번 올리면 그 순간 시장에 있는 모든 상점의 임대료가 $K$바트씩 오른다. 두 번의 인상을 모두 겪은 상점은 처음 임대료보다 $2K$바트를 더 낸다. 첫 번째 인상 뒤에 들어와 두 번째 인상만 겪은 상점은 $K$바트를 더 낸다. 상점은 들어온 뒤에 일어난 인상만 적용받는다.

세입자가 너무 많아지면 주인은 임대료가 가장 싼 상점을 하나 내보낸다. 가장 싼 상점이 여럿이면 그중 하나를 내보내며, 어느 쪽을 내보내도 남은 임대료의 합은 같다. 언제 내보낼지는 주인이 정한다.

시장에서 다음 세 종류의 연산이 $M$번 일어난다.

1. 임대료가 $P$바트인 상점이 새로 들어온다.
2. 시장에 있는 모든 상점의 임대료가 $K$바트씩 오른다.
3. 임대료가 가장 싼 상점 하나를 내보낸다. 시장에 상점이 하나도 없으면 아무 일도 일어나지 않는다.

모든 연산이 끝난 뒤 시장에 남은 상점의 수와 그 임대료의 합을 구하시오.

첫째 줄에 질의의 개수 $T$가 주어진다. ($1 \le T \le 20$)

각 질의의 첫째 줄에 세 정수 $N$, $M$, $K$가 주어진다. ($1 \le N, M \le 100{,}000$, $1 \le K \le 100$)

다음 줄에 $N$개의 정수 $X_i$가 주어진다. $X_i$는 상점 $i$의 처음 임대료다. ($1 \le X_i \le 10{,}000{,}000$)

이어지는 $M$개 줄에는 연산의 종류 $A$가 주어진다. $A$가 1이면 같은 줄에 정수 $P$가 함께 주어진다. ($1 \le P \le 10{,}000{,}000$) $A$가 2나 3이면 그 줄에는 정수 하나만 주어진다.

각 질의마다 모든 연산이 끝난 뒤 남은 상점의 수와 임대료의 합을 한 줄에 공백으로 구분해 출력한다.