Ngày xửa ngày xưa, một cô giáo mầm non đưa trẻ em ra công viên chơi trò điện thoại hỏng. Mỗi đứa trẻ trong số $N$ đứa trẻ đều biết cùng một tập hợp gồm $M$ từ, được đánh số từ $1$ đến $M$. Trò chơi diễn ra như sau: cô giáo xếp trẻ thành một hàng và thì thầm từ số $1$ vào tai đứa trẻ đầu tiên. Sau đó, đứa trẻ đầu tiên thì thầm từ mà nó nghe được vào tai đứa trẻ thứ hai, đứa trẻ thứ hai thì thầm từ mà nó nghe được vào tai đứa trẻ thứ ba, và cứ tiếp tục như vậy cho đến đứa trẻ cuối cùng. Lúc này, đứa trẻ cuối cùng sẽ nói to từ mà nó nghe được.

Vì hôm đó các bạn nhỏ yêu tin học đang mải mê lập trình ồn ào ở gần đó, bọn trẻ không thể tập trung vào trò chơi và thường nghe nhầm thành một từ rất khác so với từ được thì thầm. Tuy nhiên, có một điều chắc chắn: một đứa trẻ nhất định sẽ luôn nghe một từ nhất định theo cùng một cách, nghĩa là nếu đứa trẻ $D$ được thì thầm từ $A$, nó sẽ luôn thì thầm (hoặc nói to nếu là người cuối cùng trong hàng) cùng một từ đó, bất kể nó đang đứng ở đâu trong hàng hay ai là người thì thầm từ $A$ cho nó.

Để giải trí, cô giáo quyết định thực hiện một thí nghiệm: cô lặp lại trò chơi này $N!$ lần, mỗi lần cho một thứ tự xếp hàng khác nhau của bọn trẻ. Cô nhận thấy có một từ xuất hiện đúng $K$ lần với tư cách là từ mà đứa trẻ cuối cùng nói to. Cô tự hỏi làm thế nào điều đó có thể xảy ra và nhờ bạn tái tạo lại tình huống như vậy.

Cho trước các số $N$ và $K$. Hãy xác định kích thước từ vựng $M$ và một từ $X$ ($1 \le X \le M$) từ từ vựng đó, đồng thời với mỗi đứa trẻ trong số $N$ đứa trẻ và mỗi từ trong số $M$ từ, hãy xác định từ mà đứa trẻ đó sẽ truyền đi nếu nó nghe được từ đã cho, sao cho từ $X$ được chọn sẽ được đứa trẻ cuối cùng trong hàng nói to đúng $K$ lần (trong tổng số $N!$ thứ tự). Điểm số của bạn phụ thuộc vào kích thước từ vựng đã chọn, trong đó từ vựng nhỏ hơn sẽ nhận được nhiều điểm hơn.

Để biết chi tiết, hãy xem phần Nhiệm vụ con.

Dữ liệu vào

Dòng đầu tiên chứa số hiệu nhiệm vụ con $P$ ($1 \le P \le 2$) từ phần Nhiệm vụ con, và dòng thứ hai chứa số lượng kịch bản kiểm thử $T$ ($1 \le T \le 10$). Các kịch bản là độc lập với nhau, nghĩa là có nhiều trường hợp kiểm thử trong một tệp dữ liệu vào.

Trong mỗi $T$ dòng tiếp theo chứa hai số nguyên $N$ và $K$ ($1 \le N \le 12, 0 \le K \le N!$) tương ứng với một kịch bản kiểm thử.

Dữ liệu ra

Với mỗi kịch bản trong số $T$ kịch bản, ở dòng đầu tiên hãy in ra hai số: $M$ và $X$ ($1 \le X \le M \le 10\,000$), kích thước từ vựng và từ mà đứa trẻ cuối cùng nói to trong $K$ trò chơi. Trong $N$ dòng tiếp theo, mỗi dòng in ra $M$ số: số thứ $j$ trong dòng thứ $i$ biểu thị từ mà đứa trẻ thứ $i$ sẽ truyền đi nếu nó được thì thầm từ $j$.

Nhiệm vụ con

Các trường hợp kiểm thử được chia thành hai nhiệm vụ con, hãy đọc kỹ mô tả của từng phần. Nếu chương trình của bạn không chính xác ở bất kỳ trường hợp nào, bạn sẽ nhận được 0 điểm cho nhiệm vụ con đó.

Nhiệm vụ con 1 có tổng giá trị 30 điểm, trong đó $1 \le N \le 7$. Đối với nhiệm vụ con này, bạn có thể đạt được 0 hoặc toàn bộ số điểm. Với điều kiện chương trình của bạn đúng trên tất cả các trường hợp, điều kiện bổ sung duy nhất là $M \le 10\,000$.

Nhiệm vụ con 2 có tổng giá trị 70 điểm, trong đó $1 \le N \le 12$. Đối với nhiệm vụ con này, bạn có thể đạt được điểm từng phần. Đối với mỗi kịch bản của mỗi trường hợp, số điểm mà thuật toán của bạn đạt được sẽ được xác định. Thuật toán của bạn sẽ nhận được $70 \cdot B$ điểm, trong đó $B$ là số điểm tối thiểu trên tất cả các kịch bản trong nhiệm vụ con. Điểm số cho một kịch bản $B_S$ được tính như sau:

• Nếu $M \le N + 1$, thì $B_S = 1$
• Nếu không, nếu $M \le N + 5$, thì $B_S = 0.7 + 0.15 / (M - N - 1)$ (với $0.7 \le B_S \le 0.85$)
• Nếu không, nếu $M \le 5N$, thì $B_S = 0.5 + 0.05 \cdot (5 - M/N)$ (với $0.5 \le B_S \le 0.7$)
• Nếu không, nếu $M \le 10\,000$, thì $B_S = 0.5 / (\log_{10}(M / 5N) + 1)$ (với $0.0 \le B_S \le 0.5$)

Ví dụ

Dữ liệu vào 1

1
2
3 2
2 1

Dữ liệu ra 1

3 3
2 1 3
3 2 2
1 3 2
2 1
1 1
2 2

Ghi chú

Giải thích ví dụ đầu tiên: trong trò chơi đầu tiên, nếu thứ tự trẻ là $(1, 2, 3)$, điều sau đây sẽ xảy ra: cô giáo thì thầm từ $1$ cho đứa trẻ đầu tiên. Nó thì thầm từ $2$ cho đứa trẻ thứ hai. Đứa trẻ thứ hai thì thầm từ $2$ cho đứa trẻ thứ ba và nó nói to từ $3$. Thứ tự trẻ tương ứng thứ hai là $(3, 2, 1)$, trong đó các từ được nói ra lần lượt là $1$ (cô giáo), $1$ (đứa trẻ số $3$), $3$ (đứa trẻ số $2$), $3$ (đứa trẻ số $1$). Đối với bốn thứ tự còn lại, đứa trẻ cuối cùng nói ra từ khác $3$.

Dữ liệu vào 2

2
2
3 3
4 0

Dữ liệu ra 2

6 2
1 2 3 4 5 6
6 5 4 3 2 1
2 4 1 4 3 2
2 2
1 1
1 1
1 1
1 1

Ghi chú

Giải thích ví dụ thứ hai: đây là một ví dụ trong nhiệm vụ con thứ hai có tính điểm từng phần. Đối với kịch bản đầu tiên, $N + 1 < M \le N + 5$ thỏa mãn, vì vậy kết quả này có giá trị $0.77$ (làm tròn đến hai chữ số thập phân). Đối với kịch bản thứ hai, $M \le N + 1$ thỏa mãn, vì vậy kết quả này có giá trị $1$. Vì lấy giá trị tối thiểu trên tất cả các kịch bản kiểm thử, giải pháp này sẽ nhận được $0.77$ tổng số điểm cho ví dụ này.