Sung sướng với bits

Cho một dãy \(n\) số \(a_{1},a_{2},...,a_{n}\) và \(1\) số \(m\) sao cho \(0 \leq a_{i} < 2^m\) . Với mỗi \(i\) từ \(1\) đến \(n\) và \(k\) từ \(k\) từ \(0\) đến \(m\) hãy in ra số số \(j\) sao cho \(1 \leq j < i\) mà \(dis(a_{i},a_{j})=k\) Trong đó \(dis(x,y)\) là số số bit được bật trong đúng một trong \(2\) biểu diễn nhị phân của \(x\), \(y\) .

Input

• Dòng đầu chứa số \(n\) và \(m\) \((1 \leq n \leq 2e5, 1 \leq m \leq 16)\). Dòng sau chứa \(n\) số \(a_{1},a_{2},...,a_{n}\) .

• Dòng thứ hai chứa \(n\) số \(a_{1}, a_{2}, ..., a_{n}\).

Output

\(n\) dòng mỗi dòng \(m + 1\) số là đáp án của \(k = 0, 1, ...,m\).

Example

4 2
0 1 2 3

0 0 0 
0 1 0 
0 1 1 
0 2 1 

4 1
0 1 1 0

0 0 
0 1 
1 1 
1 2 

Scoring

\(30\%\) số test có \(n \leq 1000\).

\(30\%\) số test có \(m \leq 8\).

\(40\%\) số test còn lại không có ràng buộc gì thêm.