这是问题的困难版本。在此版本中,卡片有两种颜色。
Alice 有 $$$n$$$ 张牌,每张牌要么是黑色的,要么是白色的。这些卡片以白色卡片开始颜色交替的方式堆叠在一副卡片中。爱丽丝向自己和鲍勃发牌,同时从牌堆顶部按以下顺序发几张牌:给自己一张牌,给鲍勃两张牌,给鲍勃三张牌,给她自己四张牌,给她自己五张牌,给鲍勃六张牌,给鲍勃七张牌,给她自己八张牌,等等。换句话说,在第 $$$i$$$ 步中,Alice 将牌堆中的 $$$i$$$ 顶牌发给其中一名玩家;第一步,她给自己发牌,然后每两步轮换一次玩家。当某个步骤没有足够的牌时,爱丽丝将所有剩余的牌发给当前玩家,然后该过程停止。
爱丽丝在一副多张牌中的第一个步骤。
Alice 和 Bob 最后每种颜色各有多少张卡片?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 200$$$)。测试用例的描述如下
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 卡的数量。
输出
对于每个测试用例,打印四个整数 - 每个玩家最终的牌数 - 按以下顺序:爱丽丝有白牌,爱丽丝有黑牌,鲍勃有白牌,鲍勃有黑牌。
示例
输入 #1
5 10 6 17 8 1000000
输出 #1
3 2 2 3 1 0 2 3 6 4 3 4 2 1 2 3 250278 249924 249722 250076