{"raw_statement":[{"iden":"statement","content":"小 E 正在做一道经典题：\n\n给定一个长度为 $n$ 的序列 $a$ 和 $q$ 个操作，操作共有 $2$ 种类型：\n\n+ $\\tt{1~l~r~x}$：对于所有 $l\\le i\\le r$，$a_i\\leftarrow a_i+x$。\n+ $\\tt{2~l~r~x}$：对于所有 $l\\le i\\le r$，$a_i\\leftarrow \\max(a_i,x)$。\n\n题目要求输出所有操作结束后的最终序列 $a'$。\n\n小 E 迅速写了一份代码提交，但是发现，由于宇宙射线的影响，输入数据出现了一些小问题。具体地，对于所有 $2$ 操作，操作中给出的 $x$ 均被丢失了，也就是说，输入数据中的 $2$ 操作只剩下了 $\\tt{2~l~r}$。输出数据则没有问题。小 E 现在想要通过剩余的数据恢复原来的输入数据，请你帮助他完成这个任务。\n\n当然，可能会有多种合法的输入数据，你需要找到其中任意一种。数据保证有解。"},{"iden":"input","content":"从标准输入读入数据。\n\n**本题有多组测试数据。**\n\n第一行一个正整数 $T$，表示数据组数。\n\n对于每组测试数据，第一行两个非负整数 $n,q$。\n\n第二行 $n$ 个整数，表示初始序列 $a_1,a_2,\\ldots,a_n$。\n\n接下来 $q$ 行，每行一次操作，形如 $\\tt{1~l~r~x}$ 或 $\\tt{2~l~r}$。\n\n接下来一行 $n$ 个整数，表示最终序列 $a_1',a_2',\\ldots,a_n'$。"},{"iden":"output","content":"输出到标准输出。\n\n**本题开启自定义校验器（Special Judge）。**\n\n对于每组测试数据，设共有 $q_2$ 个 $2$ 操作，输出一行 $q_2$ 个整数，第 $i$ 个整数表示第 $i$ 次 $2$ 操作中所给出的 $x$ 的值。\n\n你需要保证 $-10^{15}\\le x\\le 10^{15}$。"},{"iden":"note","content":"**【样例 1 解释】**\n\n所有合法输出需要满足：第 $1$ 个数 $\\le3$，第 $2$ 个数恰好为 $20$。\n\n**【样例 2】**\n\n见选手文件中的 `restore/restore2.in` 与 `restore/restore2.ans`。\n\n**【样例 3】**\n\n见选手文件中的 `restore/restore3.in` 与 `restore/restore3.ans`。\n\n\n***\n\n**【数据范围】**\n\n记 $q_2$ 为单组数据内 $2$ 操作的个数，$\\sum n$ 为单个测试点内所有 $n$ 的和，$\\sum q$ 为单个测试点内所有 $q$ 的和。\n\n对于 $20\\%$ 的数据，保证 $n,q\\le50$，$\\sum n,\\sum q\\le1~000$。\n\n对于 $40\\%$ 的数据，保证 $n,q\\le1~000$，$\\sum n,\\sum q\\le10^5$。\n\n对于另外 $20\\%$ 的数据，保证 $l=1,r=n$。\n\n对于另外 $20\\%$ 的数据，保证 $q_2\\le100$。\n\n对于 $100\\%$ 的数据，保证 $1\\le T\\le 100$，$1\\le n,q\\le 10^5$，$1\\le\\sum n,\\sum q\\le 3\\times10^5$，$-10^9\\le a_i,x\\le 10^9$，$-10^{15}\\le a_i'\\le10^{15}$， $q_2\\ge1$。\n\n\n***\n\n**【校验器】**\n\n\n本题样例文件较大，无法在附件中下载，请在选手文件中查看。\n\n为了方便测试，在 $\\texttt{restore}$ 目录下我们下发了 $\\texttt{checker.cpp}$ 文件。你可以编译该文件，并使用它校验自己的输出文件。请注意它与最终评测时所用的校验器并不完全一致，你不需要也不应该关心其代码的具体内容。\n\n编译命令为：\n\n```plain\ng++ checker.cpp -o checker -std=c++14\n```\n\n使用方式为：\n\n```\n./checker <inputfile> <outputfile> <answerfile>\n```\n\n校验器可能会返回以下状态中的其中一种：\n\n+ $\\tt{Accepted}$：表示你的输出完全正确。\n+ $\\tt{Wrong~answer~at~testcase~ x}$：表示你的输出在第 $x$ 个测试数据出错。\n\n***\n\n**【提示】**\n\n本题输入输出量较大，推荐使用较快的输入输出方式。\n\nKDOI 出题组温馨提示：**多测不清空，爆零两行泪。**\n"}],"translated_statement":null,"sample_group":[["1\n5 3\n1 2 3 4 5\n2 3 5\n1 3 4 2\n2 1 1\n20 2 5 6 5\n","3 20"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}