2. Ováľané mince

V meste hovniválov sa deje veľká udalosť – ide sa stavať obrovský palác z trusových gulôčok. Stavia sa na počesť Hovnivála I. , ktorý zjednotil všetky kmene hovniválov do jednej veľkej ríše a priniesol medzi nich pokoj a mier. Keď sa zhromažďovali gulôčky, bolo jasné, že ho nebude také ľahké postaviť. Začal sa konkurz na stavbu paláca. Tento konkurz vyhrala firma, kde pracujú Janko a Ferko, a práve oni dostali poverenie postaviť tento palác. Ako roky plynuli, stavbári čakali už len na jedno – peniaze za túto neľahkú stavbu. A ten čas nastal dnes.

Kto vykonal viac práce? Janko či Ferko? Boli ste poverení vyplatiť im ich zaslúžené peniaze. Ale pozor! Nechcete, aby sa ich výplaty veľmi odlišovali, inak sa pobijú!

Úloha

Máme \(n\) mincí s hodnotami \(1\) až \(n\). Keďže chceme, aby sa nepobili, musíme rozdeliť tieto mince čo najviac rovnomerne obidvom stavbárom. Každú mincu máte k dispozícii len raz. Pochopiteľne ju musíte dať len jednému stavbárovi. Vašou úlohou je nájsť čo najmenší rozdiel výplat Janka a Ferka.

Formát vstupu

Na prvom riadku vstupu dostanete číslo \(t, 1\leq t \leq 1000\), počet výplat, ktoré chcete rozdeliť. Na každom z ďalších \(t\) riadkov sa nachádzajú dve medzerou oddelené čísla \(n_i\) a \(p\), kde číslo \(n_i\) znamená počet mincí, ktoré máme pre danú výplatu (mince majú teda hodnoty \(1, 2, ... , n_i\)), a \(p \in \{0,1\}\). Platí, že \(1 \leq n_i \leq 3000\)

Formát výstupu

Ak sa \(p=0\), na výstup vypíšte pre danú výplatu jedno číslo na samostatnom riadku – minimálny rozdiel výplat Janka a Ferka.

Ak sa \(p=1\), na výstup pre danú výplatu okrem jedného čísla na samostatnom riadku – minimálneho rozdielu výplat, vypíšte aj príklad na nejaké rozdelenie mincí, kde je rozdiel výplat minimálny. Pre každú výplatu okrem minimálneho rozdielu vypíšte ďalšie dva riadky.

Prvý z nich na začiatku obsahuje číslo \(j\) – počet mincí, ktoré dostane Janko. V tom istom riadku nasleduje medzera a \(j\) medzerou oddelených čísiel – hodnoty Jankových mincí.

Druhý z nich na začiatku obsahuje číslo \(f\) – počet mincí, ktoré dostane Ferko. V tom istom riadku nasleduje medzera a \(f\) medzerou oddelených čísel – hodnoty Ferkových mincí.

Obmedzenia

V prvej štvrtine sád platí \(p=0\).

Poznámka

V posledných sadách je treba vypisovať pomerne veľa čísel, a v prípade, ak to robíte pomaly (a najmä v pomalom programovacom jazyku ako napr. Pythone), vám môže byť neakceptované riešenie, ktoré má vzorovú časovú zložitosť. Na vypisovanie poľa odporúčame namiesto:

for i in range(len(pole)-1):
	print(pole[i], end=' ')
print(pole[-1])

použiť

print(" ".join(str(prvok) for prvok in pole))

Príklad

Input:

2
3 0
5 0

Output:

0
1

V prvom prípade máme mince hodnôt \(1, 2, 3\). Medzi dvoch ľudí ich vieme rozdeliť tak, že prvý dostane mince \(1\) a \(2\) a druhý dostane mincu \(3\). Rozdiel medzi súčtami ich mincí je teda \(0\). V druhom prípade máme mince \(1, 2, 3, 4, 5\). Tieto mince vieme najlepšie rozdeliť tak, že prvý dostane mince \(1, 2, 5\) a druhý mince \(3, 4\), teda rozdiel medzi súčtami ich mincí je 1.

Input:

2
3 1
5 1

Output:

0
2 1 2
1 3
1
3 1 2 5
2 3 4

Iný príklad na 5 mincí môže byť napríklad aj tak, že prvý človek dostane mince \(1, 2, 4\) a druhý \(3, 5\)