Это сложная версия задачи. В этой версии карты бывают двух цветов.
У Алисы есть $$$n$$$ карт, каждая карта либо черная, либо белая. Карты уложены в колоду, причем цвета карт чередуются, начиная с белой. Алиса раздает карты себе и Бобу, забирая по несколько карт сразу сверху стопки в таком порядке: одну карту себе, две карты Бобу, три карты Бобу, четыре карты себе, пять карт себе, шесть карт Бобу, семь карт Бобу, восемь карт себе и т. д.. Иными словами, на $$$i$$$-м шаге Алиса отдает верхние $$$i$$$ карт из колоды одному из игроков, при этом на первом шаге она отдает карты себе, а затем чередует игроков через каждые два шага. Если на очередном шаге в колоде недостаточно карт, Алиса выдает все оставшиеся карты текущему игроку и процесс заканчивается.
Первые шаги Алисы для колоды из большого числа карт. Сколько карт каждого цвета окажется у Алисы и Боба в конце?
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 200$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество карт.
Для каждого набора входных данных выведите четыре числа — количество карт в конце у игроков — в таком порядке: белые карты у Алисы, черные карты у Алисы, белые у Боба, черные у Боба.
51061781000000
3 2 2 3 1 0 2 3 6 4 3 4 2 1 2 3 250278 249924 249722 250076
