P8862 "KDOI-03" Restore Data

Little E is working on a classic problem: Given a sequence $a$ of length $n$ and $q$ operations, there are $2$ types of operations: + $\tt{1~l~r~x}$: For all $l \le i \le r$, set $a_i \leftarrow a_i + x$. + $\tt{2~l~r~x}$: For all $l \le i \le r$, set $a_i \leftarrow \max(a_i, x)$. The task is to output the final sequence $a'$ after all operations are finished. Little E quickly wrote some code and submitted it, but then found that, due to cosmic rays, the input data had some minor issues. Specifically, for all type $2$ operations, the given $x$ was lost. That is, in the input data, every type $2$ operation only remains as $\tt{2~l~r}$. The output data has no problem. Little E now wants to restore the original input data from the remaining data. Please help him complete this task. Of course, there may be multiple valid original inputs. You only need to find any one of them. The testdata guarantees that a solution exists.

Read from standard input. **This problem has multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case, the first line contains two non-negative integers $n, q$. The second line contains $n$ integers, the initial sequence $a_1, a_2, \ldots, a_n$. The next $q$ lines each contain one operation, in the form $\tt{1~l~r~x}$ or $\tt{2~l~r}$. The next line contains $n$ integers, the final sequence $a_1', a_2', \ldots, a_n'$.

Output to standard output. **This problem uses a Special Judge.** For each test case, suppose there are $q_2$ type $2$ operations in total. Output one line with $q_2$ integers. The $i$-th integer represents the value of $x$ given in the $i$-th type $2$ operation. You must ensure that $-10^{15} \le x \le 10^{15}$.

**[Sample 1 Explanation]** All valid outputs must satisfy: the $1$-st number $\le 3$, and the $2$-nd number is exactly $20$. **[Sample 2]** See `restore/restore2.in` and `restore/restore2.ans` in the contestant files. **[Sample 3]** See `restore/restore3.in` and `restore/restore3.ans` in the contestant files. *** **[Constraints]** Let $q_2$ be the number of type $2$ operations in one test case. Let $\sum n$ be the sum of all $n$ within one test point, and $\sum q$ be the sum of all $q$ within one test point. For $20\%$ of the testdata, $n, q \le 50$, and $\sum n, \sum q \le 1~000$. For $40\%$ of the testdata, $n, q \le 1~000$, and $\sum n, \sum q \le 10^5$. For another $20\%$ of the testdata, $l = 1, r = n$. For another $20\%$ of the testdata, $q_2 \le 100$. For $100\%$ of the testdata, $1 \le T \le 100$, $1 \le n, q \le 10^5$, $1 \le \sum n, \sum q \le 3 \times 10^5$, $-10^9 \le a_i, x \le 10^9$, $-10^{15} \le a_i' \le 10^{15}$, and $q_2 \ge 1$. *** **[Checker]** The sample files for this problem are large and cannot be downloaded as attachments. Please view them in the contestant files. To make testing easier, we provide a `checker.cpp` file in the $\texttt{restore}$ directory. You can compile it and use it to check your output file. Note that it is not exactly the same as the checker used in the final judging, and you do not need to and should not care about the specific code details. The compile command is: ```plain g++ checker.cpp -o checker -std=c++14 ``` Usage: ``` ./checker ``` The checker may return one of the following statuses: + $\tt{Accepted}$: Your output is completely correct. + $\tt{Wrong~answer~at~testcase~ x}$: Your output is wrong on test case $x$. *** **[Hint]** The input and output size of this problem is large, so faster I/O methods are recommended. A warm reminder from the KDOI problem setters: **if you do not clear arrays between test cases, you may get zero points and cry for two lines.** Translated by ChatGPT 5