题目描述

对于任意一个非负整数 $n$，都可以表示成二进制。

例如 $5$ 可以表示为 $(101)_2$，即 $2^2 + 0 + 2 ^ 0 = 4 + 1 = 5$。

现在你需要把 $n$ 拆成 $32$ 位二进制，但是每一位的取值可以是 $-1,0,1$。同时，还需要保证任意相邻的两位不能同时为 $0$。

形式化来说，你需要构造 $32$ 个数字 $a_{31},a_{30},...,a_0$ 满足下列所有条件：

$1$、$\sum_{i = 0} ^{31} a_i2^i = n$， 其中 $a_i \in \{-1,0,1\}$

$2$、$a_i^2 + a_{i+1}^2 > 0$，其中 $0 \leq i < 31$

输入格式

每个测试文件包含多组测试数据。第一行包含测试数据的组数 $T$。每组测试数据的格式如下。

每组数据仅包含一行一个非负整数 $n$。

输出格式

对于每组数据，若答案存在，你需要先输出 YES，然后接下来的 $4$ 行每行 $8$ 个数字 $a_i$,表示答案。你需要从低位到高位输出。 否则只输出 NO。如果有多种构造方案，输出任意一种即可。

3
0
3
5

NO
YES
1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 1
YES
-1 1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 1

数据规模与约定

由于具有明显提示性，本题没有大样例。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10^4,0 \leq n < 2^{30}$。