Có ~N~ giám khảo và ~M~ thí sinh. Giám khảo thứ ~i~ sẽ bầu chọn cho thí sinh thứ ~j~ nếu ~A_{i,j} = 1~, và không bầu chọn nếu ~A_{i,j} = 0~. Một thí sinh sẽ được chọn nếu họ được ~\geq \lfloor \frac{N}{2} \rfloor~ giám khảo bầu chọn cho mình.

Tuy nhiên sẽ có 2 ông giám khảo ~i~ và ~j~ bất kì (~i \neq j~) bị loại ra để kiểm phiếu. Với mỗi giám khảo ~i~, bạn cần tính xem: nếu như bạn phải loại giám khảo ~i~, và một giám khảo ~j~ bất kì khác (~j \neq i~), thì số người được chọn lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số ~N~ và ~M~. (~3 \leq N \leq 3 \times 10^5~, ~1 \leq M \leq 20~)

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa ~M~ số nguyên không âm, với số thứ ~j~ là ~A_{i, j}~. (~A_{i, j} \in \{0, 1\}~)

Output

• Gồm ~N~ dòng, dòng thứ ~i~ chứa một số nguyên duy nhất là kết quả khi bắt buộc phải chọn giám khảo ~i~ đi kiểm phiếu.

Sample Input 1

3 3
1 0 1
1 1 1
0 1 0

Sample Output 1

3
2
3

Sample Input 2

4 10
1 1 0 1 0 0 0 1 1 0
1 1 1 0 0 1 1 1 0 0
0 0 0 1 0 0 0 1 1 1
0 1 1 1 0 0 0 0 1 0

Sample Output 2

2
3
3
3