完全积性函数是一个算术函数（即定义域为自然数的函数），满足 $f(1) = 1$ 且对于所有正整数 $a$ 和 $b$，都有 $f(ab) = f(a)f(b)$。

Little Cyan Fish 热爱完全积性函数的概念，因此他想要找到一个完全积性函数 $f: \mathbb{N} \to \{-1, 1\}$，使得对于给定的整数 $n$ 和 $k$，满足 $\sum_{i=1}^n f(i) = k$。

形式化地，你需要找到一个函数 $f(x)$ 满足：

• 对于所有整数 $x$，$f(x) \in \{-1, 1\}$。
• 对于所有整数 $x$ 和 $y$，$f(x)f(y) = f(xy)$。
• 对于给定的整数 $n$ 和 $k$，$f(1) + f(2) + \dots + f(n) = k$。

为了测试你是否真正理解了完全积性函数之美，Little Cyan Fish 请你找到这样一个函数 $f$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $n$ 和 $k$ ($0 \le k \le n \le 10^6, n \ge 1$)。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^6$。

输出格式

对于每组测试数据：

如果不存在满足条件的解，输出一行，包含一个整数 $-1$。

否则，输出一行，包含 $f(1), f(2), \dots, f(n)$，中间用空格分隔。每个 $f(i)$ 的值必须为 $1$ 或 $-1$，且这些值的总和必须恰好为 $k$。

如果存在多个解，你可以输出其中任意一个。

样例

输入 1

4
4 2
10 0
10 1
10 10

输出 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