Doraemon rất thích ăn buffet lẩu ở Kichi-Kichi. Ở đây có \(n\) món ăn với số lượng vô hạn - mỗi món có thể được ăn vô số lần (có thể ăn \(0\) lần). Các món ăn được đánh số từ \(1\) đến \(n\), món thứ \(i\) có khối lượng là \(a_i\). Tổng khối lượng các món mà Doraemon có thể ăn không vượt quá \(m\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(t\) (\(t \leq 100\)) - số lượng truy vấn.
• \(2 \cdot t\) dòng tiếp theo, mỗi truy vấn nhập vào hai dòng:
  • Dòng đầu tiên nhập vào hai số nguyên dương \(n\), \(m\) (\(n, m \leq 10^4\)) - số món ăn và khối lượng đồ ăn tối đa mà Doraemon có thể ăn.
  • Dòng tiếp theo, nhập vào \(n\) số nguyên dương \(a_1, a_2, a_3, \dots, a_n\) (\(1 \leq a_i \leq 10^5\) \(\forall\) \(1 \leq i \leq n\)) - khối lượng của từng món ăn.

Output

• Với mỗi truy vấn, in ra \(m\) số. Số thứ \(i\) là \(1\) nếu có thể ăn sao cho tổng khối lượng các món ăn là \(i\) và in ra \(0\) trong trường hợp ngược lại.

Ở mỗi subtask, luôn đảm bảo rằng tổng của \(n\) trong các truy vấn không vượt quá \(N\).

Example

2
3 20
3 6 9
2 10
4 5

0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 
0 0 0 1 1 0 0 1 1 1

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(t \leq 10\), \(N \leq 20\), \(m \leq 10^4\)
• Subtask \(2\) (\(20\%\) số điểm): \(t \leq 100\), \(N \leq 10^3\), \(m \leq 10^3\)
• Subtask \(3\) (\(30\%\) số điểm): \(t \leq 100\), \(N \leq 10^4\), \(m \leq 10^4\)