Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Bằng một cách nào đó mà không ai biết được, Aki đã xây dựng cho riêng anh một phòng thí nghiệm phỏng theo tựa game Portal, và anh quyết định dùng nó làm một môi trường rèn luyện mô phỏng.

Một lần, Aki được GLaDOS giao yêu cầu truy tìm một chip dữ liệu bí mật. Vì lý do bảo mật, loại chip mà GLaDOS sử dụng có cấu tạo đặc biệt: mỗi chip gồm một lõi bất động ở giữa, bao xung quanh là một số lõi phụ xếp thành vòng. Mỗi con chip đều có khả năng đảo: khi đảo, ta chọn 2 chip bất kỳ liền kề nhau rồi tráo đổi vị trí của chúng (ví dụ như hình dưới, với chip gồm 6 lõi phụ):

Chính bởi cấu tạo linh hoạt như vậy, nên mỗi khi tìm thấy một con chip, trước khi giao cho GLaDOS, Aki cần phải đảo nó về đúng trạng thái mà A.I. này yêu cầu.

Tuy nhiên, không đời nào GLaDOS lại để “vật thí nghiệm” hoàn thành thử thách dễ dàng được. Không phải con chip nào cũng có thể đảo để biến thành con chip mà cô yêu cầu.

Aki đã thu được về một số lượng chip khá lớn, và anh quyết định tìm con chip đúng bằng phương pháp brute-force. Vì thời gian thí nghiệm có hạn, anh cần phải biết số lần đảo tối thiểu cho mỗi con chip để nó trở thành con chip đúng (đương nhiên với điều kiện là số lần đó hữu hạn!)

Input

Dòng đầu tiên gồm hai số nguyên k và N (4 <= k <= 9, 1 <= N <= 10^5), lần lượt là số lõi phụ của con chip mà GLaDOS yêu cầu và số chip mà Aki thu thập được.

N+1 dòng tiếp theo, mỗi dòng chứa (k+1) số nguyên phân biệt nằm trong khoảng [1, k+1], biểu diễn các con chip:

k số nguyên đầu tiên là các số nguyên trên các lõi phụ, lần lượt từ lõi phụ thứ 1 tới lõi phụ thứ k. Lưu ý là con chip Aperture Science không hề đối xứng – chỉ có một cách sắp đặt lõi phụ duy nhất thỏa mãn!

Số nguyên thứ k+1 là số nguyên trên lõi bất động nằm ở chính giữa con chip.

Dòng đầu tiên là con chip mà GLaDOS yêu cầu, các dòng tiếp theo là các con chip mà Aki tìm được.

Output

Output gồm N dòng: với dòng thứ i (1 <= i <= N), in ra số lần đảo tối thiểu để con chip thứ i của Aki trở thành con chip mà GLaDOS yêu cầu. Nếu không thể đảo con chip đó như ý, in ra dòng chữ “The cake is a lie.”.

Example

Input:
6 7
2 3 5 1 6 4 7
3 2 5 1 6 4 7
2 5 3 1 6 4 7
2 3 1 5 6 4 7
2 3 5 6 1 4 7
2 3 5 1 4 6 7
4 3 5 1 6 2 7
1 7 4 2 5 6 3

Output:
1
1
1
1
1
1
The cake is a lie.