다다스와 쿼리

길이 $N$의 목표 수열 $A=[A_1,A_2,\cdots,A_N]$이 주어진다.

길이 $N$의 작업 수열 $B=[B_1,B_2,\cdots,B_N]$를 생각하자. 처음에는 모든 $B_i$가 $0$이다. 다음 시행을 원하는 만큼 할 수 있다.

• 두 정수 $l,r$을 골라 $1\le l\le r\le N$을 만족하게 한다.
• 정수 $y$를 $1$ 또는 $X$ 중 하나로 고른다.
• 모든 $l\le i\le r$에 대해 $B_i$에 $y$를 더한다.

작업 수열 $B$를 목표 수열 $A$와 같게 만드는 데 필요한 시행 횟수의 최솟값을 $A$의 비용이라고 하자.

단순히 비용을 구하는건 너무 쉽다고 생각한 다다스는 $Q$개의 업데이트 쿼리를 추가하기로 했다. 각 쿼리는 목표 수열 $A$의 원소 하나를 새로운 값으로 바꾼다. 각 쿼리가 적용된 직후 현재 목표 수열 $A$의 비용을 구하여라.

각 쿼리의 비용을 계산할 때 작업 수열 $B$는 항상 모든 원소가 $0$인 상태에서 시작한다. 이전 쿼리에서 수행한 시행은 다음 쿼리로 이어지지 않는다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ Q\ X$ $A_1\ A_2\ \cdots\ A_N$ $p_1\ v_1$ $p_2\ v_2$ $\vdots$ $p_Q\ v_Q$

$j$번째 쿼리는 $A_{p_j}$를 $v_j$로 바꾼다.

각 테스트 케이스마다 $Q$개의 줄을 출력한다.

$j$번째 줄에는 $j$번째 쿼리를 적용한 직후 현재 목표 수열 $A$의 비용을 출력한다.

• $1\le T\le 200\,000$.
• $1\le N,Q\le 200\,000$.
• $2\le X\le 50$.
• $0\le A_i\le 10^9$ ($1\le i\le N$).
• $1\le p_j\le N$ ($1\le j\le Q$).
• $0\le v_j\le 10^9$ ($1\le j\le Q$).
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.
• 모든 테스트 케이스에 대한 $Q$의 합은 $200\,000$ 이하이다.