题目描述

这是该问题的困难版本。在本版本中，卡牌有两种颜色。

Alice 有 $n$ 张卡牌，每张卡牌要么是黑色，要么是白色。卡牌按顺序叠成一叠，颜色交替排列，且最上面一张是白色。Alice 按如下顺序将卡牌从牌堆顶部分发给自己和 Bob：先给自己一张，再给 Bob 两张，再给 Bob 三张，再给自己四张，再给自己五张，再给 Bob 六张，再给 Bob 七张，再给自己八张，依此类推。也就是说，在第 $i$ 步，Alice 会将牌堆顶的 $i$ 张卡牌分发给某一位玩家；第一步时给自己，然后每两步更换一次分发对象。当某一步剩余卡牌不足 $i$ 张时，Alice 会将剩下的所有卡牌都分发给当前玩家，分发过程结束。

这是在有很多卡牌的情况下，Alice 的前几步操作示意图。请问最后 Alice 和 Bob 各自拥有多少张白色卡牌和黑色卡牌？

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 200$），表示测试用例的数量。

接下来每组测试用例占一行，包含一个整数 $n$（$1 \le n \le 10^6$），表示卡牌的数量。

输出格式

对于每组测试用例，输出四个整数，依次表示：Alice 拥有的白色卡牌数、Alice 拥有的黑色卡牌数、Bob 拥有的白色卡牌数、Bob 拥有的黑色卡牌数。

说明/提示

由 ChatGPT 4.1 翻译

样例

5
10
6
17
8
1000000

3 2 2 3
1 0 2 3
6 4 3 4
2 1 2 3
250278 249924 249722 250076