#P18058. Projection

Projection

Projection

给定 nn 维空间中的点 x=(x1,…,xn)\boldsymbol x=(x_1,\ldots,x_n),以及区域

$$S=\left\{\boldsymbol y\in\mathbb R^n:\sum_{i=1}^n y_i^2\le a,\quad |y_i|\le l_i\ (1\le i\le n)\right\}.$$

求 SS 中距离 x\boldsymbol x 最近的点。也就是在这些约束下,最小化

∑i=1n(xi−yi)2.\sum_{i=1}^n(x_i-y_i)^2.

区域包含边界,输入中的 aa 是球半径的平方。

输入格式

第一行整数 TT,1≤T≤3×1041\le T\le3\times10^4。每个用例包含三行:

  • 两个整数 n,an,a,2≤n≤1052\le n\le10^5,1≤a≤1091\le a\le10^9。
  • nn 个整数 x1,…,xnx_1,\ldots,x_n,∣xi∣≤109|x_i|\le10^9。
  • nn 个整数 l1,…,lnl_1,\ldots,l_n,1≤li≤1001\le l_i\le100。

所有用例的 nn 之和不超过 10510^5。

输出格式

对每个用例输出一行 nn 个实数 y1,…,yny_1,\ldots,y_n。

设标准答案的第 ii 个坐标为 yi∗y_i^*,输出必须对所有坐标满足

∣yi−yi∗∣max⁡(1,∣yi∗∣)≤10−6.\frac{|y_i-y_i^*|}{\max(1,|y_i^*|)}\le10^{-6}.

样例

输入:

3
2 25
1 10
4 4
2 25
10 1
4 4
3 6
3 3 3
2 2 2

输出:

1.000000000000000 4.000000000000000
4.000000000000000 1.000000000000000
1.414213562373095 1.414213562373095 1.414213562373095