智乃想考一道鸽巢原理
题号:NC269394
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

智乃有N种不同颜色的小球,第i种颜色的小球有a_i个,放在同一个盒子中。

假设智乃每次任意取出两个不同颜色的小球并丢弃,然后重复这一过程,直到盒子为空或者只剩下一种颜色的小球。

智乃想要知道每种颜色的小球是否为最终可能被剩下的颜色。

一种小球的颜色为最终可能被剩下的颜色,当且仅当至少存在一种丢弃小球的方案使得盒子中最后只剩下(至少存在1个)该种颜色的小球。

输入描述:

第一行输入一个正整数T(1\leq T \leq 10^{6})

对于每组测试案例,第一行输入一个正整数N(1\leq N \leq 10^5)表示有N种颜色的小球,接下来一行输入N个正整数a_{i}(1\leq a_{i} \leq 10^{9})表示每种颜色的小球数目。

输入数据保证\sum N \leq 10^{6}

输出描述:

输出一行N个整数ans_{i},ans_i \in \{0,1\},表示第i种颜色的小球是否有可能成为最终剩下的小球,如果可能输出1,否则输出0,整数之间用一个空格隔开。
示例1

输入

复制
1
2
10 10

输出

复制
0 0

说明

只有两种颜色,个数相同,两两相消
示例2

输入

复制
2
2
10 110
3
1 1 1

输出

复制
0 1
1 1 1

说明

对于第一个样例,两两相消后只会剩下第2种球。
对于第二个样例,一开始消除1,2可以剩下3;消除1,3剩下2;消除2,3剩下1。所以每种小球都可能被留到最后。