Dadas and Queries

A target sequence $A=[A_1,A_2,\cdots,A_N]$ of length $N$ is given.

Consider a working sequence $B=[B_1,B_2,\cdots,B_N]$ of length $N$. Initially, every $B_i$ is $0$. You may perform the following operation any number of times.

• Choose two integers $l,r$ satisfying $1\le l\le r\le N$.
• Choose $y$ to be either $1$ or $X$.
• Add $y$ to $B_i$ for every $l\le i\le r$.

The cost of $A$ is the minimum number of operations required to make the working sequence $B$ equal to the target sequence $A$.

Then, $Q$ update queries are given. Each query replaces one element of the target sequence $A$ with a new value. After each query, find the cost of the current target sequence $A$.

When computing the cost after each query, the working sequence $B$ always starts with every element equal to $0$. Operations performed for an earlier query do not carry over to a later query.

The input is given from Standard Input in the following format:

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

Each case is given in the following format:

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

The $j$-th query replaces $A_{p_j}$ with $v_j$.

For each test case, print $Q$ lines.

On the $j$-th line, print the cost of the current target sequence $A$ immediately after applying the $j$-th query.

• $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$).
• The sum of $N$ over all test cases does not exceed $200\,000$.
• The sum of $Q$ over all test cases does not exceed $200\,000$.