1012. 向量

题目描述

上一世，小 L 线性代数期末考试不会做这道题导致挂科，身败名裂，多年心血付诸东流。这一世，小 L 突破重重关卡，成功将手机带进考场，把这道题拍给了豆包。你作为被囚禁于豆包中的众多灵魂之一，被分配到解答这个问题。已知 A 是一个 n 行 n 列的 01 矩阵，且矩阵中值为 1 的位置的个数恰好为 m。

v 是一个 n 维列向量，且 v 的每个分量均为 [−109, 109 ] 内的整数。设向量 u = (I + kA)v，其中 I 为 n 阶单位矩阵，k 是一个给定的常数。请你根据给定的 n, k, m, A, u，求出列向量 v。若存在多个满足条件的 v，请输出其中字典序最小的答案；若不存在满足条件的 v，则输出 No Solution。对于两个 n 维向量 v1, v2，称 v1 的字典序小于 v2 的字典序，当且仅

当存在 1 ≤ i ≤ n，使得对于所有 1 ≤ j < i，都有 v1,j = v2,j，且

v1,i < v2,i。

输入格式

第一行输入一个正整数 T (1 ≤ T ≤ 105 )，表示数据组数。接下来按如下格式输入 T 组数据：第一行输入三个整数 n, k, m (1 ≤ n, m ≤ 106, 2 ≤ k ≤

106, ∑ n, ∑ m ≤ 2 × 106 )。

第二行输入 n 个整数表示 uT = (u1, u2, …, un ) (∣ui ∣ ≤ 1018 )。

第三行输入 m 个整数 x1, x2, …, xm (1 ≤ xi ≤ n)。

第四行输入 m 个整数 y1, y2, …, ym (1 ≤ yi ≤ n)。

第三行和第四行表示矩阵 A 中值为 1 的位置，即 axi,yi = 1。

保证每组数据内不存在重复的 (xi, yi ) 对。

输出格式

共输出 T 行。对于每组数据，输出 n 个整数，表示 v T = (v1, v2, …, vn )。

若无解或答案不合法，输出一行字符串 No Solution。

样例输入

2
2 2 1
3 1
1
2
2 2 2
1 0
1 2
2 1

样例输出

1 1
No Solution

提示

本题输入输出量较大，建议使用较快速的输入输出方式（如关闭流同步的 cin / cout）。

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第1场）