BTFENCE - Hàng rào lượn sóng
BT đã xây dựng xong cho mình một ngôi nhà mới. Công việc cuối cùng là cần phải làm một hàng rào ở mặt tiền của ngôi nhà. Vốn là một con người kỳ quặc, BT muốn dựng một hàng rào theo qui tắc sau:
Hàng rào được ghép từ tấm gỗ có chiều rộng đơn vị và chiều cao là (hai tấm gỗ khác nhau có chiều cao khác nhau)
Các tấm gỗ phải được ghép lại theo qui tắc, mỗi một tấm, ngoại trừ tấm số và tấm số thì hoặc thấp hơn hai tấm gỗ bên cạnh hoặc cao hơn hai tấm này
Chính xác hơn, hàng rào có thể xem như là một hoán vị của sao cho:
BT nhanh chóng phát hiện ra rằng sẽ có nhiều hàng rào khác thỏa mãn các yêu cầu trên. Ông ta ghi lại các hàng rào lần lượt từ nhỏ đến lớn theo qui tắc: Hàng rào (được mô tả bời hoán vị ) nhỏ hơn hàng rào B (được mô tả bởi hoán vị ) nếu như tồn tại số tự nhiên mà và . Hàng rào đầu tiên mang thứ tự .
Ví dụ với n =4 thì các hàng rào trong từ điển được mô tả như hình dưới đây:
Tất nhiên là BT đã quyết định chọn một hàng rào trong số các hàng rào khác nhau kể trên. Khi đến chơi nhà một người bạn, ông ta khoe hàng rào của mình. Tuy nhiên vì không mang theo bản ghi chép nên ông ta chỉ có thể nói cho người bạn số thứ tự hàng rào mà ông lựa chọn. Hãy giúp BT vẽ lại chính xác hàng rào này.
Dữ liệu vào:
Dòng đầu tiên ghi số nguyên dương là số bộ dữ liệu.
dòng tiếp theo, mỗi dòng mô tả một test gồm hai số nguyên dương lần lượt là số tấm gỗ và số thứ tự hàng rào của BT. Dữ liệu đảm bảo rằng tồn tại hàng rào thứ tự . Hơn nữa với số lượng hàng rào sẽ nằm trong phạm vi kiểu số nguyên có dấu (long long với C++ và int64 với Pascal)
Dữ liệu ra:
In ra dòng, mỗi dòng ghi kết quả của một test theo thứ tự trong dữ liệu vào
