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?


-----Input-----

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.


-----Output-----

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.


-----Examples-----

Input
5
10
6
17
8
1000000
Output
3 2 2 3
1 0 2 3
6 4 3 4
2 1 2 3
250278 249924 249722 250076


-----Note-----

None

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
from math import sqrt, floor
t = int(input())
for _ in range(t):
	n = int(input())
	x = floor(2 + sqrt(4 + 32 * n)) // 16
	(a_w, a_b) = ((1 + 1 + 4 * x - 4) * x // 2, (0 + 0 + 4 * x - 4) * x // 2)
	(b_w, b_b) = ((2 + 2 + 4 * x - 4) * x // 2, (3 + 3 + 4 * x - 4) * x // 2)
	n -= a_w + a_b + b_w + b_b
	while n:
		nxt = min(n, 1 + 8 * x)
		a_w += (nxt + 1) // 2
		a_b += nxt // 2
		n -= nxt
		if not n:
			break
		nxt = min(n, 5 + 8 * x)
		b_b += (nxt + 1) // 2
		b_w += nxt // 2
		n -= nxt
		x += 1
	print(a_w, a_b, b_w, b_b)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	turns = (1 + math.sqrt(1 + 8 * n)) / 4
	turns = math.ceil(turns)
	a_turns = math.ceil(turns / 2)
	b_turns = math.floor(turns / 2)
	a = (1 + 1 + 8 * (a_turns - 1)) * a_turns // 2
	b = (5 + 5 + 8 * (b_turns - 1)) * b_turns // 2
	gap = (1 + 2 * (turns - 1)) * turns - n
	a_gap = a_turns
	b_gap = b_turns
	last = n - (1 + 2 * (turns - 2)) * (turns - 1)
	if turns % 2 == 0:
		b -= gap
		if last % 2 == 0:
			b_gap -= 1
	else:
		a -= gap
		if last % 2 == 0:
			a_gap -= 1
	a_white = (a + a_gap) // 2
	b_black = (b + b_gap) // 2
	print(a_white, a - a_white, b - b_black, b_black)


import math

def ans(n):
	k = math.floor((2 * n) ** (1 / 2))
	if k * (k + 1) > 2 * n:
		k -= 1
	(ab, aw) = (0, 0)
	(bb, bw) = (0, 0)
	if k % 4 in (1, 2):
		bw += (n - k * (k + 1) // 2) // 2
		bb += n - k * (k + 1) // 2 - (n - k * (k + 1) // 2) // 2
	else:
		ab += (n - k * (k + 1) // 2) // 2
		aw += n - k * (k + 1) // 2 - (n - k * (k + 1) // 2) // 2
	if k % 4 == 1:
		ab += k // 2
		aw += k // 2 + 1
		k -= 1
	elif k % 4 == 2:
		ab += (k - 1) // 2
		aw += (k - 1) // 2 + 1
		bb += k // 2
		bw += k // 2
		k -= 2
	elif k % 4 == 3:
		ab += (k - 2) // 2
		aw += (k - 2) // 2 + 1
		bb += k
		bw += k - 1
		k -= 3
	n_blocks = k // 4
	s = (k * (k + 1) // 4 - n_blocks) // 2
	l = (k * (k + 1) // 4 - n_blocks) // 2 + n_blocks
	ab += s
	aw += l
	bb += l
	bw += s
	return (aw, ab, bw, bb)
n_num = int(input())
for i in range(n_num):
	n = int(input())
	print(*ans(n))


for _ in range(int(input())):
	N = int(input())
	n = int((-1 + (1 + 8 * N) ** 0.5) / 2)
	player = n >> 1 & 1 ^ n % 2
	n -= not n & 1
	(A, B) = ((n - 1 >> 2) + 1, n + 1 >> 2)
	cards = [[A * (2 + (A - 1) * 4) // 2, A * (0 + (A - 1) * 4) // 2], [B * (4 + max((B - 1) * 4, -2)) // 2, B * (3 + max((B - 1) * 4, -3) // 2)]]
	N -= int(n * (n + 1) / 2)
	cards[player][player] += (N >> 1) + (N & 1)
	cards[player][not player] += N >> 1
	print(*cards[0], *cards[1])


import math
t = int(input())
for i in range(t):
	n = int(input())
	last = (1 + math.sqrt(1 + 8 * n)) // 4
	last = int(last)
	if last % 2 == 0:
		last_sum = 1 + (last - 1) * 4
		Sum = int(math.ceil(last / 2) / 2 * (5 + last_sum))
		t = math.ceil(last / 2)
		bob_black = int(t / 2 * (2 * 3 + (t - 1) * 4))
		alice_black = n // 2 - bob_black
		print(n - Sum - alice_black, alice_black, Sum - bob_black, bob_black)
	else:
		last_sum = 1 + (last - 1) * 4
		Sum = int(math.ceil(last / 2) / 2 * (1 + last_sum))
		t = math.ceil(last / 2) - 1
		alice_black = int(t / 2 * (2 * 4 + (t - 1) * 4))
		bob_black = n // 2 - alice_black
		print(Sum - alice_black, alice_black, n - Sum - bob_black, bob_black)


import math
for t in range(int(input())):
	a = int(input())
	n = (1 + (1 + 8 * a) ** (1 / 2)) / 8
	n = int(n)
	aw = 2 * n * n - n
	ab = 2 * n * n - 2 * n
	bw = 2 * n * n
	bb = 2 * n * n + n
	rem = a - (aw + ab + bw + bb)
	if rem <= 8 * n + 1:
		if rem % 2 == 1:
			aw += rem // 2 + 1
			ab += rem // 2
		else:
			aw += rem // 2
			ab += rem // 2
	else:
		aw += 4 * n + 1
		ab += 4 * n
		rem = rem - (8 * n + 1)
		if rem % 2 == 1:
			bb += rem // 2 + 1
			bw += rem // 2
		else:
			bb += rem // 2
			bw += rem // 2
	print(f'{aw} {ab} {bw} {bb} ')


import sys
sys.setrecursionlimit(10 ** 9)
for i in range(int(input())):
	N = int(input())
	n = int((-3 + (9 - 8 * (1 - N)) ** 0.5) / 4)
	w = N - N // 2
	if n % 2 == 1:
		k = n // 2 + 1
		b = k * (8 * k + 2) / 2
		t = (b - k) / 2
		tb = t + k
		a = N - b
		o = w - t
		ob = a - o
	else:
		k = n // 2
		a = k * (8 * k + 10) / 2
		o = (a + k) / 2 + 1
		ob = o - k - 1
		b = N - a - 1
		t = w - o
		tb = b - t
	print(int(o), int(ob), int(t), int(tb), sep=' ')


for _ in range(int(input())):
	n = int(input())
	l = 1
	r = 1000000.0
	while r - l > 1:
		mid = (r + l) // 2
		x = mid + (mid - 1) * mid // 2 * 4
		if x <= n:
			l = mid
		else:
			r = mid
	cnt1 = l // 2 + l % 2
	x = l + (l - 1) * l // 2 * 4
	y = cnt1 + (cnt1 - 1) * cnt1 // 2 * 8
	if l % 2 == 0:
		y += n - x
		if (n - x) % 2 == 1:
			cnt1 += 1
	y = int(y)
	y2 = int((y - cnt1) // 2)
	y1 = y - y2
	z1 = n // 2 + n % 2
	z2 = n - z1
	print(y1, y2, z1 - y1, z2 - y2)


def card(cards):
	A = 0
	B = 0
	A_black = 0
	A_white = 0
	B_black = 0
	B_white = 0
	pt = 1
	count = 0
	while cards > 0:
		if count % 2 == 0:
			if pt > cards:
				A += cards
				cr = cards // 2
				A_black += cr
				A_white += cards - cr
			else:
				A += pt
				cr = pt // 2
				A_black += cr
				A_white += pt - cr
		elif pt > cards:
			B += cards
			cr = cards // 2
			B_white += cr
			B_black += cards - cr
		else:
			B += pt
			cr = pt // 2
			B_white += cr
			B_black += pt - cr
		cards -= pt
		pt += 4
		count += 1
	print(A_white, '', A_black, '', B_white, '', B_black)
n = int(input())
l = []
for i in range(n):
	a = int(input())
	l.append(a)
for cards in l:
	card(cards)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	x = [i * (i + 1) / 2 for i in range(1500)]
	w = bisect_left(x, n) - 1
	if n % 2 == 0:
		black = n / 2
		white = n / 2
	else:
		black = (n - 1) / 2
		white = (n + 1) / 2
	if w % 4 == 0:
		k = w // 4
		ans2 = k * (4 * k + 1)
		ans2b = (2 * k + 1) * k
		ans2w = ans2 - ans2b
		ans1w = white - ans2w
		ans1b = black - ans2b
	elif w % 4 == 1:
		k = w // 4 + 1
		ans1 = k * (4 * k - 3)
		ans1b = (2 * k - 2) * k
		ans1w = ans1 - ans1b
		ans2w = white - ans1w
		ans2b = black - ans1b
	elif w % 4 == 2:
		k = w // 4 + 1
		ans1 = k * (4 * k - 3)
		ans1b = (2 * k - 2) * k
		ans1w = ans1 - ans1b
		ans2w = white - ans1w
		ans2b = black - ans1b
	else:
		k = w // 4 + 1
		ans2 = k * (4 * k + 1)
		ans2b = (2 * k + 1) * k
		ans2w = ans2 - ans2b
		ans1w = white - ans2w
		ans1b = black - ans2b
	print('{} {} {} {}'.format(int(ans1w), int(ans1b), int(ans2w), int(ans2b)))


for _ in range(int(input())):
	n = int(input())
	a_w = 0
	a_b = 0
	b_w = 0
	b_b = 0
	k = 1
	while n > 0:
		a_w += k // 2 + 1
		a_b += k // 2
		n -= k
		if n <= 0:
			a_w += n // 2
			a_b += n // 2 + 1 if n % 2 == 1 else n // 2
			break
		k += 4
		b_w += k // 2
		b_b += k // 2 + 1
		n -= k
		if n <= 0:
			b_w += n // 2 + 1 if n % 2 == 1 else n // 2
			b_b += n // 2
			break
		k += 4
	print(a_w, a_b, b_w, b_b)


import math

def solveA2():
	n = int(input())
	(AW, AB, BW, BB) = (0, 0, 0, 0)
	dealAmt = 1
	turn = 0
	while n >= dealAmt:
		if turn == 0:
			AW += (dealAmt + 1) // 2
			AB += (dealAmt - 1) // 2
		else:
			BW += (dealAmt - 1) // 2
			BB += (dealAmt + 1) // 2
		n -= dealAmt
		dealAmt += 4
		turn = (turn + 1) % 2
	if turn == 0:
		AW += math.ceil(n / 2)
		AB += math.floor(n / 2)
	else:
		BW += math.floor(n / 2)
		BB += math.ceil(n / 2)
	print(AW, AB, BW, BB)

def solveA1():
	n = int(input())
	cards = [0, 0]
	dealAmt = 1
	turn = 0
	while n >= dealAmt:
		cards[turn] += dealAmt
		n -= dealAmt
		dealAmt += 4
		turn = (turn + 1) % 2
	cards[turn] += n
	print(*cards)
t = int(input())
for tc in range(t):
	solveA2()


def sol():
	n = int(input())
	if n == 1:
		print(1, 0, 0, 0)
		return
	(aw, ab, bw, bb) = (1, 0, 0, 0)
	curr = 1
	i = 2
	bo = True
	while curr < n:
		if bo:
			if curr + 2 * i + 1 < n:
				bw += i
				bb += i + 1
				curr += 2 * i + 1
			else:
				val = n - curr
				v1 = (n - curr) // 2
				v2 = val - v1
				bw += v1
				bb += v2
				curr = n
			i += 2
			bo = False
		else:
			if curr + 2 * i + 1 < n:
				ab += i
				aw += i + 1
				curr += 2 * i + 1
			else:
				val = n - curr
				v1 = (n - curr) // 2
				v2 = val - v1
				ab += v1
				aw += v2
				curr = n
			i += 2
			bo = True
	print(aw, ab, bw, bb)
for i in range(int(input())):
	sol()


def solve():
	t = 1
	t = int(input())
	while t:
		t -= 1
		n = int(input())
		aw = 0
		ab = 0
		bw = 0
		bb = 0
		inc = 0
		aTurn = True
		while n >= 4 * inc + 1:
			if aTurn:
				aw += 2 * inc + 1
				ab += 2 * inc
			else:
				bw += 2 * inc
				bb += 2 * inc + 1
			n -= 4 * inc + 1
			inc += 1
			aTurn = not aTurn
		if n != 0:
			if aTurn:
				aw += int(n / 2) + n % 2
				ab += int(n / 2)
			else:
				bw += int(n / 2)
				bb += int(n / 2) + n % 2
		print(aw, ab, bw, bb) if aTurn else print(aw, ab, bw, bb)
solve()


for i in range(int(input())):
	ab = 0
	bb = 0
	bw = 0
	aw = 0
	n = int(input())
	i = 0
	while n > 0:
		if n >= 2 * i + 1:
			aw = aw + i + 1
			ab = ab + i
			n = n - 2 * i - 1
			i = i + 2
			if n >= 2 * i + 1:
				bb = bb + i + 1
				bw = bw + i
				n = n - 2 * i - 1
				i = i + 2
			else:
				bb = bb + (n // 2 + n % 2)
				bw = bw + n // 2
				n = 0
		else:
			aw = aw + n // 2 + n % 2
			ab = ab + n // 2
			n = 0
	print(aw, ab, bw, bb)


for _ in range(int(input())):
	n = int(input())
	(wAlice, bAlice, wBob, bBob) = (0, 0, 0, 0)
	count = 1
	while n > 0:
		if count > n:
			if n % 2 == 0:
				temp = int(n / 2)
				wAlice += temp
				bAlice += temp
			else:
				bAlice += n // 2
				wAlice += n - n // 2
			break
		else:
			bAlice += count // 2
			wAlice += count - count // 2
			n -= count
		count += 4
		if count > n:
			if n % 2 == 0:
				temp = int(n / 2)
				bBob += temp
				wBob += temp
			else:
				wBob += n // 2
				bBob += n - n // 2
			break
		else:
			wBob += count // 2
			bBob += count - count // 2
			n -= count
		count += 4
	print(wAlice, bAlice, wBob, bBob)


import sys
import math
from itertools import accumulate

def read_string():
	return sys.stdin.readline().strip()

def read_int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def solve():
	n = int(input())
	(A_w, A_b) = (1, 0)
	n = n - 1
	(B_w, B_b) = (0, 0)
	cur = 2
	next_b = True
	is_a = False
	while n > 0:
		next_sum = min(n, 2 * cur + 1)
		if is_a:
			A_w += next_sum // 2
			A_b += next_sum // 2
			if next_sum % 2 == 1:
				if next_b:
					A_b += 1
				else:
					A_w += 1
		else:
			B_w += next_sum // 2
			B_b += next_sum // 2
			if next_sum % 2 == 1:
				if next_b:
					B_b += 1
				else:
					B_w += 1
		n -= next_sum
		cur += 2
		is_a = not is_a
		next_b = not next_b
	print(A_w, A_b, B_w, B_b)
T = int(input())
for _ in range(T):
	solve()


t = int(input())
while t > 0:
	n = int(input())
	n -= 1
	a = 1
	aa = 0
	b = 0
	bb = 0
	flag = False
	c = 2
	while n > 0:
		s = c * 2 + 1
		if flag:
			if s <= n:
				a += s // 2 + 1
				aa += s // 2
				n -= s
				c += 2
				flag = False
			else:
				if n & 1:
					a += n // 2 + 1
					aa += n - (n // 2 + 1)
				else:
					a += n // 2
					aa += n // 2
				break
		elif s <= n:
			b += s // 2
			bb += s // 2 + 1
			n -= s
			c += 2
			flag = True
		else:
			if n & 1:
				bb += n // 2 + 1
				b += n - (n // 2 + 1)
			else:
				b += n // 2
				bb += n // 2
			break
	print(a, aa, b, bb)
	t -= 1


def solve(n):
	r = [1, 0, 0, 0]
	c = 1
	step = 1
	while c < n:
		v = min(n - c, step * 2 + step * 2 + 1)
		p1 = v // 2
		r[2] += p1
		r[3] += v - p1
		c += v
		v = min(n - c, (step + 1) * 2 + (step + 1) * 2 + 1)
		p1 = v // 2
		r[0] += v - p1
		r[1] += p1
		c += v
		step += 2
	return r
t = int(input())
ans = []
for ti in range(t):
	n = int(input())
	ans.append(solve(n))
for a in ans:
	print(' '.join((str(x) for x in a)))


batch = int(input())
for _ in range(batch):
	n = int(input())
	A = 1
	A_w = 1
	A_b = 0
	B = 0
	B_w = 0
	B_b = 0
	l = 1
	flag = 1
	while n - A_w - A_b - B_b - B_w - 2 * l - 3 >= 0:
		if flag % 2 == 1:
			B_w += l + 1
			B_b += l + 2
			l += 2
			flag += 1
		else:
			A_b += l + 1
			A_w += l + 2
			l += 2
			flag += 1
	res = n - A_w - A_b - B_b - B_w
	if res > 0:
		if flag % 2 == 1:
			res = res // 2
			B_w += res
			B_b += res
			if n - A_w - A_b - B_b - B_w == 1:
				B_b += 1
		else:
			res = res // 2
			A_b += res
			A_w += res
			if n - A_w - A_b - B_b - B_w == 1:
				A_w += 1
	print(A_w, ' ', A_b, ' ', B_w, ' ', B_b)


t = int(input())
for i in range(t):
	n = int(input())
	aw = 1
	ab = 0
	bw = 0
	bb = 0
	n = n - 1
	j = 2
	o = 0
	l = 2 * j + 1
	while n >= l:
		if o % 2 == 1:
			aw += l // 2 + 1
			ab += l // 2
		else:
			bb += l // 2 + 1
			bw += l // 2
		n -= 2 * j + 1
		j += 2
		o += 1
		l = 2 * j + 1
	if n % 2 == 1:
		if o % 2 == 0:
			bb += n // 2 + 1
			bw += n // 2
		else:
			aw += n // 2 + 1
			ab += n // 2
	elif o % 2 == 0:
		bb += n // 2
		bw += n // 2
	else:
		aw += n // 2
		ab += n // 2
	print(aw, ab, bw, bb)


ttt = int(input())
while ttt > 0:
	ttt -= 1
	n = int(input())
	a1 = 1
	a2 = 0
	n -= 1
	b1 = 0
	b2 = 0
	i = 2
	j = 0
	while n > 0:
		k = 2 * i + 1
		if k <= n:
			if j % 2 == 0:
				b2 = b2 + k - i
				b1 = b1 + k - i - 1
			else:
				a1 = a1 + k - i
				a2 = a2 + k - i - 1
			n = n - k
		else:
			if j % 2 == 0:
				if n % 2 == 0:
					b1 = b1 + n // 2
					b2 = b2 + n // 2
				else:
					b1 = b1 + n // 2
					b2 = b2 + n // 2 + 1
			elif n % 2 == 0:
				a1 = a1 + n // 2
				a2 = a2 + n // 2
			else:
				a1 = a1 + n // 2 + 1
				a2 = a2 + n // 2
			n = 0
		i = i + 2
		j += 1
	print(a1, a2, b1, b2)


t = int(input())
for _ in range(t):
	n = int(input())
	(soc, A, B, i, rb, ra, lrc) = (n - 1, 1, 0, 1, 0, 1, 0)
	while soc > 0:
		if i % 2 == 1:
			CB = 0
			if soc - (1 + i * 4) >= 0:
				CB += 1 + i * 4
			else:
				CB += soc
			rb += 1
			soc -= CB
			B += CB
		else:
			CA = 0
			if soc - (1 + i * 4) >= 0:
				CA += 1 + i * 4
			else:
				CA += soc
			ra += 1
			soc -= CA
			A += CA
		i += 1
	WA = int((A - ra) / 2 + ra)
	BA = A - WA
	BB = int((B - rb) / 2) + rb
	WB = B - BB
	print(WA, BA, WB, BB)


import sys

def read(func=int):
	return func(sys.stdin.readline().strip())

def read_array(func=int):
	return list(map(func, read(str).split()))
t = read()
for _ in range(t):
	n = read()
	(aw, bw, ab, bb) = (0, 0, 0, 0)
	inA = False
	aw += min(1, n)
	n -= aw
	cnt = 2
	while n:
		ad = min(cnt * 2 + 1, n)
		if not inA:
			bb += (ad + 1) // 2
			bw += ad // 2
		else:
			ab += ad // 2
			aw += (ad + 1) // 2
		inA = not inA
		cnt += 2
		n -= ad
	print(aw, ab, bw, bb)


for z in range(int(input())):
	n = int(input())
	i = 2
	aw = 1
	ab = 0
	bw = 0
	bb = 0
	if n % 2 == 0:
		nw = n // 2
		nb = nw
	else:
		nb = n // 2
		nw = nb + 1
	nw -= 1
	while nw + nb != 0:
		if i % 4 == 0:
			if nw >= i + 1 and nb >= i:
				aw += i + 1
				ab += i
				nw -= i + 1
				nb -= i
			else:
				aw += nw
				ab += nb
				nw -= nw
				nb -= nb
		elif nb >= i + 1 and nw >= i:
			bb += i + 1
			bw += i
			nb -= i + 1
			nw -= i
		else:
			bb += nb
			bw += nw
			nb -= nb
			nw -= nw
		i += 2
	print(aw, end=' ')
	print(ab, end=' ')
	print(bw, end=' ')
	print(bb)


t = int(input())
for i in range(t):
	n = int(input())
	a = [1, 0]
	b = [0, 0]
	n -= 1
	i = 2
	bob = True
	while n > 0:
		if bob:
			bd = i + i + 1
			if n >= bd:
				b[0] += i
				b[1] += i + 1
				bob = False
				i += 2
				n -= bd
			else:
				if n % 2:
					b[1] += n // 2 + 1
					b[0] += n // 2
				else:
					b[0] += n // 2
					b[1] += n // 2
				n = 0
				break
		else:
			ad = i + i + 1
			if n >= ad:
				a[0] += i + 1
				a[1] += i
				bob = True
				i += 2
				n -= ad
			else:
				if n % 2:
					a[0] += n // 2 + 1
					a[1] += n // 2
				else:
					a[0] += n // 2
					a[1] += n // 2
				n = 0
				break
	print(a[0], ' ', a[1], ' ', b[0], ' ', b[1])


for _ in range(int(input())):
	x = int(input())
	(a1, a2, b1, b2) = (0, 0, 0, 0)
	i = 1
	while x:
		d = min(x, i)
		a1 += d + 1 >> 1
		a2 += d >> 1
		x -= d
		i += 4
		d = min(x, i)
		b1 += d >> 1
		b2 += d + 1 >> 1
		x -= d
		i += 4
	print(a1, a2, b1, b2)


for _ in range(int(input())):
	n = int(input())
	i = 1
	Aw = 0
	Ab = 0
	Bw = 0
	Bb = 0
	last = 'B'
	while Aw + Bw + Ab + Bb + i <= n:
		if last == 'B':
			Aw += i // 2 + 1
			Ab += i // 2
			last = 'A'
		else:
			Bw += i // 2
			Bb += i // 2 + 1
			last = 'B'
		i = (i // 2 + 1) * 2 + 3
	if Aw + Bw + Ab + Bb < n:
		i = n - (Aw + Ab + Bw + Bb)
		if last == 'B':
			Aw += i // 2 + i % 2
			Ab += i // 2
		else:
			Bw += i // 2
			Bb += i // 2 + i % 2
	print(Aw, Ab, Bw, Bb)


t = int(input())
for i in range(t):
	n = int(input())
	k = 1
	while k * (2 * k - 1) <= n:
		if k * (2 * k - 1) <= n < (k + 1) * (2 * k + 1):
			break
		else:
			k += 1
	n -= k * (2 * k - 1)
	(num1, num2) = (0, 0)
	(k1, k2) = (0, 0)
	if k % 2 == 0 and n % 2 == 0:
		num1 += n
	elif k % 2 == 0 and n % 2 == 1:
		num1 += n
		k1 += 1
	elif k % 2 and n % 2:
		num2 += n
		k2 += 1
	else:
		num2 += n
	for i in range(1, k + 1):
		if i % 2:
			num1 += 4 * i - 3
			k1 += 1
		else:
			num2 += 4 * i - 3
			k2 += 1
	print((num1 + k1) // 2, (num1 - k1) // 2, (num2 - k2) // 2, (num2 + k2) // 2)


for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print(0, 0)
	a = 1
	b = 0
	n = n - 1
	temp = 2
	flag = 1
	ab = 0
	aw = 1
	bb = 0
	bw = 0
	while n > 0:
		if flag == 1:
			if n >= temp * 2 + 1:
				x = temp * 2 + 1
				b += x
				flag = 0
				n -= x
				ans = x // 2
				bw += ans
				bb += ans + 1
			else:
				b += n
				if n % 2 == 0:
					bw += n // 2
					bb += n // 2
				else:
					bw += n // 2
					bb += n // 2 + 1
				break
		elif n >= temp * 2 + 1:
			x = temp * 2 + 1
			a += x
			flag = 1
			n -= x
			ans = x // 2
			ab += ans
			aw += ans + 1
		else:
			a += n
			if n % 2 == 0:
				ab += n // 2
				aw += n // 2
			else:
				ab += n // 2
				aw += n // 2 + 1
			break
		temp += 2
	print(aw, ab, bw, bb)


t = int(input())
for i in range(t):
	Alisa_white = 0
	Bob_white = 0
	Alisa_black = 0
	Bob_black = 0
	n = int(input())
	a = 3
	f = True
	color = True
	while n >= a:
		if f:
			Alisa_white += a // 4 + 1
			Alisa_black += a // 4
			Bob_black += a // 4 + 1
			Bob_white += a // 4 + 1
		else:
			Bob_black += a // 4 + 1
			Bob_white += a // 4
			Alisa_white += a // 4 + 1
			Alisa_black += a // 4 + 1
		n -= a
		a += 4
		f = not f
	k = min(n, a // 2)
	if f:
		Alisa_white += k - k // 2
		Alisa_black += k // 2
		Bob_white += (n - k) // 2
		Bob_black += n - k - (n - k) // 2
	else:
		Bob_black += k - k // 2
		Bob_white += k // 2
		Alisa_black += (n - k) // 2
		Alisa_white += n - k - (n - k) // 2
	print(Alisa_white, Alisa_black, Bob_white, Bob_black, sep=' ')


for _ in range(int(input())):
	n = int(input())
	(aw, ab, bw, bb) = (0, 0, 0, 0)
	x = 0
	p = 1
	while n > 0:
		if p:
			if n > 4 * x + 1:
				aw += 2 * x + 1
				ab += 2 * x
			else:
				aw += n // 2 + n % 2
				ab += n // 2
		elif n > 4 * x + 1:
			bb += 2 * x + 1
			bw += 2 * x
		else:
			bb += n // 2 + n % 2
			bw += n // 2
		p ^= 1
		n -= 4 * x + 1
		x += 1
	print(aw, ab, bw, bb)


import sys
import math
import bisect
import heapq
import itertools
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 1000000007

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_list_strings():
	return list(map(str, sys.stdin.readline().strip().split()))

def solve():
	n = get_int()
	alw = 1
	alb = 0
	bw = 0
	bb = 0
	current = 2
	turn = 0
	while sum([alw, alb, bw, bb]) + (2 * current + 1) < n:
		big_half = math.ceil((2 * current + 1) / 2)
		small_half = 2 * current + 1 - big_half
		if turn % 2 == 0:
			bw += small_half
			bb += big_half
		else:
			alw += big_half
			alb += small_half
		current += 2
		turn += 1
	left_over = n - sum([alw, alb, bw, bb])
	big_half = math.ceil(left_over / 2)
	small_half = left_over - big_half
	if turn % 2 == 0:
		bw += small_half
		bb += big_half
	else:
		alw += big_half
		alb += small_half
	return [alw, alb, bw, bb]
for _ in range(get_int()):
	print(*solve())


for _ in range(int(input())):
	num = int(input())
	i = 1
	w = w1 = b1 = b = 0
	while w + w1 + b + b1 != num:
		sum = w + w1 + b + b1
		value = 4 * i - 3
		if value <= num - sum:
			value = value
		else:
			value = num - sum
		if i % 2:
			w += (value + 1) // 2
			b += value // 2
		else:
			w1 += value // 2
			b1 += (value + 1) // 2
		i += 1
	print(w, b, w1, b1)


def ncard(n):
	aw = 0
	ab = 0
	bw = 0
	bb = 0
	i = 1
	isA = True
	c = 1
	isB = False
	while n >= i:
		if isA:
			aw += i // 2
			ab += i // 2
			if i % 2 != 0:
				if isB:
					ab += 1
				else:
					aw += 1
		else:
			bw += i // 2
			bb += i // 2
			if i % 2 != 0:
				if isB:
					bb += 1
				else:
					bw += 1
		if i % 2 != 0:
			isB = not isB
		n -= i
		i += 1
		c += 1
		if c == 2:
			c = 0
			isA = not isA
	if n > 0:
		if isA:
			aw += n // 2
			ab += n // 2
			if n % 2 != 0:
				if isB:
					ab += 1
				else:
					aw += 1
		else:
			bw += n // 2
			bb += n // 2
			if n % 2 != 0:
				if isB:
					bb += 1
				else:
					bw += 1
	print(aw, ab, bw, bb)
t = int(input())
for i in range(t):
	n = int(input())
	ncard(n)


for i in range(int(input())):
	n = int(input())
	i = 2
	t = 2
	r = {}
	r['ba'] = 0
	r['bb'] = 0
	r['wa'] = 1
	n -= 1
	r['wb'] = 0
	while n > 0:
		if t % 2 == 0:
			if n - (i * 2 + 1) >= 0:
				r['wb'] += (2 * i + 1) // 2
				r['bb'] += i * 2 + 1 - (2 * i + 1) // 2
				n -= i * 2 + 1
			else:
				r['wb'] += n // 2
				r['bb'] += n - n // 2
				n -= n
		elif n - (i * 2 + 1) >= 0:
			r['ba'] += (i * 2 + 1) // 2
			r['wa'] += i * 2 + 1 - (i * 2 + 1) // 2
			n -= i * 2 + 1
		else:
			r['ba'] += n // 2
			r['wa'] += n - n // 2
			n -= n
		i += 2
		t += 1
	print(r['wa'], r['ba'], r['wb'], r['bb'])


T = int(input())
for t in range(T):
	N = int(input()) - 1
	alicew = 1
	aliceb = 0
	bobw = 0
	bobb = 0
	i = 1
	while N > 0:
		if i % 2:
			cards = min(N, 4 * i + 1)
			if cards % 2:
				bobb += 1
			N -= cards
			bobw += cards // 2
			bobb += cards // 2
		else:
			cards = min(N, 4 * i + 1)
			if cards % 2:
				alicew += 1
			N -= cards
			alicew += cards // 2
			aliceb += cards // 2
		i += 1
	print(alicew, aliceb, bobw, bobb)


n = int(input())
for _ in range(n):
	m = int(input())
	a = 1
	aw = 1
	ab = 0
	bw = 0
	bb = 0
	b = 0
	s = 2
	m = m - 1
	u = 0
	while m > 0:
		if u % 2 == 0:
			if m >= 2 * s + 1:
				b = 2 * s + 1
				m = m - 2 * s - 1
				bb += b // 2 + 1
				bw += b // 2
				s = s + 2
			else:
				b += m
				if m % 2 == 0:
					bb += m // 2
					bw += m // 2
				else:
					bb += m // 2 + 1
					bw += m // 2
				m = 0
		elif m >= 2 * s + 1:
			a = 2 * s + 1
			m = m - 2 * s - 1
			aw += a // 2 + 1
			ab += a // 2
			s = s + 2
		else:
			a += m
			if m % 2 == 0:
				ab += m // 2
				aw += m // 2
			else:
				ab += m // 2
				aw += m // 2 + 1
			m = 0
		u = u + 1
	print(aw, ab, bw, bb)


t = int(input())
for i in range(t):
	n = int(input()) - 1
	alice_white = 1
	alice_black = 0
	bob_black = 0
	bob_white = 0
	s = 0
	j = 1
	while n > 0:
		b = 4 * j + 1
		if s == 0:
			if n > b:
				n = n - b
				bob_white += int(b / 2)
				bob_black += b - int(b / 2)
				j += 1
				s = 1
			else:
				bob_white += int(n / 2)
				bob_black += n - int(n / 2)
				n = 0
		elif n > b:
			n = n - b
			alice_black += int(b / 2)
			alice_white += b - int(b / 2)
			j += 1
			s = 0
		else:
			alice_black += int(n / 2)
			alice_white += n - int(n / 2)
			n = 0
	print(str(alice_white) + ' ' + str(alice_black) + ' ' + str(bob_white) + ' ' + str(bob_black))


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	alice_turn = False
	black = True
	alice_w = 1
	bob_w = alice_b = bob_b = 0
	rem = n - 1
	for i in range(2, n + 1, 2):
		if rem <= 0:
			break
		if i + i + 1 <= rem:
			rem -= i + i + 1
			w = b = 0
			if black:
				b = i + 1
				w = i
			else:
				w = i + 1
				b = i
			if alice_turn:
				alice_b += b
				alice_w += w
			else:
				bob_b += b
				bob_w += w
		else:
			w = b = 0
			if black:
				b = (rem + 1) // 2
				w = rem - b
			else:
				w = (rem + 1) // 2
				b = rem - w
			if alice_turn:
				alice_b += b
				alice_w += w
			else:
				bob_b += b
				bob_w += w
			rem = 0
		alice_turn ^= True
		black ^= True
	print(alice_w, alice_b, bob_w, bob_b)


def solve():
	Alicebial = 0
	Aliceczar = 0
	Bobbial = 0
	Bobczar = 0
	iledod = 1
	n = int(input().strip())
	komu = False
	while n > 0:
		if not komu:
			if min(n, iledod) % 2 == 0:
				Alicebial += min(n, iledod) // 2
				Aliceczar += min(n, iledod) // 2
			else:
				Alicebial += min(n, iledod) // 2 + 1
				Aliceczar += min(n, iledod) // 2
			komu = True
		else:
			if min(n, iledod) % 2 == 0:
				Bobbial += min(n, iledod) // 2
				Bobczar += min(n, iledod) // 2
			else:
				Bobbial += min(n, iledod) // 2 + 1
				Bobczar += min(n, iledod) // 2
			komu = False
		n -= min(n, iledod)
		iledod += 4
	print(Alicebial, Aliceczar, Bobczar, Bobbial)
t = int(input().strip())
for _ in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = [1, 0]
	b = [0, 0]
	n -= 1
	t = 1
	c = 2
	while n > 0:
		x = 2 * c + 1
		if t % 2:
			if n > x:
				b[1] += x // 2 + 1
				b[0] += x // 2
			elif n % 2:
				b[1] += n // 2 + 1
				b[0] += n // 2
			else:
				b[1] += n // 2
				b[0] += n // 2
		elif n > x:
			a[1] += x // 2
			a[0] += x // 2 + 1
		elif n % 2 == 0:
			a[1] += n // 2
			a[0] += n // 2
		else:
			a[1] += n // 2
			a[0] += n // 2 + 1
		n -= 2 * c + 1
		c += 2
		t += 1
	print(a[0], a[1], b[0], b[1])


t = int(input())
for tc in range(t):
	n = int(input())
	a = 1
	aw = 1
	ab = 0
	b = 0
	bw = 0
	bb = 0
	c = 1
	while True:
		c += 1
		b += c
		bb += c // 2
		bw += c // 2
		if a + b == n:
			print(aw, ab, bw, bb)
			break
		elif a + b > n:
			diff = a + b - n
			d = diff // 2
			bb -= d
			bw -= diff - d
			print(aw, ab, bw, bb)
			break
		c += 1
		b += c
		bb += c // 2 + 1
		bw += c // 2
		if a + b == n:
			print(aw, ab, bw, bb)
			break
		elif a + b > n:
			diff = a + b - n
			d = diff // 2
			bw -= d
			bb -= diff - d
			print(aw, ab, bw, bb)
			break
		c += 1
		a += c
		ab += c // 2
		aw += c // 2
		if a + b == n:
			print(aw, ab, bw, bb)
			break
		elif a + b > n:
			diff = a + b - n
			d = diff // 2
			aw -= d
			ab -= diff - d
			print(aw, ab, bw, bb)
			break
		c += 1
		a += c
		ab += c // 2
		aw += c // 2 + 1
		if a + b == n:
			print(aw, ab, bw, bb)
			break
		elif a + b > n:
			diff = a + b - n
			d = diff // 2
			ab -= d
			aw -= diff - d
			print(aw, ab, bw, bb)
			break


for i in range(int(input())):
	n = int(input())
	alice = [1, 0]
	bob = [0, 0]
	num = 1
	for i in range(n):
		if sum(alice) + sum(bob) + num + 4 >= n:
			left = n - (sum(alice) + sum(bob))
			if i % 2 == 0:
				if left % 2 == 0:
					bob[1] += left // 2
					bob[0] += left // 2
				else:
					bob[1] += (left + 1) // 2
					bob[0] += (left - 1) // 2
			elif left % 2 == 0:
				alice[0] += left // 2
				alice[1] += left // 2
			else:
				alice[0] += (left + 1) // 2
				alice[1] += (left - 1) // 2
			break
		if i % 2 == 0:
			num += 4
			bob[1] += (num + 1) // 2
			bob[0] += (num - 1) // 2
		else:
			num += 4
			alice[0] += (num + 1) // 2
			alice[1] += (num - 1) // 2
	print(alice[0], alice[1], bob[0], bob[1])


for _ in [''] * int(input()):
	n = int(input())
	Aw = 0
	Ab = 0
	Bw = 0
	Bb = 0
	i = 1
	while n > 0:
		if i % 4 == 0 or i % 4 == 1:
			if i % 2 == 0:
				Aw += i // 2
				Ab += i // 2
			else:
				Aw += i // 2 + 1
				Ab += i // 2
		elif i % 2 == 0:
			Bw += i // 2
			Bb += i // 2
		else:
			Bw += i // 2
			Bb += i // 2 + 1
		n -= i
		i += 1
	i -= 1
	if i % 4 == 0 or i % 4 == 1:
		if n % 2 == 0:
			Aw += n // 2
			Ab += n // 2
		elif i % 2 == 0 and n % 2 == 1:
			Aw += n // 2 + 1
			Ab += n // 2
		elif i % 2 == 1 and n % 2 == 1:
			Aw += n // 2
			Ab += n // 2 + 1
	elif n % 2 == 0:
		Bw += n // 2
		Bb += n // 2
	elif i % 2 == 0 and n % 2 == 1:
		Bw += n // 2
		Bb += n // 2 + 1
	elif i % 2 == 1 and n % 2 == 1:
		Bw += n // 2 + 1
		Bb += n // 2
	print(Aw, Ab, Bw, Bb)


for t in range(int(input())):
	n = int(input())
	alice = [0, 0]
	bob = [0, 0]
	cnt = 0
	while n > 0:
		ttl = min(n, 1 + 4 * cnt)
		if cnt % 2 == 0:
			alice[0] += int((ttl + 1) // 2)
			alice[1] += int(ttl // 2)
		else:
			bob[0] += int(ttl // 2)
			bob[1] += int((ttl + 1) // 2)
		n -= ttl
		cnt += 1
	print('{} {} {} {}'.format(alice[0], alice[1], bob[0], bob[1]))


n = int(input())
for i in range(n):
	a = int(input())
	if a == 0:
		print(0, 0)
	else:
		(first, second) = (1, 0)
		(fw, fb, sw, sb) = (1, 0, 0, 0)
		a -= 1
		c = False
		n = 1
		while a > 0:
			n += 4
			if c == False:
				second += min(n, a)
				sb += (min(n, a) + 1) // 2
				sw += min(a, n) // 2
				c = True
			else:
				first += min(n, a)
				fw += (min(n, a) + 1) // 2
				fb += min(n, a) // 2
				c = False
			a -= n
		print(fw, fb, sw, sb)


def alice_and_bob_colored_cards(n):
	alice_white = 0
	alice_black = 0
	bob_white = 0
	bob_black = 0
	i = 1
	while n > 0:
		cards_dealt = min(i, n)
		if i % 4 == 0 or i % 4 == 1:
			if cards_dealt % 2 == 0:
				alice_white += cards_dealt // 2
				alice_black += cards_dealt // 2
			else:
				alice_white += (cards_dealt + 1) // 2
				alice_black += (cards_dealt - 1) // 2
		elif cards_dealt % 2 == 0:
			bob_white += cards_dealt // 2
			bob_black += cards_dealt // 2
		else:
			bob_white += (cards_dealt - 1) // 2
			bob_black += (cards_dealt + 1) // 2
		n -= cards_dealt
		i += 1
	print(alice_white, alice_black, bob_white, bob_black)
x = int(input())
for i in range(x):
	t = int(input())
	alice_and_bob_colored_cards(t)


num = int(input())
for i in range(0, num):
	n = int(input())
	i = 1
	m = 0
	k = 0
	w = 1
	white_a = 0
	white_b = 0
	black_a = 0
	black_b = 0
	while m < n:
		if i == 1:
			white_a += 1
			i = i + 1
			m = 1
		elif k % 2 == 0:
			if i + i + 1 < n - m:
				p = (i + i + 2) // 2
				black_b += p
				white_b += i + i + 1 - p
				m = m + i + i + 1
				i = i + 2
				k = k + 1
			else:
				if n - m > 0:
					p = (n - m + 1) // 2
					black_b += p
					white_b += n - m - p
				k = k + 1
				m = m + i + i + 1
				i = i + 2
		elif i + i + 1 < n - m:
			p = (i + i + 2) // 2
			white_a += p
			black_a += i + i + 1 - p
			m = m + i + i + 1
			i = i + 2
			k = k + 1
		else:
			if n - m > 0:
				p = (n - m + 1) // 2
				white_a += p
				black_a += n - m - p
			m = m + i + i + 1
			i = i + 2
			k = k + 1
	print(white_a, black_a, white_b, black_b)


import collections
import math
import heapq
for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print(0, 0, 0, 0)
		continue
	(aw, ab, bw, bb) = (0, 0, 0, 0)
	aw += 1
	lastColor = False
	cards = 2
	x = n - 1
	giveA = False
	while True:
		curr = cards + cards + 1
		if x - curr <= 0:
			currw = x // 2 if not lastColor else (x + 1) // 2
			currb = x - currw
			if giveA:
				(aw, ab) = (aw + currw, ab + currb)
			else:
				(bw, bb) = (bw + currw, bb + currb)
			break
		currw = curr // 2 if not lastColor else (curr + 1) // 2
		currb = curr - currw
		if giveA:
			(aw, ab) = (aw + currw, ab + currb)
		else:
			(bw, bb) = (bw + currw, bb + currb)
		lastColor = lastColor if curr % 2 == 0 else not lastColor
		x -= curr
		cards += 2
		giveA = not giveA
	print(aw, ab, bw, bb)


s = int(input())
for i in range(s):
	c = int(input())
	a = b = f = e = 0
	d = 1
	l = c
	a += 1
	c -= 1
	count = 0
	while c > 0:
		d += 1
		if c - d < 0:
			d = c
		if count <= 1:
			f += d // 2
			e += d - d // 2
		else:
			a += d - d // 2
			b += d // 2
			if count == 3:
				count = -1
		c -= d
		count += 1
	print(a, b, f, e)


a = int(input())
for i in range(a):
	b = [0, 0, 0, 0]
	c = 0
	o = False
	n = int(input())
	ch = n % 2
	while n > 0:
		b[int(o) * 2 + int(o)] += 1 + c * 2
		b[int(o) * 2 + int(not o)] += c * 2
		n -= 1 + 4 * c
		o = not o
		c += 1
	o = not o
	f = n % 2
	n = -1 * n // 2
	b[int(o) * 2 + int(o)] -= n
	b[int(o) * 2 + int(not o)] -= n
	if f == 1:
		b[int(o) * 2 + ch] -= 1
	print(b[0], b[1], b[2], b[3])


for _ in range(int(input())):
	n = int(input())
	alice_w = 0
	alice_b = 0
	bob_w = 0
	bob_b = 0
	i = 1
	while n > 0:
		if i % 4 == 0:
			if n < i:
				alice_w += n - n // 2
				alice_b += n // 2
				break
			alice_w += i // 2
			alice_b += i // 2
		elif i % 4 == 1:
			if n < i:
				alice_w += n - n // 2
				alice_b += n // 2
				break
			alice_w += i // 2 + 1
			alice_b += i // 2
		elif i % 4 == 2:
			if n < i:
				bob_w += n // 2
				bob_b += n - n // 2
				break
			bob_w += i // 2
			bob_b += i // 2
		elif i % 4 == 3:
			if n < i:
				bob_w += n // 2
				bob_b += n - n // 2
				break
			bob_w += i // 2
			bob_b += i // 2 + 1
		n -= i
		i += 1
	print(alice_w, alice_b, bob_w, bob_b)


t = int(input())
for _ in range(0, t):
	n = int(input())
	c1 = 1
	n = n - 1
	k = 2
	x = 0
	c2 = 0
	if n % 2 == 0:
		w = n // 2
		b = n // 2
	else:
		w = n // 2 + 1
		b = n // 2
	w = w - 1
	c1w = 1
	c1b = 0
	c2w = 0
	c2b = 0
	while n > 0:
		if x % 2 == 0:
			tot = k + k + 1
			bb = tot // 2 + 1
			ww = tot // 2
			if n - tot >= 0:
				c2w += ww
				c2b += bb
				n = n - tot
			else:
				xx = 0
				while n > 0:
					if xx % 2 == 0:
						c2b += 1
					else:
						c2w += 1
					xx += 1
					n = n - 1
		else:
			tot = k + k + 1
			bb = tot // 2
			ww = tot // 2 + 1
			if n - tot >= 0:
				c1w += ww
				c1b += bb
				n = n - tot
			else:
				xx = 0
				while n > 0:
					if xx % 2 == 0:
						c1w += 1
					else:
						c1b += 1
					xx += 1
					n = n - 1
		x += 1
		k = k + 2
	print(f'{c1w} {c1b} {c2w} {c2b}')


for _ in range(int(input())):
	n = int(input())
	n = n - 1
	aW = 1
	aB = 0
	bW = 0
	bB = 0
	i = 2
	c = 1
	while n > 0 and n >= i:
		if i % 4 == 3 or i % 4 == 2:
			if i % 2 == 0:
				bW += i // 2
				bB += i // 2
			else:
				c += 1
				if c % 2 == 0:
					bB += i // 2 + 1
					bW += i // 2
				else:
					bB += i // 2
					bW += i // 2 + 1
		elif i % 2 == 0:
			aW += i // 2
			aB += i // 2
		else:
			c += 1
			if c % 2 == 0:
				aB += i // 2 + 1
				aW += i // 2
			else:
				aB += i // 2
				aW += i // 2 + 1
		n -= i
		i += 1
	if i % 4 == 3 or i % 4 == 2:
		if n % 2 == 0:
			bW += n // 2
			bB += n // 2
		else:
			c += 1
			if c % 2 == 0:
				bB += n // 2 + 1
				bW += n // 2
			else:
				bB += n // 2
				bW += n // 2 + 1
	elif n % 2 == 0:
		aW += n // 2
		aB += n // 2
	else:
		c += 1
		if c % 2 == 0:
			aB += n // 2 + 1
			aW += n // 2
		else:
			aB += n // 2
			aW += n // 2 + 1
	print(aW, aB, bW, bB)


test_cases = int(input())

def deal(person, cards, number, start_color):
	if cards == 0:
		return (person, cards, number, start_color)
	if number <= cards:
		person[start_color] += (number + 1) // 2
		person[1 - start_color] += number // 2
		cards -= number
	else:
		person[start_color] += (cards + 1) // 2
		person[1 - start_color] += cards // 2
		cards = 0
	if number % 2 == 1:
		start_color = 1 - start_color
	return (person, cards, number, start_color)
for _ in range(test_cases):
	n = int(input())
	color = 0
	(alice, bob) = ([0, 0], [0, 0])
	i = 1
	while n > 0:
		(alice, n, i, color) = deal(alice, n, i, color)
		i += 1
		if i != 2:
			(alice, n, i, color) = deal(alice, n, i, color)
			i += 1
		(bob, n, i, color) = deal(bob, n, i, color)
		i += 1
		(bob, n, i, color) = deal(bob, n, i, color)
		i += 1
	print(alice[0], alice[1], bob[0], bob[1])


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	i = 1
	s = 0
	c = [[0, 0], [0, 0]]
	while i <= n:
		d = i // 2
		r = i % 2
		c[i // 2 % 2][s] += d + r
		c[i // 2 % 2][s ^ 1] += d
		n -= i
		s ^= i & 1
		i += 1
	d = n // 2
	r = n % 2
	c[i // 2 % 2][s] += d + r
	c[i // 2 % 2][s ^ 1] += d
	print(c[0][0], c[0][1], c[1][0], c[1][1])

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from sys import stdin
t = int(stdin.readline().strip())
for i in range(t):
	a = int(stdin.readline().strip())
	re11 = 0
	re12 = 0
	re21 = 0
	re22 = 0
	c = 1
	l = 1
	s = 0
	for i2 in range(a):
		if s == 0:
			re11 += (c + 1) // 2
			re12 += c // 2
			l += 1
		else:
			re21 += c // 2
			re22 += (c + 1) // 2
			l += 1
		if l == 2:
			if s == 0:
				s = 1
			else:
				s = 0
			l = 0
		a -= c
		c += 1
		if a < c:
			if s == 0:
				re11 += (a + 1) // 2
				re12 += a // 2
			else:
				re21 += a // 2
				re22 += (a + 1) // 2
			break
	print(re11, re12, re21, re22)


import math

def neg(num):
	if num == 1:
		return 0
	else:
		return 1

def numCards(cards):
	if cards == 0:
		return (0, 0)
	player = [1, 0, 0, 0]
	turn = 2
	i = 1
	cards -= 1
	color = 1
	while 1:
		for _ in range(2):
			i += 1
			if cards < 0:
				return player
			if cards < i:
				Ctemp = math.ceil(cards / 2)
				Ftemp = cards - Ctemp
				player[turn + color] += Ctemp
				player[turn + neg(color)] += Ftemp
				return player
			Ctemp = math.ceil(i / 2)
			Ftemp = i - Ctemp
			player[turn + color] += Ctemp
			player[turn + neg(color)] += Ftemp
			cards -= i
		color = neg(color)
		if turn == 0:
			turn = 2
		else:
			turn = 0
t = int(input())
for _ in range(t):
	n = int(input())
	ans = numCards(n)
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	cards_aw = 0
	cards_ab = 0
	cards_bw = 0
	cards_bb = 0
	for i in range(1, n + 1):
		if n >= i:
			if i % 4 == 1 or i % 4 == 0:
				cards_aw += i - int(i / 2)
				cards_ab += int(i / 2)
				n -= i
			elif i % 4 == 2 or i % 4 == 3:
				cards_bw += int(i / 2)
				cards_bb += i - int(i / 2)
				n -= i
		elif n > 0 and n < i:
			if i % 4 == 1 or i % 4 == 0:
				cards_aw += n - int(n / 2)
				cards_ab += int(n / 2)
				n -= n
			elif i % 4 == 2 or i % 4 == 3:
				cards_bw += int(n / 2)
				cards_bb += n - int(n / 2)
				n -= n
		else:
			break
	print(cards_aw, cards_ab, cards_bw, cards_bb)


for i in range(0, 10):
	continue
for _ in range(int(input())):
	n = int(input())
	n = n - 1
	a0 = 1
	a1 = 0
	b0 = 0
	b1 = 0
	l = 2
	while n > 0:
		x = min(n, l)
		if l // 2 % 2:
			b0 += x // 2
			b1 += x // 2
			if x % 2:
				b1 += 1
		else:
			a0 += x // 2
			a1 += x // 2
			if x % 2:
				a0 += 1
		n -= x
		l += 1
	print(a0, a1, b0, b1)


for _ in range(int(input())):
	n = int(input())
	n -= 1
	a = [1, 0]
	b = [0, 0]
	color = 1
	turn = 0
	ct = 0
	g = 2
	while n:
		n -= g
		if n < 0:
			n += g
			if turn:
				if not n % 2:
					a[color] += n // 2
					a[1 - color] += n // 2
				else:
					a[color] += n // 2 + 1
					a[1 - color] += n // 2
					color = 1 - color
			elif not n % 2:
				b[color] += n // 2
				b[1 - color] += n // 2
			else:
				b[color] += n // 2 + 1
				b[1 - color] += n // 2
			break
		if turn:
			if not g % 2:
				a[color] += g // 2
				a[1 - color] += g // 2
			else:
				a[color] += g // 2 + 1
				a[1 - color] += g // 2
				color = 1 - color
			ct += 1
			g += 1
		elif not turn:
			if not g % 2:
				b[color] += g // 2
				b[1 - color] += g // 2
			else:
				b[color] += g // 2 + 1
				b[1 - color] += g // 2
				color = 1 - color
			ct += 1
			g += 1
		if ct == 2:
			ct = 0
			turn = 1 - turn
	print(*a, *b)


t = int(input())
for i in range(t):
	n = int(input())
	p = n - 1
	a = 1
	b = 0
	aw = 1
	ab = 0
	bw = 0
	bb = 0
	who = 'b'
	round = 1
	test = 2
	while True:
		if p > test:
			if who == 'b':
				if round == 1:
					b += test
					bw += test / 2
					bb += test / 2
					round = 2
				else:
					b += test
					bb += test // 2 + 1
					bw += test // 2
					who = 'a'
					round = 1
			elif round == 1:
				a += test
				aw += test / 2
				ab += test / 2
				round = 2
			else:
				a += test
				aw += test // 2 + 1
				ab += test // 2
				who = 'b'
				round = 1
			p -= test
			test += 1
		elif who == 'b':
			for k in range(1, p + 1):
				if k % 2 == 0:
					bw += 1
				else:
					bb += 1
			b += p
			break
		else:
			for k in range(1, p + 1):
				if k % 2 == 0:
					ab += 1
				else:
					aw += 1
			a += p
			break
	print(int(aw), ' ', int(ab), ' ', int(bw), ' ', int(bb))


t = int(input())
for i in range(t):
	n = int(input())
	swa = 0
	sba = 0
	swb = 0
	sbb = 0
	j = 1
	while swa + sba + swb + sbb + j <= n:
		if j % 4 == 0:
			swa = swa + j // 2
			sba = sba + j // 2
		elif j % 4 == 1:
			swa = swa + j // 2 + 1
			sba = sba + j // 2
		elif j % 4 == 2:
			swb = swb + j // 2
			sbb = sbb + j // 2
		elif j % 4 == 3:
			swb = swb + j // 2
			sbb = sbb + j // 2 + 1
		j = j + 1
	s = swa + sba + swb + sbb
	if s + j > n and s != n:
		if j % 4 == 0 or j % 4 == 1:
			swa = swa + (n - s) // 2 + (n - s) % 2
			sba = sba + (n - s) // 2
		elif j % 4 == 2 or j % 4 == 3:
			swb = swb + (n - s) // 2
			sbb = sbb + (n - s) // 2 + (n - s) % 2
	print(swa, sba, swb, sbb)


t = int(input())
for i in range(t):
	n = int(input())
	p = 0
	j = 0
	k = 0
	a = 0
	b = 0
	aw = 0
	ab = 0
	bw = 0
	bb = 0
	while True:
		if k == 0:
			a = a + j + 1
			j = j + 1
			aw = 1
		else:
			r = j + 1 + j + 2 + a + b
			if r > n:
				n = n - (a + b)
				if k % 2 == 0:
					if n % 2 == 0:
						aw = aw + int(n / 2)
						ab = ab + int(n / 2)
					else:
						aw = aw + int(n / 2) + 1
						ab = ab + int(n / 2)
				elif n % 2 == 0:
					bw = bw + int(n / 2)
					bb = bb + int(n / 2)
				else:
					bw = bw + int(n / 2)
					bb = bb + int(n / 2) + 1
				break
			if k % 2 == 0:
				a = a + j + 1 + j + 2
				aw = aw + int((j + 1) / 2) + int((j + 2) / 2) + 1
				ab = ab + int((j + 1) / 2) + int((j + 2) / 2)
			else:
				b = b + j + 1 + j + 2
				bw = bw + int((j + 1) / 2) + int((j + 2) / 2)
				bb = bb + int((j + 1) / 2) + int((j + 2) / 2) + 1
			j = j + 2
		k = k + 1
	print(aw, ab, bw, bb)


for _ in range(int(input())):
	n = int(input())
	i = 1
	(alice, bob) = (0, 0)
	(aw, ab, bw, bb) = (0, 0, 0, 0)
	while alice + bob < n:
		cut = i
		if alice + bob + cut > n:
			cut = n - alice - bob
		if i % 4 in [0, 1]:
			alice += cut
			if cut % 2:
				aw += (cut + 1) // 2
				ab += cut // 2
			else:
				aw += cut // 2
				ab += cut // 2
		else:
			bob += cut
			if cut % 2:
				bw += cut // 2
				bb += (cut + 1) // 2
			else:
				bw += cut // 2
				bb += cut // 2
		i += 1
	print(aw, ab, bw, bb)


NT = int(input())
for T in range(NT):
	n = int(input())
	answer = [0, 0, 0, 0]
	first_card = 1
	for it in range(1, 20000):
		who = 0 if it % 4 == 1 or it % 4 == 0 else 1
		cnt = it
		if n < cnt:
			cnt = n
		cnt_white = (cnt + first_card % 2) // 2
		cnt_black = cnt - cnt_white
		answer[who * 2 + 0] += cnt_white
		answer[who * 2 + 1] += cnt_black
		first_card += cnt
		n -= cnt
		if n == 0:
			break
	assert n == 0
	print(*answer)


T = int(input())
for i in range(T):
	N = int(input())
	(Aw, Ab, Bw, Bb) = (0, 0, 0, 0)
	tot = 0
	now = 1
	while tot < N:
		num = min(now, N - tot)
		if now % 4 == 0 or now % 4 == 1:
			if tot % 2 == 0:
				Aw += (num + 1) // 2
				Ab += num // 2
			else:
				Aw += num // 2
				Ab += (num + 1) // 2
		elif tot % 2 == 0:
			Bw += (num + 1) // 2
			Bb += num // 2
		else:
			Bw += num // 2
			Bb += (num + 1) // 2
		tot += now
		now += 1
	print(Aw, Ab, Bw, Bb)


t = int(input())
for i in range(t):
	n = int(input())
	aw = 1
	ab = 0
	bb = 0
	bw = 0
	i = 2
	while i * (i + 1) / 2 < n:
		if (i + 2) % 4 == 0 or (i + 1) % 4 == 0:
			if i % 2 == 0:
				bb += i // 2
				bw += i // 2
			else:
				bb += i // 2 + 1
				bw += i // 2
		elif i % 2 == 0:
			ab += i // 2
			aw += i // 2
		else:
			aw += i // 2 + 1
			ab += i // 2
		i += 1
	if (i + 2) % 4 == 0 or (i + 1) % 4 == 0:
		c = n - (aw + ab + bw + bb)
		if c % 2 == 0:
			bb += c // 2
			bw += c // 2
		else:
			bb += c // 2 + 1
			bw += c // 2
	else:
		c = n - (aw + ab + bw + bb)
		if c % 2 == 0:
			ab += c // 2
			aw += c // 2
		else:
			aw += c // 2 + 1
			ab += c // 2
	print(aw, ab, bw, bb)


for n in [*map(int, open(0))][1:]:
	d = 1
	a = [0] * 4
	while n:
		t = min(d, n)
		k = t + d // 2 % 2 >> 1
		a[d & 2] += t - k
		a[d & 2 | 1] += k
		n -= t
		d += 1
	print(*a)


t = int(input())
l = []
for i in range(t):
	l.append(int(input()))
for n in l:
	whiteal = 0
	whitebob = 0
	blackal = 0
	blackbob = 0
	turn = 1
	while n > 0:
		if turn % 4 == 1 or turn % 4 == 0:
			w = min(turn, n) // 2
			whiteal += w
			blackal += min(turn, n) - w
			n -= min(turn, n)
		else:
			w = min(turn, n) // 2
			whitebob += w
			blackbob += min(turn, n) - w
			n -= min(turn, n)
		turn += 1
	print(blackal, ' ', whiteal, ' ', whitebob, ' ', blackbob)


t = int(input())
for i in range(t):
	n = int(input())
	alice_black = 0
	alice_white = 1
	bob_black = 0
	bob_white = 0
	start_color = 0
	i = 2
	n -= 1
	start_color = 1
	ct = 0
	flag = 1
	while n > 0:
		no_of_cards = min(n, i)
		if no_of_cards % 2 == 0:
			white_cards = no_of_cards // 2
			black_cards = no_of_cards // 2
			if flag == 1:
				bob_white += white_cards
				bob_black += black_cards
			else:
				alice_white += white_cards
				alice_black += black_cards
		else:
			black_cards = no_of_cards // 2
			white_cards = no_of_cards // 2
			if start_color == 0:
				white_cards += 1
			else:
				black_cards += 1
			if flag == 1:
				bob_white += white_cards
				bob_black += black_cards
			else:
				alice_white += white_cards
				alice_black += black_cards
			start_color = 1 - start_color
		ct += 1
		if ct == 2:
			ct = 0
			flag = 1 - flag
		n -= i
		i += 1
	print(alice_white, alice_black, bob_white, bob_black)


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	k = 0
	for i in range(1, int(math.sqrt(2 * n)) + 2):
		if i * (i + 1) >= 2 * n:
			k = i
			break
	if k * (k + 1) > 2 * n:
		k = k - 1
	a1 = 1
	a2 = 0
	b1 = 0
	b2 = 0
	turn = 0
	for i in range(2, k + 1):
		if turn == 0 or turn == 1:
			b1 += math.ceil(i / 2)
			b2 += math.floor(i / 2)
			turn += 1
		elif turn == 2 or turn == 3:
			a1 += math.ceil(i / 2)
			a2 += math.floor(i / 2)
			turn += 1
		if turn == 4:
			turn = 0
	if 2 * n - k * (k + 1) > 0:
		if turn == 0 or turn == 1:
			b1 += math.ceil((n - k * (k + 1) / 2) / 2)
			b2 += math.floor((n - k * (k + 1) / 2) / 2)
		else:
			a1 += math.ceil((n - k * (k + 1) / 2) / 2)
			a2 += math.floor((n - k * (k + 1) / 2) / 2)
	print(str(int(a1)) + ' ' + str(int(a2)) + ' ' + str(int(b2)) + ' ' + str(int(b1)))


from itertools import cycle
for _ in range(int(input())):
	n = int(input())
	deal: int = 1
	alice_w: int = 0
	alice_b: int = 0
	bob_w: int = 0
	bob_b: int = 0
	cy = cycle((0, 1, 2, 3))
	color = False
	if n >= deal:
		n -= deal
		alice_w += 1
		deal += 1
	while n > 0:
		c = next(cy)
		if deal % 2 == 0:
			color = not color
		deals = 0
		if n >= deal:
			deals = deal
		else:
			deals = n
		if c in (0, 1):
			bob_w += int(deals // 2)
			bob_b += int(deals // 2)
			if deals % 2 != 0:
				if color:
					bob_b += 1
				else:
					bob_w += 1
		if c in (2, 3):
			alice_w += int(deals // 2)
			alice_b += int(deals // 2)
			if deals % 2 != 0:
				if color:
					alice_b += 1
				else:
					alice_w += 1
		n -= deal
		deal += 1
	print(f'{alice_w} {alice_b} {bob_w} {bob_b}')


for i in range(int(input())):
	n = int(input())
	turn = 0
	aw = 0
	bw = 0
	ab = 0
	bb = 0
	s = 0
	for i in range(1, 10 ** 18):
		turn = 1 if i % 4 in (2, 3) else 0
		T = min(i, n)
		w = 0
		w += (s + T) // 2 - s // 2
		b = 0
		b += T - w
		n -= T
		if turn == 0:
			aw += w
			ab += b
		else:
			bw += w
			bb += b
		s += T
		if n == 0:
			break
	print(ab, aw, bb, bw)


for _ in range(int(input())):
	n = int(input())
	N = n
	(a, b) = ([0, 0], [0, 0])
	i = 1
	while n > 0:
		if i == 1 or i // 2 % 2 == 0:
			if min(i, n) % 2 == 0:
				a[0] += min(n, i) // 2
				a[1] += min(n, i) // 2
			else:
				a[0] += min(n, i) // 2 + 1 - (N - n) % 2
				a[1] += min(n, i) // 2 + (N - n) % 2
		elif min(i, n) % 2 == 0:
			b[0] += min(n, i) // 2
			b[1] += min(n, i) // 2
		else:
			b[0] += min(n, i) // 2 + 1 - (N - n) % 2
			b[1] += min(n, i) // 2 + (N - n) % 2
		n -= i
		i += 1
	print(*a, *b)


for _ in range(int(input())):
	n = int(input())
	ok = 0
	a = [0, 0]
	b = [0, 0]
	i = 1
	while ok < n:
		mn = min(i, n - ok)
		if i // 2 % 2 == 0:
			a[0] += (ok + mn + 1) // 2 - (ok + 1) // 2
			a[1] += (ok + mn) // 2 - ok // 2
		else:
			b[0] += (ok + mn + 1) // 2 - (ok + 1) // 2
			b[1] += (ok + mn) // 2 - ok // 2
		ok += mn
		i += 1
	print(a[0], a[1], b[0], b[1])


t = int(input())
rjesenja = []
for case in range(t):
	n = int(input())
	a = [0, 0]
	b = [0, 0]
	i = 1
	j = 0.5
	while True:
		cur = int(j)
		if cur % 2 == 0:
			a[0] += i // 2
			a[1] += i // 2
			a[(sum(a) + sum(b)) % 2] += i % 2
		else:
			b[0] += i // 2
			b[1] += i // 2
			b[(sum(a) + sum(b)) % 2] += i % 2
		if sum(a) + sum(b) >= n:
			dif = sum(a) + sum(b) - n
			if cur % 2 == 0:
				a[(sum(a) + sum(b)) % 2 - 1] -= dif % 2
				a[0] -= dif // 2
				a[1] -= dif // 2
			else:
				b[(sum(a) + sum(b)) % 2 - 1] -= dif % 2
				b[0] -= dif // 2
				b[1] -= dif // 2
			break
		i += 1
		j += 0.5
	rjesenja.append((a, b))
for r in rjesenja:
	print(r[0][0], r[0][1], r[1][0], r[1][1])


for _ in range(int(input())):
	cards = int(input())
	f = 'AABB' * cards
	w_A = 0
	b_A = 0
	w_B = 0
	b_B = 0
	i = 0
	while cards >= i:
		if f[i] == 'A':
			w_A = w_A + i // 2 + i % 2
			b_A = b_A + i // 2
		else:
			w_B = w_B + i // 2
			b_B = b_B + i // 2 + i % 2
		cards = cards - i
		i += 1
	if f[i] == 'A':
		w_A = w_A + cards // 2 + cards % 2
		b_A = b_A + cards // 2
	else:
		w_B = w_B + cards // 2
		b_B = b_B + cards // 2 + cards % 2
	print(w_A, b_A, w_B, b_B)


for _ in range(int(input())):
	n = int(input())
	x = 0
	white = [0, 0]
	black = [0, 0]
	i = 1
	while n:
		if i // 2 % 2:
			j = 0
		else:
			j = 1
		if not min(n, i) % 2:
			white[j] += min(n, i) // 2
			black[j] += min(n, i) // 2
		elif x % 2:
			white[j] += min(n, i) // 2
			black[j] += min(n, i) // 2 + 1
		else:
			white[j] += min(n, i) // 2 + 1
			black[j] += min(n, i) // 2
		x += min(n, i)
		n -= min(n, i)
		i += 1
	print(white[1], black[1], white[0], black[0])


t = int(input())
for i in range(t):
	n = int(input())
	alw = 1
	alb = 0
	bobw = 0
	bobb = 0
	A = []
	n = n - 1
	for j in range(10000):
		A.append(j + 1)
	for j in range(1, 1000):
		if j % 2 == 1:
			if n >= A[2 * j - 1]:
				bobw += A[2 * j - 1] // 2
				bobb += A[2 * j - 1] // 2 + A[2 * j - 1] % 2
				n -= A[2 * j - 1]
				if n >= A[2 * j]:
					bobw += A[2 * j] // 2
					bobb += A[2 * j] // 2 + A[2 * j] % 2
					n -= A[2 * j]
				else:
					bobb += n // 2 + n % 2
					bobw += n // 2
					break
			else:
				bobb += n // 2 + n % 2
				bobw += n // 2
				break
		elif n >= A[2 * j - 1]:
			alw += A[2 * j - 1] // 2 + A[2 * j - 1] % 2
			alb += A[2 * j - 1] // 2
			n -= A[2 * j - 1]
			if n >= A[2 * j]:
				alw += A[2 * j] // 2 + A[2 * j] % 2
				alb += A[2 * j] // 2
				n -= A[2 * j]
			else:
				alw += n // 2 + n % 2
				alb += n // 2
				break
		else:
			alw += n // 2 + n % 2
			alb += n // 2
			break
	print(f'{alw} {alb} {bobw} {bobb}')


import math
t = int(input())
for i in range(t):
	n = int(input())
	k = 1
	while n >= k * (k + 1) / 2:
		k += 1
	k -= 1
	a = [j if j % 4 == 0 or (j + 3) % 4 == 0 else 0 for j in range(1, k + 1)]
	(aw, ab, bw, bb) = (0, 0, 0, 0)
	for j in a:
		aw += math.ceil(j / 2)
		ab += math.floor(j / 2)
	b = [j if (j + 1) % 4 == 0 or (j + 2) % 4 == 0 else 0 for j in range(1, k + 1)]
	for j in b:
		bb += math.ceil(j / 2)
		bw += math.floor(j / 2)
	if k % 4 == 0 or (k + 1) % 4 == 0:
		aw += math.ceil((n - k * (k + 1) // 2) / 2)
		ab += math.floor((n - k * (k + 1) // 2) / 2)
	else:
		bb += math.ceil((n - k * (k + 1) // 2) / 2)
		bw += math.floor((n - k * (k + 1) // 2) / 2)
	print(aw, ab, bw, bb)


def cards(n):
	move = 1
	(aw, ab, bw, bb) = (0, 0, 0, 0)
	i = 1
	cur_c = 1
	while aw + ab + bw + bb < n:
		move %= 4
		if move == 2 or move == 3:
			if i % 2 == 0:
				bw += i // 2
				bb += i // 2
			elif cur_c == 1:
				bw += i // 2 + 1
				bb += i // 2
				cur_c = 0
			else:
				bb += i // 2 + 1
				bw += i // 2
				cur_c = 1
			move += 1
		else:
			if i % 2 == 0:
				aw += i // 2
				ab += i // 2
			elif cur_c == 1:
				aw += i // 2 + 1
				ab += i // 2
				cur_c = 0
			else:
				ab += i // 2 + 1
				aw += i // 2
				cur_c = 1
			move += 1
		i += 1
		if aw + ab + bw + bb + i >= n:
			i = n - (aw + ab + bw + bb)
	return (aw, ab, bw, bb)
n = int(input())
for i in range(n):
	t = int(input())
	print(cards(t)[0], cards(t)[1], cards(t)[2], cards(t)[3])