CF1786A2.Alternating Deck (hard version)

This is a hard version of the problem. In this version, there are two colors of the cards.

Alice has $n$ cards, each card is either black or white. The cards are stacked in a deck in such a way that the card colors alternate, starting from a white card. Alice deals the cards to herself and to Bob, dealing at once several cards from the top of the deck in the following order: one card to herself, two cards to Bob, three cards to Bob, four cards to herself, five cards to herself, six cards to Bob, seven cards to Bob, eight cards to herself, and so on. In other words, on the $i$-th step, Alice deals $i$ top cards from the deck to one of the players; on the first step, she deals the cards to herself and then alternates the players every two steps. When there aren't enough cards at some step, Alice deals all the remaining cards to the current player, and the process stops.

First Alice's steps in a deck of many cards.

How many cards of each color will Alice and Bob have at the end?

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

爱丽丝有 $n$ 张卡片，每张卡片要么是黑色，要么是白色。这些卡片以颜色交替的方式叠放在一副牌中，且最上面一张为白色卡片。爱丽丝将这些卡片依次发给自己和鲍勃：每次从牌堆顶部发出若干张卡片，发牌顺序如下：第 1 次发 1 张给自己，第 2 次发 2 张给鲍勃，第 3 次发 3 张给鲍勃，第 4 次发 4 张给自己，第 5 次发 5 张给自己，第 6 次发 6 张给鲍勃，第 7 次发 7 张给鲍勃，第 8 次发 8 张给自己，依此类推。换言之，在第 $i$ 步，爱丽丝从牌堆顶部发出 $i$ 张卡片给其中一名玩家；第一步发给自己，之后每两步轮换一次发牌对象。若某一步时剩余卡片不足 $i$ 张，则将所有剩余卡片全部发给当前应得的玩家，过程随即结束。

一副大量卡片的牌堆中，爱丽丝前几步的发牌示意图。

最终，爱丽丝和鲍勃各自获得的每种颜色的卡片各有多少张？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 200$). The description of the test cases follows

The only line of each test case contains a single integer $n$ ($1 \le n \le 10^6$) — the number of cards.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 200$）。随后是测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$1 \le n \le 10^6$）—— 卡片的数量。

For each test case print four integers — the number of cards in the end for each player — in this order: white cards Alice has, black cards Alice has, white cards Bob has, black cards Bob has.

对于每个测试用例，按以下顺序输出四个整数——每位玩家最终拥有的卡片数量：Alice 拥有的白色卡片数、Alice 拥有的黑色卡片数、Bob 拥有的白色卡片数、Bob 拥有的黑色卡片数。