← 返回题目列表

Codeforces · 1786/A2

A2. 交替牌组(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。在此版本中,卡片有两种颜色。

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