兄弟矿业：产值调整模拟

题目描述

偏远小镇的 兄弟矿业 拥有三座矿山：金矿、银矿、铜矿。 它们的当前产值分别为非负整数 A、B、C。

公司每年执行一次产值调整，三座矿山 同时更新，规则如下（向下取整）：

• 金矿新产值 $A' = \left\lfloor \dfrac{B + C}{2} \right\rfloor$

• 银矿新产值 $B' = \left\lfloor \dfrac{A + C}{2} \right\rfloor$

• 铜矿新产值 $C' = \left\lfloor \dfrac{A + B}{2} \right\rfloor$

三兄弟计划连续执行 K 次调整。 请计算执行 K 次后 (A, B, C) 的最终值。

输入格式

第一行包含一个整数 T，表示测试用例数量。

接下来 T 行，每行包含四个整数 A B C K，表示初始产值与调整次数。

输出格式

对每个测试用例输出一行，包含三个整数 A B C，表示执行 K 次调整后的结果，用空格分隔。

样例输入

2
10 20 30 1
5 5 5 3

样例输出

25 20 15
5 5 5

数据范围

• 30%： 1 ≤ T ≤ 100，0 ≤ A, B, C ≤ 10^5，1 ≤ K ≤ 10^5
• 100%： 1 ≤ T ≤ 10^5，0 ≤ A, B, C ≤ 10^9，1 ≤ K ≤ 10^9